提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

【Java集合】HashMap的添加操作源码详解

JAVA源码集合 详解 操作 添加 HashMap
2023-09-27 14:19:52 时间

目录

1、putTreeVal()

2、root()

3、find()

4、untreeify()、treeify()、treeifyBin()总结

4.1 treeifyBin()和treeify()

4.2 untreeify()

HashMap中的putVal()添加元素方法会触发一系列的TreeNode类的方法，依次为：putTreeVal()、root()、find()。

下面我们将按照添加操作流程依次详细讲解方法源码。

调用开始位置：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    ......
    // 若p节点是红黑树，则直接在树中插入或者更新键值对
    else if (p instanceof TreeNode){
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    }
    ......
    // 插入节点后，判断是否需要链表转红黑树，
    // 链表元素数大于8才转，因为这里是从第二个节点开始的，所以 TREEIFY_THRESHOLD - 1 = 7 ，又因为binCount是从0开始的，所以用的是>=号。
    // 例如bigCount=7，表示循环了进行了7次，加上原来的那个头节点，表示该链表原先有8个节点，然后新元素又进行了尾插入，此时该链表就有9个元素了，所以此时就得树化操作
    if (binCount >= TREEIFY_THRESHOLD - 1)
        treeifyBin(tab, hash); // 树化操作
    ......
}

1、putTreeVal()

向红黑树插入 or 更新数据（键值对），遍历红黑树，如果找到与新数据key相同的节点，则直接返回该节点；如果找不到相同的key，则创建新节点并插入，然后重新平衡红黑树。

putTreeVal的两种情况：

  1. key已经存在这个红黑树中当中了，就直接放回对应的那个节点；
  2. 从红黑树的root节点开始遍历，定位到要插入的叶子节点，插入新节点；

putTreeVal除了要维护红黑树的平衡外，还需要维护节点之间的前后关系，也就是同时在维护双向链表关系。

/**
    红黑树的put操作，红黑树插入会同时维护原来的链表属性, 即原来的next属性
    @param map:当前调用该方法的对象实例，也就是当前map
    @param tab：当前map里的数组，
    @param h:新数据的key计算出来的hash，
    @param k：新数据的key，
    @param v：新数据的value 
    @return 成功插入返回null，如果找到在红黑树中有key相同的节点，则直接将该节点返回
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
    // 新数据的key的Class类型
    Class<?> kc = null;
    // 是否调用find方法进行查找，默认没调用
    boolean searched = false;
    // 查找根节点, 索引位置的头节点并不一定为红黑树的根节点，所以需要通过调用root()方法来遍历红黑树结构进而找到根节点
    // 此处的this就是调用该方法的TreeNode实例，
    TreeNode<K,V> root = (parent != null) ? root() : this;
    // 将根节点赋值给p节点，从根节点开始遍历红黑树，从内部终止遍历
    for (TreeNode<K,V> p = root;;) {
        // dir：表示向哪个子树查找，-1左，1右； p：当前节点，ph：当前树节点的hash，pk：当前树节点的key
        int dir, ph; K pk;
        // 将当前节点p的hash赋值给ph，
        // 并且新数据的hash小于当前树节点的hash，则向p的左子树查找
        if ((ph = p.hash) > h)
            // dir赋值为-1
            dir = -1;
        // 否则向p的右子树查找
        else if (ph < h)
            // dir赋值为1
            dir = 1;
        // 当前树节点的key等于新数据的key，直接返回当前节点
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        /**
         * 如果kc为null，说明当前kc还没有被赋值，需要继续执行后面的代码对kc进行赋值，因为它的后面是与运算符，如果kc已经被赋值了，说明已经执行过后面的语句了，就不用再执行后面comparableClassFor和compareComparables了
         * kc==null&&(kc = comparableClassFor(k)) == null是同一个与运算表达式，继续执行后面comparableClassFor来判断key是不是实现了comparable接口，如果返回null，说明key没有实现comparable接口，也就无法使用compareComparables来比较大小了。整个与运算表达式结果为true，也就直接进入到if分支内部了，因为它们的后面是或运算
         * 如果实现了comparable接口接口，则继续调用compareComparables来比较大小，如果返回值不为0，则说明通过compareComparables比较出了大小，将比较结果直接赋值给dir，也就不用执行if分支内部的语句来比较大小了。
         * 如果返回值为0，说明compareComparables方法也没有比较出两者的大小关系，则需要继续进入到if分支内部去用别的方法继续进行比较。
         */
        else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            // 还没有调用find方法进行查找
            if (!searched) {
                TreeNode<K,V> q, ch;
                // 改为已经调用find方法进行查找了，
                searched = true;
                // 从p节点的左节点和右节点分别调用find方法进行查找, 如果查找到目标节点则并终止循环，返回q；
                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;
            }
            // 使用定义的一套规则来比较p节点的key和新数据的key大小, 用来决定向左还是向右查找
            dir = tieBreakOrder(k, pk);// dir<0 则代表 k<pk，则向p左边查找；反之亦然
        }
        // x表示新插入元素构建出来的树节点
        // xp赋值为x的父节点，中间变量，用于下面给x的父节点赋值
        TreeNode<K,V> xp = p;
        // dir<=0则向p左边查找，否则向p右边查找，如果为null,说明已经到达了叶子节点，红黑树插入新节点都会插入到叶子结点的位置，遍历到了null则代表该位置即为新插入节点x的应该插入的位置，进入if分支内进行插入操作
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // 走进来代表已经找到x要插入的位置，只需将x放到该位置即可
            Node<K,V> xpn = xp.next;
            // 创建新的节点, 其中x的next节点为xpn, 即将x节点插入xp与xpn之间
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            // 调整x、xp、xpn之间的属性关系
            if (dir <= 0) // 如果时dir <= 0, 则代表x节点为xp的左节点
                xp.left = x;
            else // 如果时dir> 0, 则代表x节点为xp的右节点
                xp.right = x;
            // 将xp的next节点设置为x
            xp.next = x; 
            // 将x的parent和prev节点设置为xp
            x.parent = x.prev = xp; 
            // 如果xpn不为空,则将xpn的prev节点设置为x节点,与上文的x节点的next节点对应
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            // 进行红黑树的插入平衡调整，调用了balanceInsertion和moveRootToFront
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

2、root()

查找红黑树的根节点。向上层遍历，通过判断有没有父节点来找出根节点

final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
        // 当节点没有父节点的时候，该节点即为根节点
        if ((p = r.parent) == null)
            return r;
        // 当前遍历到的节点设置为其父节点，实现向上层遍历
        r = p;
    }
}

3、find()

从调用此方法的节点开始查找, 对左右子树进行递归遍历，通过hash值和key找到对应的节点。查找过程是比较hash，判断往左找还是往右找，特殊情况就是一边为空，那就只往另一边找，比较key是否相等，递归遍历直到找到相等的key时，就代表找到了。

/**
 * 从调用此方法的节点开始查找, 通过hash值和key找到对应的节点
 * 此方法是红黑树节点的查找, 红黑树是特殊的自平衡二叉查找树
 * 平衡二叉查找树的特点：左节点<根节点<右节点
 * 
 * @return 找到了返回找到的节点，没找到返回Null
 */
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    // 1.将p节点赋值为调用此方法的节点，即为红黑树根节点
    TreeNode<K,V> p = this;
    // 2.从p节点开始向下遍历
    do {
        // ph p的hash，pk p的key
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        // 3.如果传入的hash值小于p节点的hash值，则往p节点的左边遍历
        if ((ph = p.hash) > h)
            p = pl;
        // 4.如果传入的hash值大于p节点的hash值，则往p节点的右边遍历
        else if (ph < h)
            p = pr;
        // 5.如果传入的hash值和key值等于p节点的hash值和key值,则p节点为目标节点,返回p节点
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // 6.p节点的左节点为空则将向右遍历
        else if (pl == null)    
            p = pr;
        // 7.p节点的右节点为空则向左遍历
        else if (pr == null)    
            p = pl;
        // 8.如何k的hash值等于pk的hash值，但是k和pk不相等，则将继续用其他的方法对p节点与k进行比较
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) && // 8.1 kc不为空代表k实现了Comparable
                 (dir = compareComparables(kc, k, pk)) != 0)// 8.2 k<pk则dir<0, k>pk则dir>0
            // 8.3 k<pk则向左遍历(p赋值为p的左节点), 否则向右遍历
            p = (dir < 0) ? pl : pr;
        // 9.代码走到此处, 代表key所属类没有实现Comparable, 向p的右边遍历查找，继续递归调用find()
        else if ((q = pr.find(h, k, kc)) != null) 
            return q;
        // 10.代码走到此处代表上一步的向右边没找到“pr.find(h, k, kc)”为空, 因此向左遍历
        else
            p = pl;
    } while (p != null);
    // 没找到
    return null;
}

4、untreeify()、treeify()、treeifyBin()总结

上一章节讲了untreeify()和treeify()两个TreeNode类的方法，在HashMap源码讲解的文章里讲了HashMap类的treeifyBin()方法。下面将这三个方法拿到一起对比总结一下。

4.1 treeifyBin()和treeify()

在向一个HashMap中添加数值时，算法会根据已经计算过的节点数binCount来控制是否需要将链表转化为红黑树，如果着实需要，那么会将当前hash值映射的桶进行树化。在本节最开始也贴出了，插入数据时进行树化需要调用treeifyBin()方法，然后treeifyBin()方法再去调用treeify()方法。

在树化的过程中使用的这两个方法，其中，treeifyBin()是将链接的链表线索化，即为每个二叉树的节点添加前驱和后继节点，形成线索，也就是维护了双向链表的结构，并且将节点都转换成红黑树节点。在完成线索化后，算法会调用treeify函数将已经线索化的链表转化为红黑树。

除了这两个方法之外，还有replacementTreeNode()和newTreeNode()两个方法用来完成Node节点和TreeNode节点之间的相互转化。由于TreeNode没有表达next的语义，所以虽然TreeNode继承自Node，但在算法中调用replacementTreeNode()时，形参next被赋予null。在Node转向TreeNode后，next语义由left，right两个字段表达。

treeifyBin小结：

  1. 判断是否真的需要转换红黑树，如果数组长度小于MIN_TREEIFY_CAPACITY 将会对HashMap进行扩容，不会去进行树化。
  2. 如果符合转换的条件。将指定链表上的节点转换成树形节点，并且构造成双链表，为调用treeify()转换成红黑树结构做准备。

treeify小结：

该方法的主要作用就是，将链表的元素一个一个的插入到树中，构造出符合红黑树特性的结构，来将链表结构真正转换为红黑树结构。真正构建红黑树结构就是在这个方法内实现的。

4.2 untreeify()

这个方法就相对简单很多，就是将红黑树转变为链表，具体的实现就是使用红黑树节点的链表结构进行遍历，将所有的TreeNode节点都转换为Node节点，只是对节点的类型进行了转换，并没有修改红黑树和链表的结构。

相关文章：【Java集合】HashMap系列（一）——底层数据结构分析
                  【Java集合】HashMap系列（二）——底层源码分析
                  【数据结构】史上最好理解的红黑树讲解，让你彻底搞懂红黑树
                  【Java集合】HashMap的扩容操作源码详解

相关文章