[java进阶]——HashMap的底层实现原理和源码分析，另附几个高频面试题

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable{}

public class Test {
    public static void main(String[] args) {
        HashMap<String, String> hm1 = new HashMap();
        hm1.put("张翠山", "殷素素");
        //指定默认容量
        HashMap<String, String> hm2 = new HashMap<>(16);
        //指定默认容量和加载因子
        HashMap<String, String> hm3 = new HashMap<>(16, 0.7f);
        HashMap<String, String> hm4 = new HashMap<>(hm1);
        System.out.println(hm4);
        System.out.println(hm1);
    }
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    //tab用于保存Hashmap中数组的地址
    //tab是在栈上开辟的，访存速度快，而外面的table是在堆上开辟的，访问慢
        Node<K,V>[] tab; 
    //要添加的节点p
    Node<K,V> p; 
    int n, i;
    //数组没有创建或者数组长度为0进if
        if ((tab = table) == null || (n = tab.length) == 0){
      //如果是第一次添加元素，调用resize()方法，底层会创建一个默认长度为16，加载因子为0.75的数组
      //将tab的长度赋给变量n
            n = (tab = resize()).length;
    }
      //不是第一次添加元素
      //1.计算要添加元素在数组中的索引，也就是i
      //2.判断：数组中索引处是否为null
        //如果为null 直接添加一个新的节点到tab中
        //如果不为null，走else，此时p是数组中索引处的节点，默念三遍！！！
        if ((p = tab[i = (n - 1) & hash]) == null)
      //是null添加新节点
            tab[i] = newNode(hash, key, value, null);
        else {
      //不是null
            Node<K,V> e; K k;
      //1.判断要添加的hash值与数组中索引处的节点(p)的hash值是否相同
        //相同并且key也相同 覆盖元素
        //不相同走elseif 或 else
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
        //覆盖原数组中的元素
                e = p;
            else if (p instanceof TreeNode)
        //与p的hash不同 可添加该节点
        //是红黑树结构就添加红黑树的节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
        //与p的hash不同，以p为迭代对象循环找该链表的尾节点
                for (int binCount = 0; ; ++binCount) {
          //判断p是否是尾节点
                    if ((e = p.next) == null) {
            //是尾节点，在p的后面添加新的链表节点
                        p.next = newNode(hash, key, value, null);
            //添加完后判断是否转为红黑树结构
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
          //迭代的过程中有与添加元素重复的key，break跳出，注意此时e是与添加元素重复key的节点
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
          //迭代p
                    p = e;
                }
            }
      //如果e是空 添加新元素
      //如果e不是空 覆盖元素
            if (e != null) { // existing mapping for key
        //记录老的value
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
          //覆盖
                    e.value = value;
                afterNodeAccess(e);
        //返回老的value
                return oldValue;
            }
        }
        ++modCount; //不用管
    //向数组中添加元素需要判断是否达到了扩容时机 达到就扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }