從零開始的 HashMap 源碼閱讀（二) 構造函數分析

0.構造函數源碼

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(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
           

第一個給的資訊多就看第一個構造函數吧

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;
        //因為table的初始化長度必須是2的次方數,是以要先将不規則的initialCapcity通過 tableSizeFor 轉化成2的次方數再乘以負載因子傳回給threshold
        this.threshold = tableSizeFor(initialCapacity);
    }

           

前面的都是一些判斷,判斷傳入參數是否合法

主要是最下面的 tableSizeFor函數,我們傳入的cap可能是不規則的,通過tableSizeFor就可以傳回最接近cap的2的次方數0.

為什麼table.length一定要是2的次方數呢?

因為節點插入到數組的下标是

index = hashcode&table.length-1,HashMap為了減少碰撞,就要将資料配置設定均勻.hashcode&table.length-1能正常工作的前提就是table.length是2的次方數

為什麼這樣能均勻分布減少碰撞呢？2的n次方實際就是1後面n個0，2的n次方-1 實際就是n個1；

例如長度為9時候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；

例如長度為8時候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；

1.tableSizeFor分析

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;
    }
           

傳入給定的一個容量,通過一頓位運算操作傳回成該數最近的較大的2的次方數

如何工作的?

比如傳入的cap為10

cap == 10

n = 10-1=9 == 1001

1001 | 0100 ⇒ 1101

1101 | 0011 ⇒ 1111

1111 | 0000 ⇒ 1111

1111 ⇒ 15

return 15+1

最後傳回了16