HashMap是大家都在用，面试的时候也经常会被考的考点，在这篇文章中介绍下HashMap的hash碰撞和减轻碰撞的优化。
1、什么是hash碰撞
在解释Hash碰撞之前先说一下hashmap的存储结构、添加和检索是怎么实现的
1.1HashMap的存储结构
· HashMap的存储结构是Entry数组+链表的结构,如下图
HashMap存储结构
注意：数组+链表的结构是在JDK7中的数据结构，JDK8中已经变成数组 +（链表或红黑树）的结构
1.2添加元素
添加过程：
1、通过key的hashcode调用hash()函数，计算出hash值，
2、计算数组存储数据的下标 index =hash&(数组长度n-1)
3、通过index得到数组中对应位置的链表，JDK7中将新节点插入到链表头，而JDK8插入到链表尾部
HashMap添加元素还有一个知识点就是多线程不安全，扩容造成元素丢失或者链表闭环的问题，这个知识点不在这篇文章中详述。
1.3快速检索
通过key查询value的过程：
1、通过Key的hashcode调用hash()函数，计算出hash值，
2、计算数组下标 index =hash&(数组长度n-1)
3、通过index得到数组中对应位置的链表，遍历链表的Entry通过==对key进行比较得到对应的entry
知道HashMap的添加和查询过程，来看一下什么是Hash碰撞
1.4Hash碰撞是什么，Hash碰撞严重会有什么问题
在HashMap的查询和添加过程中，绕不过去的是计算元素在数组的位置index，key的HashCode作为这个计算的基础。计算后的Hash值存在相同的情况，hash与长度取余的结果也有相同的情况，这个时候运算结果相同的两个对象就需要存储到同一个链表中，这就是HashMap中的Hash碰撞。
这样会引起什么问题呢，碰撞严重的话，大量的元素都存储在一个链表中，检索过程中的第三步，遍历链表会耗费大量的时间，严重极端情况下会遍历所有元素，检索效率会很低。和HashMap快速检索的设计严重不符。
hash碰撞严重回来带查询效率问题，那么HashMap做了什么优化，来避免Hash碰撞呢
2、HashMap碰撞优化
HashMap减轻Hash碰撞主要做了两个方面的优化，
1）提高hash的复杂度，减少相同hash的出现
2）让元素尽量均匀的分部到数组中
2.1提高hash复杂度
看一下JDK8中hash()函数的代码
static final int hash(Object key) {
int h;
return (key ==null) ?0 : (h = key.hashCode()) ^ (h >>>16);
}
很简单，将key的HashCode右移16位将高16位和低16位做异或运算，目的是让hash值得低16位也包含高16位的特性。
这样做有什么好处呢，元素在数组的下标index =hash%数组长度n，当数组长度很短的时候，如初始状态下是16，如果两个key的HashCode低16位相同，不处理的话index计算结果相同。只要HashCode不同的话，计算后的hash低16位保证不会相同。增强了hash结果的复杂度。
注意：JDK7中hash函数要比JDK8中复杂度高很多，所以7的计算结果减少hash碰撞的效果更好，那为什么8不增加复杂度反而降低复杂度呢。官方解释是，因为JDK8在链表存储的基础上增加了红黑树的存储方式，提高了碰撞引起的查询效率。应该是对红黑树的效率比较有信心。
2.2让元素尽量均匀分部
前边已经说过，数组的下标的计算是：
index= hash&（数组长度n-1）
用17作为长度n计算一下取余，7转成二进制是 0001 0001 ，hash&（0001 0001 -1） =hash&(0001 0000) , 类似 0100 1001 和0010 1111的hash就会发生碰撞。
怎么解决这个问题呢，保证&运算中二进制数每一位都是1，也就是数组的长度保证是2的整数次幂，就不会出现分不到元素的情况了。
所以HashMap中对的优化策略就是，数组的长度必须是2的整数次幂。
注意：在HashMap扩容这个过程中，元素数量达到loadFactor*capacity，数组会扩容到2的n+1次幂，这个时候，map中存储的元素数量是 2的n次幂*loadFactor，
也就是说只要loadFactor<1，那么HashMap的数组长度永远大于元素数量，所以我理解的HashMap是空间换时间的容器。
Hash碰撞的知识点都已经说完了，分享一个在hashMap中的函数，代码如下
static final int tableSizeFor(int cap) {
int n = cap -1;
n |= n >>>1;
n |= n >>>2;
n |= n >>>4;
n |= n >>>8;
n |= n >>>16;
return (n <0) ?1 : (n >=MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY : n +1;
}
返回结果是一个2的整数次幂
如有遗错请留言，会尽快修改
网友评论