07 | 深入浅出HashMap的设计与优化
常用的数据结构
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
《Java 性能调优实战》，新⼈⾸单¥59
全部留言(64)
- 最新
- 精选
陆离2的幂次方减1后每一位都是1，让数组每一个位置都能添加到元素。 例如十进制8，对应二进制1000，减1是0111，这样在&hash值使数组每个位置都是可以添加到元素的，如果有一个位置为0，那么无论hash值是多少那一位总是0，例如0101，&hash后第二位总是0，也就是说数组中下标为2的位置总是空的。 如果初始化大小设置的不是2的幂次方，hashmap也会调整到比初始化值大且最近的一个2的幂作为capacity。作者回复: 回答正确，就是减少哈希冲突，均匀分布元素。
6125
giserway1）通过将 Key 的 hash 值与 length-1 进行 & 运算，实现了当前 Key 的定位，2 的幂次方可以减少冲突（碰撞）的次数，提高 HashMap 查询效率； 2）如果 length 为 2 的次幂，则 length-1 转化为二进制必定是 11111…… 的形式，在于 h 的二进制与操作效率会非常的快，而且空间不浪费；如果 length 不是 2 的次幂，比如 length 为 15，则 length-1 为 14，对应的二进制为 1110，在于 h 与操作，最后一位都为 0，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。作者回复: 回答非常到位
457
Sdylan装载因子0.75是怎么算出来了，是经验值还是什么？ 另外为什么链表长度8就要转红黑树呢作者回复: 加载因子过高，虽然提高了空间的利用率，但增加了查询时间的成本；加载因子过低，虽然减少查询时间的成本，但是空间利用率又很低了。所以0.75是一个折中的选择。 链表长度为8转为红黑树的原因是，官方根据泊松分布实验发现，假设hashmap长度length为16，假设放入12（0.75*16）个数据到hashmap中，链表中存放8个节点的概率仅为0.00000006，而链表中存放1~7节点的概率为： 0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 从以上可知，实际上一个链表被放满8个节点的概率非常小，实际上链表转红黑树是非常耗性能的，而链表在8个节点以内的平均查询时间复杂度与黑红树相差无几，超过8个节点，黑红树的查询复杂度会好一些。所以，当链表的节点大于等于8个的时候，转为红黑树的性价比比较合适。
439
大虫子老师您好，能解答下，为什么JDK1.8之前，链表元素增加采用的是头插法，1.8之后改成尾插法了。1.8之前采用头插法是基于什么设计思路呢？作者回复: 你好，JDK1.7是考虑新增数据大多数是热点数据，所以考虑放在链表头位置，也就是数组中，这样可以提高查询效率，但这种方式会出现插入数据是逆序的。在JDK1.8开始hashmap链表在节点长度达到8之后会变成红黑树，这样一来在数组后节点长度不断增加时，遍历一次的次数就会少很多，相比头插法而言，尾插法操作额外的遍历消耗已经小很多了。 也有很多人说避免多线程情况下hashmap扩容时的死循环问题，我个人觉得避免死循环的关键不在尾插法的改变，而是扩容时，用了首尾两个指针来避免死循环。这个我会在后面的多线程中讲到hashmap扩容导致死循环的问题。
431
嘉嘉☕加载因子那块儿，感觉有点跳跃，为什么加载因子越大，对空间利用越充分呢？作者回复: 加载因子是扩容的参考标准，如果加载因子越大，例如默认数组初始化大小为16，加载因子由0.75改成1.0，原来数组长度到了12就扩容，变成数组大小为16，也就是说被占满了，才会进行扩容，这也可能意味着已经发生了很多哈希冲突，这样导致某些数组中的链表长度增加，影响查询效率。
330
孙志强以前看源码，我记得好像链表转换红黑树不光链表元素大于8个，好像还有一个表的大小大于64作者回复: 对的，有这样一个条件。
22
小小征0 的话索引不变，1 的话索引变成原索引加上扩容前数组。 这句有点不理解 老师作者回复: 以下是resize中判断是否位移的部分代码，我们可以看到元素的hash值与原数组容量运算，如果运算结果为0，保持原位，如果运算结果为1，则意向扩容的高位。 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } 假设链表中有4、8、12，他们的二进制位00000100、00001000、00001100，而原来数组容量为4，则是 00000100，以下与运算： 00000100 & 00000100 = 0 保持原位 00001000 & 00000100 = 1 移动到高位 00001100 & 00000100 = 1 移动到高位
1012
-W.LI-老师好。hashmap的put和get的时间复杂度算多少啊?最好O(1)。最坏复杂度是O(log(n))平均是O(1)么?。。。treeMap的,treeMap，putO(n)，getO(1)?之前面试被问了，不晓得哪错了作者回复: 面试的时候，问到时间复杂度，大部分是考察你对数据结构的了解程度。建议可以多复习下数据结构的知识。 hashmap的最优时间复杂度是O（1），而最坏时间复杂度是O(n)。 在没有产生hash冲突的情况下，查询和插入的时间复杂度是O(1)； 而产生hash冲突的情况下，如果是最终插入到链表，链表的插入时间复杂度为O(1)，而查询的时候，时间复杂度为O(n)； 在产生hash冲突的情况下，如果最终插入的是红黑树，插入和查询的平均时间复杂度是O（logn）。 而TreeMap是基于红黑树实现的，所以时间复杂度你也清楚了吧。
211
Chocolate老师，您好，请教一个问题，为什么 HashMap 的容量等于数组长度？但是扩容的时候却是根据 Map 里的所有元素总数去扩容，这样会不会导致数组中的某一个 node 有很长的链表或红黑树，数组中的其他位置都没有元素？谢谢作者回复: 这种数据倾斜的可能性比较小
28
M.c“这是因为链表的长度超过 8 后，红黑树的查询效率要比链表高，所以当链表超过 8 时，HashMap 就会将链表转换为红黑树”，此处转换为红黑树少了个条件吧？MIN_TREEIFY_CAPACITY要同时大于64作者回复: 是的，在源码中可以查到对于的代码，链表长度大于8而且整个map中的键值对大于等于MIN_TREEIFY_CAPACITY (64)时，才进行链表到红黑树的转换。
3
