hash扩容的坑
来源：14-7 哈希表更复杂的动态空间处理方法
30K必胜
2019-01-12
虽然均摊复杂度是O(1)，但是在实际 的hash存储中在扩容阶段的O(n)还是无法忍受的，所以采用了O(2)的复杂度，也就是先扩容，不进行数据搬移，而是在每次存储一个新元素的时候搬移一个老元素，存储在重新计算的索引中，这样就避免了O(n)的问题。
有个小疑问想请教老师，就是我们这个代码所模拟的哈希表是不是对应java中的hashmap。没有看过java8的源码，也就是说java8中hashmap的底层是一个数组+链表或者treemap。
写回答
1回答
-
这个代码所模拟的哈希表不完全是java中的hashmap，但原理是一致的，都是链地址法：）
Java中的HashMap，最大的优化在于，当冲突达到一定程度，如果可能的话，每一个地址将对应一个平衡二叉树，而不仅仅是一个链表：）
10
相似问题