BAT大厂面试官必问的HashMap相关面试题及部分源码分析

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

/**
     * Implements Map.put and related methods
     * @param hash key的哈希值
     * @param key key值
     * @param value 需要Put进去的value
     * @param onlyIfAbsent 如果为true,不改变已存在的值
     * @param evict 如果为false，则table 为creation 模式.
     * @return 返回之前的值, 不存在则返回nullh
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //先判断table是否为空或者长度为零
        if ((tab = table) == null || (n = tab.length) == 0)
            //调用resize方法初始化数组
            n = (tab = resize()).length;
        //计算数组下标i=(tab.length - 1) & hash
        if ((p = tab[i = (n - 1) & hash]) == null)
            //如果数组下标处元素为空，则将hash, key, value等值封装成链表后保存在此数组下标处
            tab[i] = newNode(hash, key, value, null);
        else {
            //数组下标处元素不为空
            Node<K,V> e; K k;
            //若p = tab[i = (n - 1) & hash]的hash值等于入参hash同时其key值等于入参key
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //将tab[i = (n - 1) & hash]赋值给局部变量e
                e = p;
            //若数组下标处的元素是一棵红黑树
            else if (p instanceof TreeNode)
                //调用TreeNode#putTreeVal方法并将其返回值赋值给e,putTreeVal方法后面再讲
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { //数组下标元素不同时满足其hash值等于入参hash和其key值等于入参key,
                //同时它也不是红黑树节点,此时它仍然是Node类型的节点
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) { //若p的下一个节点为空，并把p.next赋值给e
                        //封装hash, key, value为一个新的Node节点赋值给p.next
                        p.next = newNode(hash, key, value, null);
                        //若binCount大于等于TREEIFY_THRESHOLD - 1
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //调用treeifyBin方法后跳出循环
                            treeifyBin(tab, hash);
                        break;
                    }
                    //若e的hash值等于入参hash,同时e的key值等于入参key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        //跳出循环
                        break;
                    //以上两种情况都没出现时将e赋值给p
                    p = e;
                }
            }
            if (e != null) { // 若对应的key值在HashMap中存在映射值
                //将e的value值赋值给oldValue
                V oldValue = e.value;
                //若onlyIfAbsent==false或者oldValue == null
                if (!onlyIfAbsent || oldValue == null)
                    //将新值value赋值给e.value
                    e.value = value;
                //调用afterNodeAcces方法
                afterNodeAccess(e);
                //返回旧值
                return oldValue;
            }
        }
        //对应的key值在HashMap中不存在映射值，属于新增一个元素，modCount值加1
        ++modCount;
        if (++size > threshold)
            //若size+1后大于阈值threshold，则调用resize方法扩容
            resize();
        //调用afterNodeInsertion方法
        afterNodeInsertion(evict);
        //返回null
        return null;
    }

/**
 * Tree version of putVal.
 */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    //若当前TreeNode的父节点不为null则调用root()方法获得node节点，
    //否则当前TreeNode即为root节点
    TreeNode<K,V> root = (parent != null) ? root() : this;
    //从红黑树的root节点开始遍历
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        //若p节点的hash值大于入参hash值h则dir赋值为-1
        if ((ph = p.hash) > h)
            dir = -1;
        //若p节点的hash值小于入参hash值h则dir赋值为1
        else if (ph < h)
            dir = 1;
        //p.key赋值给pk
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            //若满足(pk = p.key) == k或者k != null && k.equals(pk)
            //则返回p节点
            return p;
        //若满足kc为null同时调用comparableClassFor(k)方法的返回值赋给kc后的值也为null
        //或者调用compareComparables(kc, k, pk)方法后的返回值赋值给dir后等于0
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                //若searched==false
                TreeNode<K,V> q, ch;
                searched = true;
                //p.left或p.right赋值给ch后不为null,同时满足调用ch.find(h, k, kc)方法后的
                //返回值赋值给q后也不为null则返回q节点
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            //调用tieBreakOrder(k, pk)方法的返回值赋值给dir
            dir = tieBreakOrder(k, pk);
        }
        //定义红黑树节点xp，并将p赋值给xp
        TreeNode<K,V> xp = p;
        //若dir <= 0则将p.left赋值给p,否则将p.right赋值给p,以进行下一次遍历
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            //p节点为null走以下逻辑
            //定义xpn节点，并将xp.next节点赋值给xpn
            Node<K,V> xpn = xp.next;
            //定义x节点为调用map.newTreeNode(h, k, v, xpn)方法后的返回值
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            //若dir<=0 则将x节点赋值给xp的左孩子节点，否则将x节点赋值给xp的右孩子节点
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            //将x节点赋值给xp的next节点
            xp.next = x;
            //将xp节点同时赋值给x的prev节点和parent节点
            x.parent = x.prev = xp;
            if (xpn != null)
                //若xpn节点不为null则将x节点赋值给xpn的prev节点
                ((TreeNode<K,V>)xpn).prev = x;
            //确保root节点是根节点,里面调用了插入节点后的平衡红黑树方法balanceInsertion(root, x)
            moveRootToFront(tab, balanceInsertion(root, x));
            //返回null
            return  null;
        }
    }
}