HashMap

JDK1.8之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置 (这里的 n 指的是数组的⻓度)，如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现 比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码**: ** JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。

   static final int hash(Object key) {
       int h;
// key.hashCode():返回散列值也就是hashcode
// ^ :按位异或
// >>>:无符号右移，忽略符号位，空位都以0补⻬
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

} 对比一下 JDK1.7的 HashMap 的 hash 方法源码.

 static int hash(int h) {
     // This function ensures that hashCodes that differ only by
     // constant multiples at each bit position have a bounded
     // number of collisions (approximately 8 at default load factor).
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
 }

相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

所谓 “拉链法” 就是:将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链 表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8之后

相比于之前的版本， JDK1.8之后在解决哈希冲突时有了􏰀大的变化，当链表⻓度大于阈值(默认为8)

时，将链表转化为红黑树，以减少搜索时间

原文:https://zhuanlan.zhihu.com/p/21673805

为什么HashMap 容量 都为 2 的N次方

1.在计算hash的时候，确定落在数组的位置的时候，计算方法是(n - 1) & hash ，奇数n-1为偶数，偶数2进制的结尾都是0，经过&运算末尾都是0，会增加hash冲突。

2.为啥要是2的幂,

1) hashmap 结构是数组，每个数组里面的结构是node（链表或红黑树），正常情况下，如果你想放数据到不同的位置，肯定会想到取余数确定放在那个数据里,计算公式：hash % n，这个是十进制计算。在计算机中， (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n，计算更加高效。

2)只有是2的幂数的数字经过n-1之后，二进制肯定是 …11111111 这样的格式，这种格式计算的位置的时候（&），完全是由产生的hash值类决定，而不受n-1(组数长度的二进制) 影响。你可能会想，受影响不是更好么，又计算了一下，类似于扰动函数，hash冲突可能更低了，这里要考虑到扩容了，2的幂次方*2，在二进制中比如4和8，代表2的2次方和3次方，他们的2进制结构相 似,比如4和8 00000100 , 0000 1000 只是高位向前移了一位，这样扩容的时候，只需要判断高位hash,移动到之前位置的倍数就可以了，免去了重新计算位置的运算。

ConcurrentHashMap

JDK1.8之后

ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟 HashMap1.8的结构类似，数组+链表/红黑二叉树。Java 8在链表⻓度超过一定阈值(8)时将链表(寻 址时间复杂度为O(N))转换为红黑树(寻址时间复杂度为O(log(N)))

synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又 提升N倍。