Java 数据结构与算法系列精讲之哈希算法实现
概述
从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.
获取哈希值
hashCode()
方法可以返回一个对象的哈希值. 需要注意的是, 我们需要对值进行装箱, 才能调用
hashCode()
方法.
例子:
public static void main(String[] args) { // 小数 Integer a = 1; System.out.println(a.hashCode()); // 负数 Integer b = -1; System.out.println(b.hashCode()); // 小数 Double c = 1.23; System.out.println(c.hashCode()); // 字符串 String d = "Hello World"; System.out.println(d.hashCode()); }
输出结果:
1
-1
1158867386
-862545276
哈希冲突
哈希冲突 (Hash Collision) 存在的原因是哈希算法被计算的数是无限的, 然而计算后的结果范围有限. 所以会出现两个不同的数据得到相同的哈希值的情况, 即哈希冲突.
哈希冲突的处理办法:
- 链地址法: 将具有相同的 hash 值的 key 放入到同一个桶中
- 开放地址法: 将具有相同 hash 值的 key 的后一个值向后顺移到空位
到此这篇关于Java 数据结构与算法系列精讲之哈希算法实现的文章就介绍到这了,更多相关Java 哈希算法实现内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!
相关推荐
-
一篇文章读懂Java哈希与一致性哈希算法
目录 哈希 Hash 算法介绍 分布式存储场景 场景描述: 实现思路: 缺点: 一致性Hash算法 节点增加场景 节点减少场景 节点分布不均匀 虚拟节点 增加节点 节点减少 总结 哈希 Hash 算法介绍 哈希算法也叫散列算法, 不过英文单词都是 Hash, 简单一句话概括, 就是可以把任意长度的输入信息通过算法变换成固定长度的输出信息, 输出信息也就是哈希值, 通常哈希值的格式是16进制或者是10进制, 比如下面的使用 md5 哈希算法的示例 md5("123456") =>
-
一文彻底搞定Java哈希表和哈希冲突
一.什么是哈希表? 哈希表也叫散列表,它是基于数组的.这间接带来了一个优点:查找的时间复杂度为 O(1).当然,它的插入时间复杂度也是 O(1).还有一个缺点:数组创建后扩容成本较高. 哈希表中有一个"主流"思想:转换.一个重要的概念是将「键」或「关键字」转换成数组下标.这由"哈希函数"完成. 二.什么是哈希函数? 由上,其作用就是将非 int 的键/关键字转化为 int 的值,使可以用来做数组下标. 比如,HashMap 中就这样实现了哈希函数: static f
-
Java数据结构之实现哈希表的分离链接法
哈希表的分离链接法 原理 Hash Table可以看作是一种特殊的数组.他的原理基本上跟数组相同,给他一个数据,经过自己设置的哈希函数变换得到一个位置,并在这个位置当中放置该数据.哦对了,他还有个名字叫散列 0 1 数据1 数据2 就像这个数组,0号位置放着数据1,1号位置放数据2 而我们的哈希表则是通过一个函数f(x) 把数据1变成0,把数据2变成1,然后在得到位置插入数据1和数据2. 非常重要的是哈希表的长度为素数最好!! 而且当插入数据大于一半的时候我们要进行扩充!!! 冲突问题产生 现在
-
Java深入了解数据结构之哈希表篇
目录 1,概念 2,冲突-避免 3,冲突-避免-哈希函数设计 4,冲突-避免-负载因子调节 5,冲突-解决-闭散列 ①线性探测 ②二次探测 6,冲突-解决-开散列/哈希桶 7,完整代码 1,概念 顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键 码的多次比较.顺序查找时间复杂度为O(N),平衡树中为树的高度,即O( ),搜索的效率取决于搜索过程中 元素的比较次数. 理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素. 如果构造一
-
Java实现哈希表的基本功能
一.哈希表头插法放入元素 /** * user:ypc: * date:2021-05-20; * time: 11:05; */ public class HashBuck { class Node { public int key; int value; Node next; Node(int key, int value) { this.key = key; this.value = value; } } public int usedSize; public Node[] array;
-
详解Java分布式系统中一致性哈希算法
业务场景 近年来B2C.O2O等商业概念的提出和移动端的发展,使得分布式系统流行了起来.分布式系统相对于单系统,解决了流量大.系统高可用和高容错等问题.功能强大也意味着实现起来需要更多技术的支持.例如系统访问层的负载均衡,缓存层的多实例主从复制备份,数据层的分库分表等. 我们以负载均衡为例,常见的负载均衡方法有很多,但是它们的优缺点也都很明显: 随机访问策略.系统随机访问,缺点:可能造成服务器负载压力不均衡,俗话讲就是撑的撑死,饿的饿死. 轮询策略.请求均匀分配,如果服务器有性能差异,则无法实现
-
带你了解Java数据结构和算法之哈希表
目录 1.哈希函数的引入 ①.把数字相加 ②.幂的连乘 2.冲突 3.开放地址法 ①.线性探测 ②.装填因子 ③.二次探测 ④.再哈希法 4.链地址法 5.桶 6.总结 1.哈希函数的引入 大家都用过字典,字典的优点是我们可以通过前面的目录快速定位到所要查找的单词.如果我们想把一本英文字典的每个单词,从 a 到 zyzzyva(这是牛津字典的最后一个单词),都写入计算机内存,以便快速读写,那么哈希表是个不错的选择. 这里我们将范围缩小点,比如想在内存中存储5000个英文单词.我们可能想到每个单词
-
Java 集合框架掌握 Map 和 Set 的使用(内含哈希表源码解读及面试常考题)
目录 1. 搜索 1.1 场景引入 1.2 模型 2. Map 2.1 关于 Map 的介绍 2.2 关于 Map.Entry<K, V> 的介绍 2.3 Map 的常用方法说明 2.4 关于 HashMap 的介绍 2.5 关于 TreeMap 的介绍 2.6 HashMap 和 TreeMap 的区别 2.7 Map 使用示例代码 3. Set 3.1 关于 Set 的介绍 3.1 Set 的常用方法说明 3.3 关于 TreeSet 的介绍 3.4 关于 HashSet 的介绍 3.5
-
Java 数据结构哈希算法之哈希桶方式解决哈希冲突
一. 实现形式一(键值对只能为整数) 我们可以先实现一个比较简单的哈希表,使用java中解决哈希冲突的方法,即哈希桶(开散列)方式实现,其中注意: 可以使用内部类方式定义节点 负载因子默认为0.75 因为我们使用的是哈希桶方式解决哈希冲突,所以在我们扩容成功之后,原来桶中的数据得重新哈希计算出新的位置,不然就和原来桶中的数据的位置不一样了 相关代码如下 public class HashBucket { static class Node {//使用内部类方式定义节点 public int ke
-
Java 数据结构与算法系列精讲之哈希算法实现
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 获取哈希值 hashCode()方法可以返回一个对象的哈希值. 需要注意的是, 我们需要对值进行装箱, 才能调用 hashCode()方法. 例子: public static void main(String[] args) { // 小数 Integer a = 1; System.out.println(a.hashCode()); // 负数 Integer b = -1; System.out.printl
-
Java 数据结构与算法系列精讲之贪心算法
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 贪心算法 贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果. 贪心算法的优缺点: 优点: 贪心算法的代码十分简单 缺点: 很难确定一个问题是否可以用贪心算法解决 电台覆盖问题 假设存在以下的广播台, 以及广播台可以覆盖的地区: 广播台 覆盖地区 K1 北京
-
Java 数据结构与算法系列精讲之排序算法
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 冒泡排序 冒泡排序 (Bubble Sort) 是一种简单的排序算法. 它重复地遍历要排序的数列, 一次比较两个元素, 如果他们的顺序错误就把他们交换过来. 遍历数列的工作是重复地进行直到没有再需要交换, 也就是说该数列已经排序完成. 这个算法的名字由来是因为越小的元素会经由交换慢慢 "浮" 到数列的顶端. 冒泡排序流程: 通过比较相邻的元素, 判断两个元素位置是否需要互换 进行 n-1 次比较,
-
Java 数据结构与算法系列精讲之KMP算法
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. KMP 算法 KMP (Knuth-Morris-Pratt), 是一种改进的字符串匹配算法. KMP 算法解决了暴力匹配需要高频回退的问题, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 从而大大提高效率. 如图: 举个例子 (字符串 "abcabcdef" 匹配字符串 "abcdef"): 次数 暴力匹配 KMP 算法 说明 1 abcabcdef abcdef
-
Java 数据结构与算法系列精讲之字符串暴力匹配
概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 字符串匹配 字符串匹配 (String Matching) 指的是判断一个字符串是否包含另一个字符串. 举个例子: 字符串 "Hello World" 包含字符串 "Hello" 字符串 "Hello World" 不包含字符串 "LaLaLa" 暴力匹配 暴力匹配 (Brute-Force) 的思路: 如果charArray1[i] ==
-
Java 数据结构与算法系列精讲之单向链表
目录 概述 链表 单向链表 单向链表实现 Node类 add方法 remove方法 get方法 set方法 contain方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 单向链表 单向链表
-
Java 数据结构与算法系列精讲之环形链表
目录 概述 链表 环形链表 环形链表实现 Node类 insert方法 remove方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 链表 链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大. 链表包括三类: 单向链表 双向链表 循环链表 环形链表 环形链表 (Circular Linked Li
-
Java 数据结构与算法系列精讲之栈
目录 概述 栈 栈实现 push方法 pop方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 栈 栈 (Stack) 是一种运算受限的线性表, 遵循先进后出的原则 (Last-In-First-Out). 举个例子, 当我们灌调料的时候, 后灌进去的调料会先被使用. 栈只能在表尾部进行插入和删除的操作. 开口的一端被称为栈顶, 另一端则被称为栈底. 如图: 栈实现 push 方法 栈 (Stack) 的 push 方法, 把项压入栈顶部.
-
Java 数据结构与算法系列精讲之数组
目录 概述 数组 声明数组的两个方法 创建数组的两个方法 索引 自定义数组 泛型 构造函数 元素操作 调用 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 数组 数组 (Array) 是有序数据的集合, 在 Java 中 java.util.Arrays包含用来操作数组的各种方法, 比如排序和搜索等. 其所有方法均为静态方法, 调用起来非常简单. 声明数组的两个方法 方法一: 数据类型[] array; 方法二: 数据类型 array[]; 创建数组的两
-
Java 数据结构与算法系列精讲之二叉堆
目录 概述 优先队列 二叉堆 二叉堆实现 获取索引 添加元素 siftUp 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 优先队列 优先队列 (Priority Queue) 和队列一样, 是一种先进先出的数据结构. 优先队列中的每个元素有各自的优先级, 优先级最高的元素最先得到服务. 如图: 二叉堆 二叉堆 (Binary Heap) 是一种特殊的堆, 二叉堆具有堆的性质和二叉树的性质. 二叉堆中的任意一节点的值总是大于等于其孩子节点值. 如图: 二
随机推荐
- JavaScript常用全局属性与方法记录积累
- JavaWeb实现文件上传下载功能实例详解
- iOS微信支付交互图分析
- javascript 利用arguments实现可变长参数
- 老生常谈PHP面向对象之解释器模式
- 用正则和xmlHttp实现的asp小偷程序
- 使用Memcache缓存mysql数据库操作的原理和缓存过程浅析
- 使用Cookies保存网站历史浏览记录实例代码
- python实现线程池的方法
- 用javascript删除当前行,添加行(示例代码)
- java实现一个简单TCPSocket聊天室功能分享
- jquery使用each方法遍历json格式数据实例
- JavaScript中具名函数的多种调用方式总结
- 一张图总结C++中关于指针的那些事
- Swift3迁移至Swift4可能遇到的问题小结
- Swift中排序算法的简单取舍详解
- Angular使用动态加载组件方法实现Dialog的示例
- C# / VB.NET 在PPT中创建、编辑PPT SmartArt图形的方法详解
- Docker数据卷常用操作代码实例
- Python实战之实现康威生命游戏