本文从三个部分去探究 HashMap 的链表转红黑树的具体时机:
一, 从 HashMap 中有关 "链表转红黑树" 阈值的声明;
二,[重点] 解析 HashMap.put(K key, V value)的源码;
三, 测试;
一, 从 HashMap 中有关 "链表转红黑树" 阈值的声明, 简单了解 HashMap 的链表转红黑树的时机
在 jdk1.8 HashMap 底层数据结构: 散列表 + 链表 + 红黑树 (图解 + 源码) 的 "四, 问题探究" 中, 我有稍微提到过散列表后面跟什么数据结构是怎么确定的:
HashMap 中有关 "链表转红黑树" 阈值的声明:
- /**
- * 使用红黑树 (而不是链表) 来存放元素. 当向至少具有这么多节点的链表再添加元素时, 链表就将转换为红黑树.
- * 该值必须大于 2, 并且应该至少为 8, 以便于删除红黑树时转回链表.
- */
- static final int TREEIFY_THRESHOLD = 8;
二,[重点] 解析 HashMap.put(K key, V value)的源码, 去弄清楚链表转红黑树的具体时机
通过查看 HashMap 的源码可以发现, 它的 put(K key, V value)方法调用了 putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)来实现元素的新增. 所以我们实际要看的是 putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)的源码.
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
- Node<K, V>[] tab;
- Node<K, V> p;
- int n, i;
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null); // 直接放在散列表上的节点, 并没有特意标识其为头节点, 其实它就是 "链表 / 红黑树. index(0)" <---------------
- else {
- Node<K, V> e;
- K k;
- if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
- e = p;
- else if (p instanceof TreeNode)
- e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
- else { // 下面的代码是探究 "链表转红黑树" 的重点:
- for (int binCount = 0;; ++binCount) {
- if ((e = p.next) == null) { // 沿着 p 节点, 找到该桶上的最后一个节点:
- p.next = newNode(hash, key, value, null); // 直接生成新节点, 链在最后一个节点的后面;
- //"binCount>= 7":p 从链表. index(0)开始, 当 binCount == 7 时, p.index == 7,newNode.index == 8;
- // 也就是说, 当链表已经有 8 个节点了, 此时再新链上第 9 个节点, 在成功添加了这个新节点之后, 立马做链表转红黑树.
- if (binCount>= TREEIFY_THRESHOLD - 1)
- treeifyBin(tab, hash); // 链表转红黑树
- break;
- }
- ......
- p = e;
- }
- }
- ......
- }
- }
- ......
- }
通过源码解析, 我们已经很清楚 HashMap 是在 "当链表已经有 8 个节点了, 此时再新链上第 9 个节点, 在成功添加了这个新节点之后, 立马做链表转红黑树".
三, 通过测试, 进一步理解链表转红黑树的具体时机
1. 先创建一个 Node 类, 它是 HashMap 的节点的一个简化:
- class Node {
- int info;
- Node next;
- public Node(int info) {
- this.info = info;
- }
- }
2. 简化 HashMap 的 put()方法, 并进行测试:
- public class A03Method_TreeifyBin {
- public static void main(String[] args) {
- A03Method_TreeifyBin treeifyBin = new A03Method_TreeifyBin();
- // 假设下面创建的所有 Node 都是要放到散列表上的同一个桶上的(即通过计算它们的哈希值定位到了同一个桶):
- Node firstNode = new Node(0);//firstNode 作为直接放在桶上的节点.
- for(int i = 1; i <10; i++) {// 已有 firstNode, 再 put 进 9 个节点
- treeifyBin.put(firstNode, new Node(i));//new 出的新节点依次链在 firstNode 后面, 形成一个链表.
- }
- }
- /**
- * 该方法截取自 HashMap.putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法中有关 "链表转红黑树的时机" 那部分代码.
- * 该方法是对 HashMap.putVal(......)源码做简化后的方法, 可以参照源码来看该方法.
- *
- * @param p : 当前节点
- * @param newNode : 要新添进去的节点
- */
- public void put(Node p, Node newNode) {
- Node e;
- for (int binCount = 0;; ++binCount) {
- if ((e = p.next) == null) {
- p.next = newNode;
- if(binCount>= 7) {
- //HashMap.putVal(......)源码中这里执行了 treeifyBin(tab, hash)方法, 将链表转为了红黑树.
- System.out.println("binCount ==" + binCount);
- System.out.println("p.next.info :" + p.next.info);
- System.out.println("p.info :" + p.info);
- System.out.println("----------------------------");
- }
- break;
- }
- p = e;
- }
- }
- }
最后的输出结果是:
- binCount == 7
- p.next.info : 8
- p.info : 7
- ----------------------------
- binCount == 8
- p.next.info : 9
- p.info : 8
- ----------------------------
从输出结果我们可以得知:
从 firstNode 后面链上 new Node(1)开始, 从输出结果可以看到, 一旦 binCount==7 就做链表转数组;
此时 "p.next = newNode;" 的 p 是 new Node(7),newNode 是 new Node(8);
也就是说: 当链表已经有 8 个元素了(firstNode 到 new Node(7)), 此时 put 进第 9 个元素(new Node(8)), 先完成第 9 个元素的 put, 然后立刻做链表转红黑树. 这个结论和第 2 点中得到的结论一致.
来源: https://www.cnblogs.com/laipimei/p/11282055.html