Java集合类

//数组
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;
}
//红黑树入口，链表长度 > 8 转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD = 8
        treeifyBin(tab, hash);

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

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        if ((tab = table) == null || (n = tab.length) == 0)
			    n = (tab = resize()).length;
		...
		if (++size > threshold)
			resize();
		...
	}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果map还是空的，则先开始初始化，table是map中用于存放索引的表
    if ((tab = table) == null || (n = tab.length) == 0) {
        n = (tab = resize()).length;
    }
    // 使用hash与数组长度减一的值进行异或得到分散的数组下标，预示着按照计算现在的
    // key会存放到这个位置上，如果这个位置上没有值，那么直接新建k-v节点存放
    // 其中长度n是一个2的幂次数
    if ((p = tab[i = (n - 1) & hash]) == null) {
        tab[i] = newNode(hash, key, value, null);
    }
    // 如果走到else这一步，说明key索引到的数组位置上已经存在内容，即出现了碰撞
    // 这个时候需要更为复杂处理碰撞的方式来处理，如链表和树
    else {
        Node<K,V> e; K k;
        // 其中p已经在上面通过计算索引找到了，即发生碰撞那一个节点
        // 比较，如果该节点的hash和当前的hash相等，而且key也相等或者
        // 在key不等于null的情况下key的内容也相等，则说明两个key是
        // 一样的，则将当前节点p用临时节点e保存
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k)))) {
            e = p;
        }
        // 如果当前节点p是（红黑）树类型的节点，则需要特殊处理
        // 如果是树，则说明碰撞已经开始用树来处理，后续的数据结构都是树而非
        // 列表了
        else if (p instanceof TreeNode) {
            // 其中this表示当前HashMap, tab为map中的数组
            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);
                    // TREEIFY_THRESHOLD = 8
                    // 从0开始的，如果到了7则说明满8了，这个时候就需要转
                    // 重新确定是否是扩容还是转用红黑树了
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到了碰撞节点中，key完全相等的节点，则用新节点替换老节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 此时的e是保存的被碰撞的那个节点，即老节点
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent是方法的调用参数，表示是否替换已存在的值，
            // 在默认的put方法中这个值是false，所以这里会用新值替换旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // Callbacks to allow LinkedHashMap post-actions
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // map变更性操作计数器
    // 比如map结构化的变更像内容增减或者rehash，这将直接导致外部map的并发
    // 迭代引起fail-fast问题，该值就是比较的基础
    ++modCount;
    // size即map中包括k-v数量的多少
    // 当map中的内容大小已经触及到扩容阈值时，则需要扩容了
    if (++size > threshold)
        resize();
    // Callbacks to allow LinkedHashMap post-actions
    afterNodeInsertion(evict);
    return null;
}

/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // MIN_TREEIFY_CAPACITY = 64
    // 如果当前map的数组为空，或者数组长度还小于64，则选择扩充数组长度
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
        // 扩充数组长度涉及到原内容的重新散列再存储
        resize();
    }
    // 如果执行else if则说明数组长度已经大于64了，这个时候就使用了
    // 红黑树来处理
    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)
            // table表从此节点链接成树
            hd.treeify(tab);
    }
}

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
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) {
        // MAXIMUM_CAPACITY = 1 << 30 = 1073741824
        // Integer.MAX_VALUE = (1 << 31) - 1 = 2147483647
        // 如果已经到了最大容量了，那么就调整扩容的threshold阈值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // DEFAULT_INITIAL_CAPACITY = 1 << 4
        // 否则的话，如果将目前的容量扩充2倍还在允许范围之内，则将容量
        // 扩充为原来的两倍，并且阈值也为原来的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 如果原始（或者初始）容量不大于0，且之前的阈值大于0，则将容量初始化为
    // 之前阈值的大小
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 执行这里的方法说明，初始参数中容量大小和阈值都不大于0，那么就用
        // map中的缺省值
        // DEFAULT_INITIAL_CAPACITY = 1 << 4 = 16
        // DEFAULT_LOAD_FACTOR = 0.75f
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新的阈值没有重新计算，那么先用加载因子计算出值
    // 如果新的容量大小和阈值大小都未超过限定值，则计算出的值可用，否则
    // 阈值就限定为容量真正允许的上限即Integer.MAX_VALUE
    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已经是扩容好的新table了
    // 老的table存在了oldTab中
    table = newTab;
    // 以下就是一个重新散列存储的过程了
    // 将老的tab中的node，按照key重新散列得到新得存储地址来存储，
    // 以此来完成扩充
    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)
                    ((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;
}