用素数可以降低hash冲突，为什么hashmap底层使用二倍扩容的方式，这样做的目的是为什么？
来源：14-8 更多哈希冲突的处理方法
慕容9198694
2018-07-04
写回答
1回答
-
事实上，HashTable底层实现，扩容不是二倍方式，而是二倍加一。即原来有c的空间，经过扩容以后，有2*c+1的空间：）（initialCapacity取11）
这个方案是在编程简单和“尽量”避免哈希冲突之间的一个平衡。使用这种方式，即使某个空间大小不是一个素数，也不会像不断乘以二那样糟糕：）
如果你学习过我的《算法与数据结构》，并且看过第二章的补充代码：希尔排序，就会知道，其实在希尔排序中，也使用过类似的技巧。对于希尔排序的步长数列，数学家给出了很多最优解的猜想，不过通常，我们编程实现，直接使用3*h+1的方式获得这个步长序列。生成简单，又不失效率：）
052018-08-09
相似问题