用素数可以降低hash冲突，为什么hashmap底层使用二倍扩容的方式，这样做的目的是为什么？

Answer 1

liuyubobobo 2018-07-04 09:58:41

事实上，HashTable底层实现，扩容不是二倍方式，而是二倍加一。即原来有c的空间，经过扩容以后，有2*c+1的空间：）（initialCapacity取11）

这个方案是在编程简单和“尽量”避免哈希冲突之间的一个平衡。使用这种方式，即使某个空间大小不是一个素数，也不会像不断乘以二那样糟糕：）

如果你学习过我的《算法与数据结构》，并且看过第二章的补充代码：希尔排序，就会知道，其实在希尔排序中，也使用过类似的技巧。对于希尔排序的步长数列，数学家给出了很多最优解的猜想，不过通常，我们编程实现，直接使用3*h+1的方式获得这个步长序列。生成简单，又不失效率：）

• 提问者 慕容9198694 #1

  非常感谢！

• liuyubobobo 回复 提问者 慕容9198694 #2

  抱歉，我搜索这个问题的时候，发现我在这个问题下的回答有误。我在这里介绍的是HashTable的底层实现方式。HashMap确实是而被扩容的方式，具体可以参考这个问答：https://coding.imooc.com/learn/questiondetail/72069.html

• 提问者 慕容9198694 回复 liuyubobobo #3

  我前几天从新看了hashmap的底层，把hash%length的方式改成了hash&length-1，但是改成这个的条件是length是2^n,这样length-1的二进制码就是1111111的形式，能够使hash值分布均匀，同时不造成空间的浪费，所以2倍扩容是有道理的

点开查看后面2条评论