HashMap 源码解析一、构造函数

类结构

看到HashMap 的类结构，肯定会有个疑问，问什么HashMap 继承了AbstractMap 还实现了Map 接口？
我当时也很遗憾，于是我就查了一下，结果是个乌龙。“据java集合框架的创始人Josh Bloch描述，这样的写法是一个失误；最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。来自于

构造函数

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    /**
     * 默认的负载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    int threshold;//扩容伐值
    
    final float loadFactor;//负载因子默认为 0.75
    
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
        // all other fields defaulted
    }
    
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * @param  initialCapacity 初始容量
     * @param  loadFactor      负载因子
     */
    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;
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
}
复制代码

HashMap(int initialCapacity, float loadFactor) 构造函数

前两个没什么好讲的，我们直接看第3个 HashMap(int initialCapacity, float loadFactor)
这里的重点就是 int tableSizeFor(int cap)函数。

tableSizeFor(int cap) 函数

tableSizeFor(int cap) 的作用是返回 大于等于cap 且 最接近cap 的2的幂次方的值

    static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * Returns a power of two size for the given target capacity.
     * 返回 大于等于cap 且 最接近cap 的2的幂次方的值
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
复制代码

我们分步骤解析一下这个函数：

1. >>> 无符号右移运算符，高位用0 填充。如下：

a = 1010
a >>> 1 = 0101
复制代码

2. | 如果相对应位都是 0，则结果为 0，否则为 1。如下：

a     = 1010
b     = 0011
------------
a | b = 1011
复制代码

3. |= , a |= b 等同于 a = a|b。

这时候我们就能看懂 `n |= n >>> 1`; 等同于 `n = n | n >>> 1` 
复制代码

4. int n = cap - 1; 是因为如果cap不减1，当 cap 本来就是2次幂数值，就会导致返回的结果为 cap*2 。

5. 我们带入一个值看下运行结果，假设 cap = 20

    static final int tableSizeFor(int cap) {
        System.out.println("cap = "+ Integer.toBinaryString(cap));
        int n = cap - 1;
        System.out.println("n = "+ Integer.toBinaryString(n));
        n |= n >>> 1;
        System.out.println("n1 = "+ Integer.toBinaryString(n));
        n |= n >>> 2;
        System.out.println("n2 = "+ Integer.toBinaryString(n));
        n |= n >>> 4;
        System.out.println("n4 = "+ Integer.toBinaryString(n));
        n |= n >>> 8;
        System.out.println("n8 = "+ Integer.toBinaryString(n));
        n |= n >>> 16;
        System.out.println("n16 = "+ Integer.toBinaryString(n));
        System.out.println("n+1 = "+ Integer.toBinaryString(n+1));
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    
    @Test
    public void tableSizeForTest(){
        System.out.println("tableSizeFor:"+ tableSizeFor(20));
    }
复制代码

我这里直接把tableSizeFor(int cap) 拷贝出来，然后添加了日志。结果如下：

cap = 10100
n   = 10011
n1  = 11011   (10011 | 01001)
n2  = 11111   (11011 | 01101)
n4  = 11111   (11111 | 01111)
n8  = 11111   (11111 | 01111)
n16 = 11111   (11111 | 01111)
n+1 = 100000  (11111 + 1)
tableSizeFor:32
复制代码

HashMap(Map<? extends K, ? extends V> m) 构造函数

我们来看下最后一个构造函数，参数是一个Map ,loadFactor 设置为默认的 0.75，然后putMapEntries(m, false) 函数，把参数Map 的值拷贝到构造的HashMap 中去。
接着我们看下putMapEntries(m, false) 这个函数的具体实现

putMapEntries(m, false) 函数

    /**
     * 在 putAll 和 构造函数 中被调用
     *
     * @param m the map
     * @param 构造函数调用是传 false，否则传true
     */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // 构造函数调用是 table = null
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
复制代码

可以看到，当构造函数调用putMapEntries(Map<? extends K, ? extends V> m, boolean evict) 函数时，通过参数map 的size 设置threshold ，然后调用putVal() 函数设置内容。putVal() 我们在后面讲 put 的时候再具体分析。

构造函数小结

我们看完HashMap 的构造函数，可以知道他们的主要作用就是 设置loadFactor 和 threshold。

• loadFactor 负载因子， 一般都不会设置，默认为0.75
• threshold 扩容伐值，使用 initialCapacity或者 map.size 通过tableSizeFor(int cap) 函数得到。为大于等于且最接近的2的幂次方的值