← 返回目录

什么时候会树化

第 10 / 17 卷

链表长度超过树化阈值8

数组长度大于等于64

当链表长度超过8时, 若数组长度小于64, 则会对数组进行扩容, 然后二次哈希的值就会变, 此时链表的部分值就会重新分配到数组其他位置. 二次分配后链表长度未

必大于8, 所以必须同时满足两个条件才会树化.

为何一上来不树化

刚开始链表的长度可能只有三四个, 如果此时树化, 那么树化后查询的效率和短链表差不多. 所以, 在短链表的情况下, 树化意义不大.

而且链表的节点是Node, 红黑树的节点为TreeNode. TreeNode的内存占用大于 Node.

为何树化阈值为8

红黑树是为了防止链表超长时性能下降,树化应当是偶然情况. 长度超过8的链表出现几率非常小, 选择8就是为了让树化几率足够小

hash表的查找, 更新的时间复杂度是O(1). 而红黑树的查找, 更新的时间复杂度是 O(log2n), TreeNode占用空间也比普通Node的大,所以如非必要,尽量还是使

用链表。

索引如何计算? hashCode有了, 为何还有hash()方法? 数组容量为

何是2^n?

索引计算方式

对任何一个对象调用其hashCode()方法会获得其原始hash值.

对原始hash值再调用HashMap的hash方法进行二次hash, 获取到二次hash 值.

二次hash值对数组容量进行取余操作获取到存放的数组下标.

为何需要二次hash?

全站分卷索引 · 17 卷
  1. 1JavaSE
  2. 2深拷贝和浅拷贝区别?什么是引用拷贝
  3. 3hashCode() 有什么用?
  4. 4面向对象的三大特征
  5. 5String直接赋值和new对象的区别
  6. 6字符串拼接用“+” 还是 StringBuilder?
  7. 7集合
  8. 8ArrayList的扩容机制
  9. 9HashMap (常考)
  10. 10什么时候会树化
  11. 11HashMap的put()方法流程
  12. 12多线程操作HashMap会出现什么问题
  13. 13特性
  14. 14反射
  15. 15什么是死锁
  16. 16提交一个新任务到线程池时,具体的执行流程 / 线程池的工作流程
  17. 17Executors创建线程池会存在什么问题