HashMap：数组+链表+红黑树，环链表尾插法，二的倍数数组

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

版本：JDK1.8。

这里把数组每个元素称为桶

  1. 使用数组+链表+红黑树：使用红黑树为了解决链表过长导致性能下降的问题。链表大于8就会转为红黑树

  2. JDK1.8后，hashmap使用尾插法。新增的元素会放在bucket(桶)的最后面。

  • 为了解决头插入法在多线程下可能出现环链表的问题。同时链表内元素顺序保持不变

  1. 使用2的倍数作为数组的大小：更加容易计算他们所在的桶

如果是2的倍数的话，更容易计算所在的桶。比如原来是4，扩展为8

  • 在原来桶0的元素，会在新的桶0和4中

  • 在原来桶1的元素，会在新的桶1和5中

  • 在原来桶2的元素，会在新的桶2和6中

  • 在原来桶3的元素，会在新的桶3和7中

为什么会这样呢？首先需要是将hash值取余得到所在桶。

原来通长度是4，取余则是二进制后两位。比如在桶0，后两位必然是00，桶1则是01，桶2则是10,桶3则是11。对于长度为8，则是3位，原来桶0的00将有两种可能：000和100也就是桶0和桶4(原来桶位置 + 原来桶长度 = 0 + 4)。

参考：

  1. 关于JDK1.8 HashMap扩容部分源码分析 ：在resize扩容为什么会出现环链表

  2. jdk1.8的HashMap和ConcurrentHashMap

以上是 HashMap：数组+链表+红黑树，环链表尾插法，二的倍数数组 的全部内容， 来源链接： utcz.com/z/514939.html

回到顶部