jdk collection hashmap

hashMap 的实现

初始化

设置初始容量的初始化

public class HashMap<K, V> extends AbstractMap<K, V>
        implements Map<K, V>, Cloneable, Serializable {
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int MAXIMUM_CAPACITY = 1 << 30;
    final float loadFactor;
    int threshold;

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }
        // 默认是 0.75f
        this.loadFactor = loadFactor;
        // 此步骤会得到一个 2^n 的值，且比 initialCapacity 大
        // 但是是最接近 initialCapacity 的一个值
        this.threshold = tableSizeFor(initialCapacity);
    }

    static final int tableSizeFor(int cap) {
        // Integer.numberOfLeadingZeros(cap - 1); 的结果是某个数转换为2进制，高位以上 0 的个数。
        // -1 的二进制是 FFFFFFFF，无符号右移 X 位
        // 此步骤得到的结果通常是 2^n -1 的值
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
}

无参数初始化

public class HashMap<K, V> extends AbstractMap<K, V>
        implements Map<K, V>, Cloneable, Serializable {
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    final float loadFactor;

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
}

在无参数构造的时候，没有为 threshold 赋值，而是在第一次 put 时.通过计算可知，默认值是 12

public class HashMap<K, V> extends AbstractMap<K, V>
        implements Map<K, V>, Cloneable, Serializable {
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    int threshold;

    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) {
        } else if (oldThr > 0) {
        } else {               // zero initial threshold signifies using defaults
            // 初始容量是 16
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 16 * 0.75 = 12
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 12
        threshold = newThr;
    }
}

Node 数组的初始化

从下面的代码可以得出两个结论，

• table 的长度是 2 的倍数，而 threshold 的值永远是数组长度的 0.75。
• 每次扩容都是在原有容量的基础上扩大 2 倍

public class HashMap<K, V> extends AbstractMap<K, V>
        implements Map<K, V>, Cloneable, Serializable {
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    int threshold;
    transient Node<K, V>[] table;
    transient int size;

    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) {
            // 注意，此时 newCap 已经扩大了 2 倍
            if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY) {
                // 一来容量不能超过最大值，
                // 二来旧值必须超过默认值
                newThr = oldThr << 1;
            }
        } else if (oldThr > 0) {
            // 有参构造的时候，oldThr 不为 0，对应的是那个 threshold 值
            newCap = oldThr;
        } else {
            // 16
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 12
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            // 例如 newCap = oldThr = 128，那么 ft = 96
            float ft = (float) newCap * loadFactor;
            // newThr = 96
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                    (int) ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        // 初始化数据
        Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
        table = newTab;
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // 由此可知，只要 map 的 size 超过了 threshold 就会触发扩容
        if (++size > threshold)
            resize();
    }
}

扩容后的 rehash 处理

public class HashMap<K, V> extends AbstractMap<K, V>
        implements Map<K, V>, Cloneable, Serializable {
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    int threshold;
    transient Node<K, V>[] table;
    transient int size;

    final Node<K, V>[] resize() {
        Node<K, V>[] oldTab = table;
        Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];

        for (int j = 0; j < oldCap; ++j) {
            Node<K, V> e;
            if ((e = oldTab[j]) != null) {
                // 帮助 gc
                oldTab[j] = null;
                if (e.next == null) {
                    // 说明链表只有一个元素
                    // 找到在新数组中的位置，为何这么自信的 = 直接赋值，不担心碰撞？
                    // 因为数组的长度扩大的是 2 倍，因此原有的单节点链表，在新数组中也只会是单节点，高！
                    newTab[e.hash & (newCap - 1)] = e;
                } else if (e instanceof TreeNode) {
                    // 说明已经升级成了红黑树结构
                    // 简言之就是遍历树，并以次进行 rehash
                    ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                } else {
                    // 后面也不看了，就是一种优化后的 rehash 算法   
                }

            }
        }
    }
}

转换为红黑树的条件

只要单链表的长度超过了8，就会将链表转化为树结构，默认是红黑树。

public class HashMap<K, V> extends AbstractMap<K, V>
        implements Map<K, V>, Cloneable, Serializable {
    static final int TREEIFY_THRESHOLD = 8;

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        if ((p = tab[i = (n - 1) & hash]) == null) {
        } else {
            Node<K, V> e;
            K k;
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k)))) {
            } else if (p instanceof TreeNode) {
            } else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) {
                            treeifyBin(tab, hash);
                        }
                        break;
                    }
                }
            }
        }

    }
}