HashMap源码解析（JDK8）

粗略概述

• HashMap 基于 Hash 算法实现，通过 put(key,value) 存储，get(key) 来获取 value
• 当传入 key 时，HashMap 会根据 key，调用 hash(Object key) 方法，计算出 hash 值，根据 hash 值将 “value” 保存在 “Node 对象”里，Node 对象保存在“数组”里
• 当计算出的 hash 值相同时，称之为 hash 冲突，HashMap 的做法是用链表和红黑树存储相同 hash 值的 value
• 当 hash 冲突的个数：小于等于 8 使用链表；大于 8 且 tab length 大于等于 64 时，使用红黑树解决链表查询慢的问题

链表节点Node

    这是一个静态内部类，用来存取value

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;// 哈希值
        final K key;// key
        V value;// value
        Node<K,V> next;// 链表后置节点

        // 构造初始化
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        // 每一个节点的hash值，是将key的hashCode 和 value的hashCode 亦或得到的。
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        // 设置新的value 同时返回旧value
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        // 重写equals()，也必须重写hashCode()
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

构造函数

    注意一下数组类型成员变量哈希桶table，存放链表。

    // 最大容量 2的30次方
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认的加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 哈希桶，存放链表。 长度是2的N次方，或者初始化时为0.
    transient Node<K,V>[] table;

    // 加载因子，用于计算哈希表元素数量的阈值。  threshold = 哈希桶.length * loadFactor;
    final float loadFactor;
    // 哈希表内元素数量的阈值，当哈希表内元素数量超过阈值时，会发生扩容resize()。
    int threshold;

    public HashMap() {
        // 默认构造函数，赋值加载因子为默认的0.75f
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    public HashMap(int initialCapacity) {
        // 指定初始化容量的构造函数
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    // 同时指定初始化容量 以及 加载因子， 用的很少，一般不会修改loadFactor
    public HashMap(int initialCapacity, float loadFactor) {
        // 边界处理
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 初始容量最大不能超过2的30次方
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 显然加载因子不能为负数
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        // 设置阈值为  >=初始化容量的 2的n次方的值
        this.threshold = tableSizeFor(initialCapacity);
    }
    // 新建一个哈希表，同时将另一个map m 里的所有元素加入表中
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

put核心逻辑

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // tab存放 当前的哈希桶， p用作临时链表节点
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果当前哈希表是空的，代表是初始化( || 只要满足第一个条件，后面的条件就不再判断，)
        // 注意这里的 成员变量table 赋值给了临时变量 tab
        if ((tab = table) == null || (n = tab.length) == 0)
            // 那么直接去扩容哈希表，并且将扩容后的哈希桶长度赋值给n
            n = (tab = resize()).length;
        // 如果当前index的节点是空的，表示没有发生哈希碰撞。 直接构建一个新节点Node，挂载在index处即可。
        // index 是利用 哈希值 & 哈希桶的长度-1，替代模运算。n在上面if中赋值了
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {// 否则 发生了哈希冲突。
            // e
            Node<K,V> e; K k;
            // 如果哈希值相等，key也相等，则覆盖value
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;// 将当前节点引用赋值给e
            else if (p instanceof TreeNode)// p为红黑树类型
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {// 可能不是覆盖操作，则插入一个普通链表节点
                // 遍历链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {// 遍历到尾部，追加新节点到尾部
                        p.next = newNode(hash, key, value, null);
                        // 如果追加节点后，链表数量>=8，则转化为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果找到了要覆盖的节点
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e; // 更新p便于指向下一个节点
                }
            }
            // 如果e不是null，说明有需要覆盖的节点，
            if (e != null) { // existing mapping for key
                // 则覆盖节点值，并返回原oldValue
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 这是一个空实现的函数，用作LinkedHashMap重写使用。
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null。

        // 修改modCount
        ++modCount;
        // 更新size，并判断是否需要扩容。
        if (++size > threshold)
            resize();
        // 这是一个空实现的函数，用作LinkedHashMap重写使用。
        afterNodeInsertion(evict);
        return null;
    }

创建一个链表节点，存放了value

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

扩容逻辑

    final Node<K,V>[] resize() {
        // oldTab 为当前表的哈希桶
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;// 当前哈希桶的容量 length
        int oldThr = threshold; // 当前的阈值
        int newCap, newThr = 0; // 初始化新的容量和阈值为0
        if (oldCap > 0) {// 如果当前容量大于0
            if (oldCap >= MAXIMUM_CAPACITY) {// 如果当前容量已经到达上限
                threshold = Integer.MAX_VALUE;// 则设置阈值是2的31次方-1
                return oldTab;// 同时返回当前的哈希桶，不再扩容
            }// 否则新的容量为旧的容量的两倍。
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)// 如果旧的容量大于等于默认初始容量16
                // 那么新的阈值也等于旧的阈值的两倍
                newThr = oldThr << 1; // double threshold
        }// 如果当前表是空的，但是有阈值。代表是初始化时指定了容量、阈值的情况
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;// 那么新表的容量就等于旧的阈值
        else {               // zero initial threshold signifies using defaults
            // 如果当前表是空的，而且也没有阈值。代表是初始化时没有任何容量/阈值参数的情况
            newCap = DEFAULT_INITIAL_CAPACITY;// 此时新表的容量为默认的容量 16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 新的阈值为默认容量16 * 默认加载因子0.75f = 12
        }
        if (newThr == 0) {// 如果新的阈值是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;// 更新哈希桶引用
        // 如果以前的哈希桶中有元素
        // 下面开始将当前哈希桶中的所有节点转移到新的哈希桶中
        if (oldTab != null) {
            // 遍历老的哈希桶
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;// 取出当前的节点 e
                // 如果当前桶中有元素,则将链表赋值给e
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;// 将原哈希桶置空以便GC
                    if (e.next == null)// 如果当前链表中就一个元素，（没有发生哈希碰撞）
                        // 直接将这个元素放置在新的哈希桶里。
                        // 注意这里取下标 是用 哈希值 与 桶的长度-1 。 由于桶的长度是2的n次方，这么做其实是等于 一个模运算。但是效率更高
                        newTab[e.hash & (newCap - 1)] = e;
                        // 如果发生过哈希碰撞 ,而且是节点数超过8个，转化成了红黑树（暂且不谈 避免过于复杂， 后续专门研究一下红黑树）
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。
                    else { // preserve order
                        // 因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位， 或者扩容后的下标，即high位。 high位=  low位+原哈希桶容量
                        // 低位链表的头结点、尾节点
                        Node<K,V> loHead = null, loTail = null;
                        // 高位链表的头节点、尾节点
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;// 临时节点 存放e的下一个节点
                        do {
                            next = e.next;// 这里又是一个利用位运算 代替常规运算的高效点： 利用哈希值 与 旧的容量，可以得到哈希值去模后，是大于等于oldCap还是小于oldCap，等于0代表小于oldCap，应该存放在低位，否则存放在高位
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;// 给头尾节点指针赋值
                                else
                                    loTail.next = e;
                                loTail = e;
                            }// 高位也是相同的逻辑
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }// 循环直到链表结束
                        } while ((e = next) != null);
                        // 将低位链表存放在原index处，
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 将高位链表存放在新index处
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }