Java容器HashMap源码分析

transient Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {  
    final int hash;  
    final K key;  
    V 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; }  
  
    public final int hashCode() {  
        return Objects.hashCode(key) ^ Objects.hashCode(value);  
    }  
  
    public final V setValue(V newValue) {  
        V oldValue = value;  
        value = newValue;  
        return oldValue;  
    }  
  
    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;  
    }  
}

static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;

final void treeifyBin(Node<K,V>[] tab, int hash) {  
    int n, index; Node<K,V> e;  
    // 容器大小小于转化限制时，不转化红黑树，而是先扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  
        resize();  
    else if ((e = tab[index = (n - 1) & hash]) != null) {  
        TreeNode<K,V> hd = null, tl = null;  
        do {  
            TreeNode<K,V> p = replacementTreeNode(e, null);  
            if (tl == null)  
                hd = p;  
            else {  
                p.prev = tl;  
                tl.next = p;  
            }  
            tl = p;  
        } while ((e = e.next) != null);  
        if ((tab[index] = hd) != null)  
            hd.treeify(tab);  
    }  
}

static final int UNTREEIFY_THRESHOLD = 6;

// 指定默认容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

public HashMap(int initialCapacity, float loadFactor) {  
    // 对指定容量的非法值和特殊值的处理
    if (initialCapacity < 0)  
        throw new IllegalArgumentException("Illegal initial capacity: " +  
                                           initialCapacity);  
    if (initialCapacity > MAXIMUM_CAPACITY)  
        initialCapacity = MAXIMUM_CAPACITY;  
    if (loadFactor <= 0 || Float.isNaN(loadFactor))  
        throw new IllegalArgumentException("Illegal load factor: " +  
                                           loadFactor);  
    this.loadFactor = loadFactor;
    // 求出满足条件的容量大小，容量大小放在threshold属性
    this.threshold = tableSizeFor(initialCapacity);  
}

static final int tableSizeFor(int cap) {
    // 将指定容量减1后，把最高位的1之后的所有低位全部置为1
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 处理特殊值，正常值则加1
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

static final int MAXIMUM_CAPACITY = 1 << 30;

static final float DEFAULT_LOAD_FACTOR = 0.75f;

final Node<K,V>[] resize() {  
    Node<K,V>[] oldTab = table;  
    int oldCap = (oldTab == null) ? 0 : oldTab.length;  
    int oldThr = threshold;  
    int newCap, newThr = 0;  
    if (oldCap > 0) {  
        if (oldCap >= MAXIMUM_CAPACITY) {  
            threshold = Integer.MAX_VALUE;  
            return oldTab;  
        }
        // 常规情况下扩容，容量大小与扩容阈值都乘以2  
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&  
                 oldCap >= DEFAULT_INITIAL_CAPACITY)  
            newThr = oldThr << 1; // double threshold  
    }  
    else if (oldThr > 0) // initial capacity was placed in threshold  
        // 数组未初始化或未有元素，初始化HashMap时容量大小已指定并放置在threshold，容量大小取threshold值
        newCap = oldThr;  
    else {               // zero initial threshold signifies using defaults  
        // 数组未初始化或未有元素，初始化HashMap时未指定容量大小，按默认值设置容量大小和扩容阈值
        newCap = DEFAULT_INITIAL_CAPACITY;  
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);  
    }  
    if (newThr == 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;  
            if ((e = oldTab[j]) != null) {  
                oldTab[j] = null;  
                if (e.next == null)  
                    // 链表只有一个元素，通过新计算的位置转移链表
                    newTab[e.hash & (newCap - 1)] = e;  
                else if (e instanceof TreeNode)
                    // 红黑树处理
                    // split方法中，假如红黑树节点数量减少到小于等于限制值，则红黑树将转化为链表  
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
                else { // preserve order  
                    Node<K,V> loHead = null, loTail = null;  
                    Node<K,V> hiHead = null, hiTail = null;  
                    Node<K,V> next;  
                    do {  
                        // 遍历原链表中的每一个元素，通过扩容哈希求模优化切分成两个链表，再放到对应的新位置上
                        next = e.next;  
                        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);  
                    if (loTail != null) {  
                        loTail.next = null;  
                        newTab[j] = loHead;  
                    }  
                    if (hiTail != null) {  
                        hiTail.next = null;  
                        newTab[j + oldCap] = hiHead;  
                    }  
                }  
            }  
        }  
    }  
    return newTab;  
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
               boolean evict) {  
    Node<K,V>[] tab; Node<K,V> p; int n, i;  
    if ((tab = table) == null || (n = tab.length) == 0)  
        // 数组未初始化或未有元素，调用resize，初始化数组
        n = (tab = resize()).length;  
    // 哈希求模优化，求模转化为按位与
    if ((p = tab[i = (n - 1) & hash]) == null) 
        // 链表第一个元素，直接放进数据即可 
        tab[i] = newNode(hash, key, value, null);  
    else {  
        Node<K,V> e; K k;  
        if (p.hash == hash &&  
            ((k = p.key) == key || (key != null && key.equals(k))))  
            // 链表已有元素，第一个元素是相同的key，取出原来的Node
            e = p;  
        else if (p instanceof TreeNode)  
            // 链表已转为红黑树，将值存放到红黑树中，若有旧值则返回
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  
        else { 
            // 链表已有元素，第一个元素不是相同的key，从链表的第二个元素开始遍历
            for (int binCount = 0; ; ++binCount) {  
                if ((e = p.next) == null) {  
                    // 在链表中找不到相同key的元素，链表尾加上新的元素
                    p.next = newNode(hash, key, value, null);  
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                        // 加入新元素后，链表元素个数超过TREEIFY_THRESHOLD限制值，转化为红黑树
                        treeifyBin(tab, hash);  
                    break;                }  
                if (e.hash == hash &&  
                    ((k = e.key) == key || (key != null && key.equals(k))))  
                    // 在链表中找到相同key的元素，此时e指向旧值
                    break; 
                // 遍历链表移动指针     
                p = e;  
            }  
        }  
        if (e != null) { // existing mapping for key  
            // 存在旧值，e不为空
            V oldValue = e.value;  
            if (!onlyIfAbsent || oldValue == null)  
                // 替换新值
                e.value = value;  
            afterNodeAccess(e);  
            return oldValue;  
        }  
    }  
    ++modCount;  
    if (++size > threshold)  
        // 放入元素后，元素总个数大于扩容阈值，调用resize
        resize();  
    afterNodeInsertion(evict);  
    return null;
}

final Node<K,V> getNode(int hash, Object key) {  
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;  
    if ((tab = table) != null && (n = tab.length) > 0 &&  
        (first = tab[(n - 1) & hash]) != null) {  
        // 通过哈希求模获取元素位置，该位置的链表不为空
        if (first.hash == hash && // always check first node  
            ((k = first.key) == key || (key != null && key.equals(k))))  
            // 要查找的元素的key与链表中的第一个元素的key相等，查找成功
            return first;  
        if ((e = first.next) != null) {  
            if (first instanceof TreeNode)  
                // 红黑树查找
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);  
            do {  
                // 遍历链表中的所有元素,找到匹配的元素则查找成功
                if (e.hash == hash &&  
                    ((k = e.key) == key || (key != null && key.equals(k))))  
                    return e;  
            } while ((e = e.next) != null);  
        }  
    }  
    return null;  
}

static final int hash(Object key) {  
    int h;
    // 将原始key的哈希值与自身逻辑右移16位的结果按位异或
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);  
}