HashMap 长度及死循环问题

HashMap 的长度为什么是2的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。 Hash 值的范围为 -2147483648 到 2147483647，前后加起来大概是40亿的映射空间，只要哈希函数映射得比较均匀松散，一般情况是很难出现碰撞的。但问题是，一个40亿长度的数组，内存是放不下的，所以这个散列值是不能直接拿来用的。用之前，还要先做对数组长度的取模运算，得到的余数，才是用来要存放的位置（也就是对应的数组下标）。这个数组下标的计算方法是 (n - 1) & hash。（n代表数组长度）。这也就解释了 HashMap 的长度为什么是2的幂次方。

这个算法应该如何设计？

首先，我们可能会想到采用%取余的操作来实现。但是，取余(%)操作中，如果除数是2的幂次，则等价于与其除数减一的与(&)操作（hash%length == hash&(length-1)，前提是 length 是2的 n 次方；）， 而且采用二进制位操作 &，相对于%能够提高运算效率，这同样解释了 HashMap 的长度为什么是2的幂次方。

HashMap 多线程操作导致死循环问题

主要原因是由于多并发情况下， rehash 操作可能会造成元素间形成一个循环链表。不过，JDK1.8 后问题已经解决，但还是不建议在多线程下使用 HashMap，因为还是会存在其他问题，比如：数据丢失。并发环境下，强烈推荐使用 ConcurrentHashMap 。

参考阅读：JAVA HASHMAP的死循环