什么是哈希?
翻译成 “散列” ,就是把任意长度的输入,通过散列算法,变成固定长度的输出,该输出就是 散列值 ,这个映射函数叫做散列函数,存放记录的数组叫做 散列表 。
假设现在有100个盒子,每个盒子随机放有编号1-100的数字,如果现在我们要找出49号数字,那么就需要一个一个盒子找下去,最坏情况就是在最后一个盒子中才找出来49号,这种查找方式太慢了。
如何快速找到我们想要的数字呢?
可以通过hash算法,在盒子中放入编号n的时候,通过一个方法fn(),计算出对应盒子的index,找的时候再通过对应的编号n,通过方法fn(),同样计算出index,就可以快速的定位到具体的盒子。哈希其实就是通过fn()计算出来的index,哈希方法就是fn()。
什么是完美哈希?
如果存在函数h(x)将 集合 U映射到集合S并且没有碰撞, 我们就可以说h(x)是集合U到集合S的完美 hash函数 。 完美哈希函数 是静态的,就意味着事前必须知道需要哈希哪些数据。同时生成的算法比较复杂,需要很长的时间来建立 索引 。没有办法实时添加更新。
什么是哈希冲突?
通过上面100个盒子的示例,假设现在有101个数字需要放入100个盒子,多出来的这个数字如果一定要放入某个盒子,那么必定会跟某个数字挤在一个盒子里面,其实这个时候就出现了冲突。
我们知道哈希值是通过哈希函数计算出来的,那么哈希冲突就是两个不同值的东西,通过哈希函数计算出来的哈希值相同,这样他们存在数组中的时候就会发生冲突,这就是哈希冲突。
怎么解决哈希冲突?
1.开放地址法
这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。
就是说当发生冲突时,就去寻找下一个空的地址把数据存入其中,只要 哈希表 足够大,就总能找到这样一个空的地址。
2.拉链法
将所有关键字为同义字的记录存储在一个单链表中
3.再哈希法
在发生冲突的时候再用另外一个哈希函数算出哈希值,直到算出的哈希值不同为止。
4.建立公共溢出区
在创建哈希表的同时,再额外创建一个公共溢出区,专门用来存放发生哈希冲突的元素。查找时,先从哈希表查,查不到再去公共溢出区查。
HashMap JDK1.7
JDK 1.7中 HashMap 的底层数据结构是数组 + 链表 ,使用 Entry 类存储 Key 和 Value。结构如下:
如果出现哈希冲突那么,结构就会变成:
那么当哈希冲突的次数比较多的时候,这个时候链表将会越来越长,查找的性能就会降低。
HashMap JDK1.8
JDK 1.8 中 HashMap 的底层数据结构是数组 + 链表 / 红黑树 ,用 Node 类存储 Key 和 Value.这里的Node其实跟Entry结构基本一致。
当链表的长度大于 8 的时候就会转换为红黑树,不过在转换之前,会先去查看 table 数组的长度是否大于 64,如果数组的长度小于 64,那么 HashMap 会优先选择对数组进行扩容 ,而不是把链表转换成红黑树,如下图:
HashMap数组扩容
通过之前可以知道,数组容量是有限的,如果数据多次插入并到达一定的数量就会进行数组扩容,也就是 resize 方法。什么时候会进行 resize 呢?与两个因素有关:
1) Capacity :HashMap 当前最大容量/长度
2) LoadFactor :负载因子,默认值0.75f
如果当前存入的数据数量大于 Capacity * LoadFactor 的时候,就会进行数组扩容 resize 。就比如当前的 HashMap 的最大容量大小为 100,当你存进第 76 个的时候,判断发现需要进行 resize了,那就进行扩容。当然, Hash Map 的扩容不是简单的扩大点容量这么简单的。
扩容 resize 分为两步 :
1)扩容:创建一个新的 Entry/Node 空数组,长度是原数组的 2 倍
2)ReHash:遍历原 Entry/Node 数组,把所有的 Entry/Node 节点重新 Hash 到新数组
为什么要 ReHash 呢?直接复制到新数组不行吗?
显然是不行的,因为数组的长度改变以后,Hash 的规则也随之改变。index 的计算公式是这样的:
- index = HashCode (key) & (Length – 1)
比如说数组原来的长度(Length)是 4,Hash 出来的值是 2 ,然后数组长度翻倍了变成 16,显然 Hash 出来的值也就会变了。画个图解释下:
HashMap 的默认初始数组长度是多少?为什么是这么多?
默认数组长度是 16,其实只要是 2 的次幂都行,至于为啥是 16 呢,我觉得应该是个经验值问题, Java 作者是觉得 16 这个长度最为常用。
那为什么数组长度得是 2 的次幂呢?
首先,一般来说,我们常用的 Hash 函数 是这样的:index = HashCode(key) % Length,但是因为 位运算 的效率比较高嘛,所以 HashMap 就相应的改成了这样:index = HashCode(key) & (Length – 1)。