JDK1.8 HashMap get源码简介

心已赠人 2022-05-27 13:43 99阅读 0赞

废话不多说，上刑

public V get(Object key) {
        Node<K,V> e;
        // 如果 查询到node，返回node的value，如果没有查询到，返回null
        // hash(key)算法在put方法里面有讲
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    
    // 获取node
    final Node<K,V> getNode(int hash, Object key) {
    
        // 存放数组（table）用，临时用
        Node<K,V>[] tab;
        // first:存放数组里面的node，也就是链表的第一个节点
        // e:临时存放first的下一个节点
        Node<K,V> first, e;
        // 存放素组的长度
        int n;
        // 存放临时key
        K k;
        if ((tab = table) != null // 赋值，并判断不为null
            && (n = tab.length) > 0 // 赋值，并判断长度大于0
            && (first = tab[(n - 1) & hash]) != null) // 获取素组里面存放的第一个node，判断是否null
    
            {
    
            // 判断存放在数组的node 的hash是否和入参相等
            if (first.hash == hash && // always check first node
                // 并且 key相等
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;//返回素组中的node
    
            // 如果下一个节点不为null，并赋值e
            if ((e = first.next) != null) {
    
                // 如果是红黑色结构
                if (first instanceof TreeNode)
                    // 通过红黑数方式查询 key first为根节点
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    
                // 不是红黑树，就表示是一个普通的链表
                do {
                    // 判断hash和key是否相等
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        如果相等，返回这个node
                        return e;
                    // 一直循环到下一个节点为null，结束循环
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
    
    // 红黑树查找key
    final TreeNode<K,V> getTreeNode(int h, Object k) {
        // 如果当前节点的父节点为null，调用父节点.find，
        // 如果当前节点的没有父节点，调用root，如果
        return ((parent != null) ? root() : this).find(h, k, null);
    }
    
    // 返回父节点
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
    
    // 通过节点，查找key
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
        TreeNode<K,V> p = this;// 临时存放当前节点（入参是父节点，针对get方法）
        do {
            // ph：父节点的hash
            // dir:
            // pk：父key
            int ph, dir; K pk;
    
            // 存放父节点的左右节点
            TreeNode<K,V> pl = p.left, pr = p.right, q;
            // 如果父节点的hash值大于需要查找的key的hash
            if ((ph = p.hash) > h)
                p = pl; //父节点=左叶子节点
            else if (ph < h)
                p = pr; //父节点=右叶子节点
    
            // 如果key相等，表明找到了，返回当前节点
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
    
            // 如果左叶子节点为null,将右节点赋值个p
            else if (pl == null)
                p = pr;
    
            // 如果右叶子节点为null,将左节点赋值个p
            else if (pr == null)
                p = pl;
    
            // 如果开class不为null，验证类型是否一致
            else if ((kc != null ||
                      (kc = comparableClassFor(k)) != null) &&
                     (dir = compareComparables(kc, k, pk)) != 0)
                p = (dir < 0) ? pl : pr;
    
            // 递归循环
            else if ((q = pr.find(h, k, kc)) != null)
                return q;
    
            // 其他情况，返回左节点
            else
                p = pl;
    
            // 直到p为null结束
        } while (p != null);
    
        // 没有找到，返回null
        return null;
    }