signed

QiShunwang

“诚信为本、客户至上”

HashMap源码解析(JDK1.8)

2021/6/24 19:19:16   来源:

HashMap中一些关键点的理解

主要介绍了HashMap中的几个关键参数、get()和put()方法详解、树化和逆树化、resize()以及一些追求性能而使用的技巧。

一:JDK1.8中和之前JDK版本关于HashMap最大的区别

​ JDK1.8中当HashCode冲突较为严重时,即槽位上链表长度大于8的时候会将链表变成红黑树,提高查询效率,故JDK8中HashMap的数据结构如下图所示。理想情况下,Hash函数的分布应该是均匀的,这个时候,槽位上HashCode冲突的次数服从泊松分布。正常情况下,几乎不会使用到红黑树。
HashMap-JDK8

​ HashMap中的红黑树,比普通红黑树多维护了一份双向链表,方便遍历。

二:HashMap中几个关键的参数

1:构造方法中的initialCapacity和loadFactor
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        //这里只是使用threshold暂存初始容量,具体看resize()方法
        this.threshold = tableSizeFor(initialCapacity);
    }
  • initialCapacity:HashMap第一次resize时槽位的数量(这个值会被重置成第一个比它大的二次幂的整数详情可以见tableSizeFor()方法,目的是保证槽位数一定是二次幂,这样方便快速计算HashCode对应的槽位)
  • loadFactor:负载因子,槽位中被占用loadFactor后,会进行resize,减少冲突
2:几个关键静态参数
  • DEFAULT_LOAD_FACTOR:默认的负载因子:0.75,太大冲突多,太小浪费内存
  • MAXIMUM_CAPACITY:最大槽位数为 1 << 30,最大容量是小于Integer.MAX_VALUE(2^31 - 1)的最大的2次幂
  • TREEIFY_THRESHOLD:链表->红黑树的阈值:8
  • UNTREEIFY_THRESHOLD:红黑树->链表的阈值:6
  • MIN_TREEIFY_CAPACITY:槽位上树化是,槽位数必须大于该值,否则将进行resize,而不是将这个槽位上
    的链表树化

三:HashMap中的get()和put()方法概览

1:查找:get()
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

getNode():

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //槽位数组不为null、长度大于0且给定hash值所在的槽位不为null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //比较一个对象是否equals逻辑:首先比较hash值,不等直接返回;其次比较key(先比较引用,再使用			//equals方法)
            //这个逻辑完全是出于性能考虑:比较原始类型速度快
            //槽位上第一个节点就是所要找的元素,直接返回
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                //节点是树节点,槽位上挂的是树
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //否则,槽位上挂的是链表
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        //不存在,返回null
        return null;
    }
2:插入:put()
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

putVal():

/**
* hash:keyash值
* onlyIfAbsent:key已经存在,且oldValue不为null时,不替换oldValue
* evict:LinkedHashMap中使用,用来触发LinkedHashMap中链表的更新(JDK中没有见到过false)
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
    	//槽位数组空,resize扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
    	//槽位数组上为空,直接new新的节点
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //第一个元素key和插入的元素key相等,存在该key,将e指向所存在的元素p
            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) {
                    //e指向链表的下个元素
                    if ((e = p.next) == null) {
                        //若链表的下个元素
                        p.next = newNode(hash, key, value, null);
                        //链表长度大于等于7,链表->红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //链表上的元素和插入的元素key相等,直接break跳出链表的遍历
                	//e已经指向冲突的元素
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //p = p.next
                    p = e;
                }
            }
            //map中存在所插入的key
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                //预留给LinkedHashMap的Hook
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //修改次数加1
        ++modCount;
        //超出阈值,扩容
        if (++size > threshold)
            resize();
    	//预留给LinkedHashMap的Hook
        afterNodeInsertion(evict);
        return null;
    }

四:HashMap中的红黑树

TreeNode比较节点中的key的大小,决定将节点放在当前节点的左子树上还是右子树上。比较key的大小,考虑到性能比较的优先级为:1,hash值(HashMap中的hash());2,key的引用;3,key的比较器;4,key使用Object中hashCode值

1:树化:treeifyBin()

调用处:putVal(),compute(),computeIfAbsent(),merge(),后三个是JDK1.8中新增的拓展方法

    /**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //冲突严重,但是槽位数小于64时,选择扩容,而不是树化
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            //遍历挂在槽位上的链表,将Node变为TreeNode,并维护TreeNode的双向链表
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            //树化
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

treeift():

        /**
         * Forms tree of the nodes linked from this node.
         */
        final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null;
            //从本节点开始遍历,构建红黑树(循环中的逻辑即为普通红黑树的插入逻辑)
            for (TreeNode<K,V> x = this, next; x != null; x = next) {
                next = (TreeNode<K,V>)x.next;
                //新节点x,左右孩子都是null
                x.left = x.right = null;
          		//还没有根节点,新节点x作为根节点,颜色设为黑
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                }
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    //从根节点开始遍历,将新节点x插入到红黑树上,并修复红黑树保持性质
                    for (TreeNode<K,V> p = root;;) {
                        int dir, ph;
                        K pk = p.key;
                        //比较节点间的大小,比较优先级:hash值、key类型的比较器、使用Object的hashCode()
                        //计算hash值比较
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);

                        TreeNode<K,V> xp = p;
                        //如果p的左孩子是null,说明新节点x应该成为p的左孩子
                        //否则将p的左孩子赋值给p,进入下个循环查找(到p的左子树上查找合适的节点插入)
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            //为新节点x赋父节点
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;
                            //染色、旋转保持性质,详细逻辑请参考TreeMap中的详解
                            root = balanceInsertion(root, x);
                            //新节点x插入完成,跳出循环,取下个节点插入
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);
        }
2:逆树化:untreeify(),树->链表

调用处:

  • removeTreeNode(),从树上删除元素时,树上元素太少时(2~6)
  • split(),resize时需要将树上节点按照hash值分为高位和低位,如果分开后的树元素小于等于6,则进行退化
        final Node<K,V> untreeify(HashMap<K,V> map) {
            Node<K,V> hd = null, tl = null;
            //通过TreeNode中的双向链表进行遍历
            for (Node<K,V> q = this; q != null; q = q.next) {
                //TreeNode -> Node
                Node<K,V> p = map.replacementNode(q, null);
                //处理链表指向
                if (tl == null)
                    hd = p;
                else
                    tl.next = p;
                tl = p;
            }
            return hd;
        }
3:从红黑树中查找:getTreeNode()
        final TreeNode<K,V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
        }

find():

        final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            //从自己开始查找
            TreeNode<K,V> p = this;
            do {
                int ph, dir; K pk;
                TreeNode<K,V> pl = p.left, pr = p.right, q;
        		//比较hash值
                if ((ph = p.hash) > h)
                    p = pl;
                else if (ph < h)
                    p = pr;
                //hash值一样,比较key的引用
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                //这里又做特殊判断,既然不是当前节点,那么存在哪棵子树就去哪棵子树去查询
                //毕竟通过反射、比较器等比较的代价比较大
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                //通过比较器来比较key
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                //key没有实现Comparable接口,无法通过比较器来比较,只能左右子树都去查找了
                //先查右子树,递归调用
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                else
                //走到这里,说明右子树上找不到,那么将pl赋值给p,进入下个循环到左子树上找
                    p = pl;
            } while (p != null);
            return null;
        }
4:插入元素到红黑树上:putTreeVal()

​ 插入到红黑树上和传统方法基本类似,差异在于以下两点:

  • 需要返回已存在的和key相等的节点
  • 维护TreeNode中的双向链表
	     final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
            //key的Class对象
            Class<?> kc = null;
            //是否已经遍历过左右子树
            boolean searched = false;
            TreeNode<K,V> root = (parent != null) ? root() : this;
            //从根节点开始查找合适的位置
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                //这里为何不判断p的左右子树是否为空,直接进入左右子树查找?
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                    //走到这里,说明key没有比较器或者比较器返回0
                    //如果没有遍历过当前节点的左右子树,那么遍历查找
                    if (!searched) {
                        TreeNode<K,V> q, ch;
                        //遍历当前节点的左右子树,在一次插入中仅遍历一次,因为它的节点的子树也不会存在
                        //和key相等的节点
                        searched = true;
                        if (((ch = p.left) != null &&
                             (q = ch.find(h, k, kc)) != null) ||
                            ((ch = p.right) != null &&
                             (q = ch.find(h, k, kc)) != null))
                            //如果能查询到和key相等的节点,直接返回
                            return q;
                    }
                    //这里只能通过Object的hashCode来比较大小
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    Node<K,V> xpn = xp.next;
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                    //将新节点x插入到树上
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    //将新节点x插入到双向链表中
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    //修复,将根节点移到链表头:first=tab[index]和root不相等时,将root从链表中删除,放到first前面
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }
5:从树上删除元素:removeTreeNode()

HashMap中的红黑树的删除相比传统的红黑树的删除更为复杂,主要体现在以下两点:

  • 不可以直接进行值交换
  • 需要维护TreeNode中的双向链表

复杂的原因就是TreeNode中维护了双向链表。

a)传统红黑树删除算法简介
  1. 找到待删除节点;
  2. 如果删除的节点没有子树,直接删除,如果它是黑色的,从哨兵节点开始颜色修复;
  3. 如果删除的节点只有一个子树,用它的孩子节点替换它,如果它是黑色的,从它的孩子开始执行颜色修复;
  4. 如果删除的节点有双子树,用右子树最小的节点(后继节点)替换它,并对最小节点的右节点执行颜色修复。

具体算法实现可以参考TreeMap中的deleteEntry()方法。

b)HashMap中红黑树删除
  1. 维护双向链表;
  2. 树上元素过少,退化成链表;
  3. 找到待删除节点的替换节点,并交换位置并进行颜色修复(思想和传统红黑树一样)
  4. 将根节点移到链表的头部。

具体实现如下:

  • 待删除节点和后继节点交换示意图

交换示意图

  • replacement != p示意图

Replacement

        /**
         * Removes the given node, that must be present before this call.
         * This is messier than typical red-black deletion code because we
         * cannot swap the contents of an interior node with a leaf
         * successor that is pinned by "next" pointers that are accessible
         * independently during traversal. So instead we swap the tree
         * linkages. If the current tree appears to have too few nodes,
         * the bin is converted back to a plain bin. (The test triggers
         * somewhere between 2 and 6 nodes, depending on tree structure).
         */
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {
            int n;
            if (tab == null || (n = tab.length) == 0)
                return;
            int index = (n - 1) & hash;
            //找到树的root和链表的first
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
            //待删除节点的next和prev
            TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
            
            /*
            *下面一部分是对双向链表进行维护,即将待删除节点从双向链表中断开
            */
            
            //首先处理上个节点的next指向
            //prev为null,直接将tab[index]指向当前节点的下个节点
            if (pred == null)
                tab[index] = first = succ;
            else
                //否则,上个节点的next指向下个节点
                pred.next = succ;
            //其次处理下个节点的prev指向
            //下个节点不为null则将下个节点的prev指向当前节点的prev
            if (succ != null)
                succ.prev = pred;
            //一个特殊判断,first为空,双向链表上无节点,直接返回(tab[index]在HashMap中始终是first)
            if (first == null)
                return;
            //first不是root,root指向真正的根节点(个人理解几乎不会走到这个地方,因为每次操作都会moveRootToFront的)
            if (root.parent != null)
                root = root.root();
            
            /*
            * 下面一部分是对当前树上节点数进行简单的判断,节点过少则将树退化成链表,返回
            * 根节点只有一个子树
            * 或者根节点的左孩子只有一个左子树
            */
            
            if (root == null
                || (movable //movable为true时,每次操作才会维护root使其成为双向链表的first(个人理解这里的root一定是真正的树的根节点)
                    && (root.right == null
                        || (rl = root.left) == null
                        || rl.left == null))) {
                //方法的注释中说在测试中走到这里树上的节点一般为2~6个
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            
            /*
            * 下面真正从树上删除节点(区别于传统红黑树)
            */
            //p:待删除节点
            TreeNode<K,V> p = this, pl = left, pr = right, replacement;
            //如果删除的节点有双子树,用右子树最小的节点(后继节点)替换它,并对它的右节点执行颜色修复
            if (pl != null && pr != null) {
                //s为p的后继节点
                TreeNode<K,V> s = pr, sl;
                while ((sl = s.left) != null) // find successor
                    s = sl;
                //由于是这里需要交换整个节点(通过改变引用交换),为了保持当前节点和周围节点符合红黑树性质,这里先行将节点颜色进行交换,待后面节点交换后,其实节点颜色是不变的
                //p的父节点、左右孩子,s的父节点、左右孩子
                boolean c = s.red; s.red = p.red; p.red = c; // swap colors
                TreeNode<K,V> sr = s.right;
                TreeNode<K,V> pp = p.parent;
                //p的后继节点就是pl
                if (s == pr) { // p was s's direct parent
                    //p的父节点指向s,s的右孩子指向p,即可完成节点交换
                    p.parent = s;
                    s.right = p;
                }
                else {
                    TreeNode<K,V> sp = s.parent;
                    //p的父节点指向后继节点的父节点
                    if ((p.parent = sp) != null) {
                        //后继节点是左孩子,则将后继节点的左孩子指向p
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    //后继节点的右孩子指向pr
                    if ((s.right = pr) != null)
                        //pr的父节点指向后继节点
                        pr.parent = s;
                }
                //p.left = sl(但是sl一定是null)
                p.left = null;
                //p.right指向后继节点的右孩子
                if ((p.right = sr) != null)
                    //后继节点的右孩子的父节点指向p
                    sr.parent = p;
                //后继节点的左孩子指向pl(后继节点的右孩子在上面处理过了)
                if ((s.left = pl) != null)
                    pl.parent = s;
                //处理pp
                if ((s.parent = pp) == null)
                    root = s;
                else if (p == pp.left)
                    pp.left = s;
                else
                    pp.right = s;
                //后继节点有右孩子,对其进行染色修复,否则对p进行染色修复
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            }
            //如果删除的节点只有一个子树,用它的孩子节点替换它,如果它是黑色的,从它的孩子开始执行颜色修复
            else if (pl != null)
                replacement = pl;
            else if (pr != null)
                replacement = pr;
            else
                //如果删除的节点没有子树,直接删除,如果它是黑色的,从哨兵节点开始颜色修复
                replacement = p;
            
            //replacement不是删除节点(是删除节点的孩子,p不是叶子节点,需要染色修复),将replacement移至p处,具体操作是:树指向replacement,断开指向p;断开p指向树
            if (replacement != p) {
                //replacement.parent指向pp
                TreeNode<K,V> pp = replacement.parent = p.parent;
                //pp指向replacement(断开树指向p,转而指向replacement)
                if (pp == null)
                    root = replacement;
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                //断开p指向树
                p.left = p.right = p.parent = null;
            }
		   
            //被删除的节点是黑色的才需要进行颜色修复,因为红黑树满足根节点到任意叶子节点路径上的黑色节点个数一样,如果黑色节点被删除,必然破坏红黑树的性质(平衡)
            TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

            //replacement就是p时,p就是叶子节点,删除后不需要染色
            if (replacement == p) {  // detach
                TreeNode<K,V> pp = p.parent;
                //断开p指向树
                p.parent = null;
                if (pp != null) {
                    //断开树指向p
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            //将r移到链表头
            if (movable)
                moveRootToFront(tab, r);
        }
6:旋转、染色修复算法

CLR中的标准算法实现,和TreeMap中一致,写法稍有区别。具体参考TreeMap的实现。

五:HashMap中设计比较巧妙且难理解的几个方法

1:tableSizeFor(),计算第一个比给定数大的二次幂,HashMap在resize
    /**
     * 计算第一个比给定数大的二次幂
     * 即1000 -> 1111,1010 -> 1111
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        //这是为了防止,cap已经是2的幂。如果cap已经是2的幂, 
        //又没有执行这个减1操作,则执行完后面的几条无符号右移操作之后,
        // 返回的capacity将是这个cap的2倍。
        int n = cap - 1;
        //这里无符号右移然后按位或可以将n中某位的0变成1
        n |= n >>> 1;
        n |= n >>> 2;
        //无符号右移的位数是上次的两倍,原因如下实例:1000 | 0100 = 1100
        //可以看出1位经过n |= n>>>1可以变成2位1,为了减少运算,每次右移次数
        //可以是上次的2倍
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
2:计算hash值的方法:hash()
    static final int hash(Object key) {
        int h;
        /**
        *  为什么要h ^ h >>> 16
        *  将高16位和低16位,按位异或;高16位保持不变。目的是为了使hashCode对较小的数
        *  取模更均匀,以8bit位宽的数为例:
        *  0b10100001,0b11110001,0b10010001,对16(0b00010000)取模都是1,所以这些hashCode的对象
        *  都是冲突的,
        *  那么h ^ h >>> 4之后对16取模就是11、14、8,在槽位中分布均匀,冲突少
        *  原因:异或可以看做是一种半加,即不带进位的加法,这样做可以将高位和低位的变化都
        *  加到低位上而不影响高位
        *  异或还有其他有趣的特性。
        */
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
3:resize()方法

简单resize()示意图:

resize

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        //这里计算新的槽位容量和下次resize的阈值
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            //这里处理初始容量,将临时存放在threshold的初始容量赋值给新的容量
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        //初始化新的槽位数组
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        //原槽位数组不为空,需要进行reHash,将结点放入新的槽位数组
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //槽位单个结点直接将结点指向该槽位即可
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        //槽位指向一个树
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        //槽位指向一个链表
                        //这种情况,会将链表拆成两个链表
                        Node<K,V> loHead = null, loTail = null;//低位链表头尾,该链表上的结点reHash后位置不变
                        Node<K,V> hiHead = null, hiTail = null;//高位头尾头尾,该链表上的结点reHash后位置变为oldIndex + oldCap
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //oldCap一定是2次幂,e.hash & oldCap为0的说明hashCode / oldCap 为偶数,reHash(hashCode % 2oldCap)后还会落在原位置
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                //e.hash & oldCap不为0的说明hashCode / oldCap 为奇数,reHash(hashCode % 2oldCap)后会落在原位置 + oldCap
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //将两个新链表指向新的槽位数组
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

六:TreeNode中prev的意义有多大?

​ TreeNode中有属性prev,结合从HashMap.Node中继承的next,构成了个双向链表(TreeNode直接继承的LinkedHashMap.Entry,也是比较费解)。


    /**
     * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
     * extends Node) so can be used as extension of either regular or
     * linked node.
     */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        //在删除节点时,待删除节点是通过红黑树查找到的,为了维护链表不断,所以需要维护Prev
        //以便找到待删除节点的上个节点
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

		//其他省略
     }
1:TreeNode中维护双向链表的作用
  • 迭代器:KeyIterator、ValueIterator、EntryIterator,方便访问下个元素
  • JDK1.8中的Spliterator:HashMapSpliterator,方便访问下个元素
  • 树->链表untreeify()方法不需要遍历树,直接使用next指针即可
2:在TreeNode中引入双向链表,带来的问题
  • 单个节点所需的空间开销:线性增加一点

  • 维护双向链表带来的时间复杂度:线性增加一点

  • 代码的可读性

    尤其是从树上删除节点时,不能像传统的树一样,保持树的结构,对节点的存储内容进行简单的交换。而需要对节点进行交换,即需要多步引用的交换赋值,较为复杂。具体可以参考上述对HashMap中红黑树的删除。

    可否将TreeNode中key、value、parent、left、right、next、prev直接交换,然后将被删除节点从树上断开?如此实现可读性会大大提高。