Implementation Notes

• HashMap有兩個(gè)參數(shù)，initialCapacity(默認(rèn)16），loadFactor默認(rèn)0.75，當(dāng)容器內(nèi)節(jié)點(diǎn)數(shù)量多于initialCapacity*loadFactor，自動(dòng)擴(kuò)充
• loadFactor越大，時(shí)間（puth和get的時(shí)間)成本越高，越小，空間成本越高
• 一般情況下，內(nèi)部存儲(chǔ)的是哈希表，當(dāng)內(nèi)容過大時(shí)，轉(zhuǎn)變?yōu)門reeNode容器，TreeNode容器內(nèi)部類似TreeMap的結(jié)構(gòu)，HashMap的方法大部分不區(qū)分，只在TreeNode有額外實(shí)現(xiàn)時(shí)被調(diào)用（通過instrance of TreeNode)方法，使用TreeNode容器是為了在數(shù)據(jù)過多時(shí)能夠快速查找，然而因?yàn)榇蟛糠諱ap內(nèi)部元素沒有達(dá)到需要Tree Bin(樹狀容器）存儲(chǔ)的要求（默認(rèn)64個(gè)元素），所以checking for existence of tree bins may be delayed in the course of table methods.
• 樹形態(tài)根據(jù)key的哈希碼排序，但是當(dāng)類實(shí)現(xiàn)了Comparable接口時(shí)，類的compareTo方法被調(diào)用來排序，在多個(gè)實(shí)例返回同樣的hashCode的情況下，通過實(shí)現(xiàn)compareTo方法來提高效率
• TreeNode大小大概是普通Node的兩倍，因此需要一個(gè)閾值來控制它的啟用

常量

• DEFAULT_INITIAL_CAPACITY 初始化容量，16
• MAXIMUM_CAPACITY 最大容量，2的30次方
• DEFAULT_LOAD_FACTOR 負(fù)載比例，0.75
• TREEIFY_THRESHOLD 樹狀閾值，HashMap相同hash的默認(rèn)放到同一個(gè)節(jié)點(diǎn)并next鏈時(shí)穿起來，但當(dāng)鏈長>=TREEIFY_THRESHOLD時(shí)，需將鏈變?yōu)闃錉钜蕴嵘L問效率
• UNTREEIFY_THRESHOLD （樹狀轉(zhuǎn)數(shù)組的閾值，6）
• MIN_TREEIFY_CAPACITY 最小轉(zhuǎn)樹狀閾值，64

內(nèi)部靜態(tài)Node類

• 內(nèi)部存儲(chǔ)final hash,final key,value,next四個(gè)變量
• hashCode方法返回Objects.hashCode(key) ^ Objects.hashCode(value)

public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

• equals方法要求key和value對(duì)equals方法都成立

方法

1.hash方法

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

計(jì)算key的hash，結(jié)尾是key的hashCode方法返回值（int型）的高16位拼接高16位與低16位按位異或的結(jié)果
這么做的原因是:table中計(jì)算key對(duì)應(yīng)存儲(chǔ)位置的時(shí)候，使用的是(capacity-1)&hash，當(dāng)n=16時(shí)，相當(dāng)于16&hash,也就是，000000000000000001111&hash,也就是前28位確認(rèn)為0，hash的后四位決定是否碰撞，對(duì)于只在高位有區(qū)別的key，是大概率會(huì)碰撞的，因此將高16位spread到低位去，可以在某些場景減少碰撞，下面是驗(yàn)證：

public static void main(String[] args) {
        Float f1 = 11111.0f;
        Float f2 = 111111.0f;
        int capacity = 16;
        System.out.println("f1的二進(jìn)制："+Integer.toBinaryString(f1.hashCode()));
        System.out.println("f2的二進(jìn)制："+Integer.toBinaryString(f2.hashCode()));
        System.out.println("HashMap630行，位置計(jì)算方式為(n - 1) & hash，假設(shè)當(dāng)前容量為16\n若不進(jìn)行spread，則：");
        int index1 = (capacity-1)&f1.hashCode();
        int index2 = (capacity-1)&f2.hashCode();
        System.out.println("位置1為:"+index1);
        System.out.println("位置2為:"+index2);
        System.out.println("發(fā)生碰撞\n若進(jìn)行spread:");
        index1 = (capacity-1)&spreadHash(f1.hashCode());
        index2 = (capacity-1)&spreadHash(f2.hashCode());
        System.out.println("位置1為:"+index1);
        System.out.println("位置2為:"+index2);
        System.out.println("不發(fā)生碰撞");
    }

    /**
     * 按hashMap的方法，計(jì)算spread后的hash
     * @param hash
     * @return
     */
    static  int spreadHash(int hash){
        return hash ^ (hash >>> 16);
    }

f1的二進(jìn)制：1000110001011011001110000000000
f2的二進(jìn)制：1000111110110010000001110000000
根據(jù)HashMap源碼630行，位置計(jì)算方式為(n - 1) & hash，假設(shè)當(dāng)前容量為16
若不進(jìn)行spread，則：
位置1為:0
位置2為:0
發(fā)生碰撞
若進(jìn)行spread:
位置1為:13
位置2為:9
不發(fā)生碰撞

為什么是^不是|或者&，驗(yàn)證可得按&是不好的，比如上面例子，按位與的話，還是會(huì)碰撞（結(jié)果都是0），^和|的運(yùn)算結(jié)果一致，待探究

2.comparableClassFor方法：判斷是否實(shí)現(xiàn)Comparable接口

static Class<?> comparableClassFor(Object x)

• 因?yàn)镾tring類型的key最多，且實(shí)現(xiàn)了Comparable接口，所以入?yún)镾tring類的直接返回String.class，
• 判斷類實(shí)現(xiàn)Comparable接口，且泛型實(shí)際類型為自己，則返回
• 否則返回null

3.compareComparables方法：返回兩個(gè)Comparable對(duì)象的比較值

static int compareComparables(Class<?> kc, Object k, Object x)

• kc:實(shí)現(xiàn)了Comparable接口的實(shí)體類
• k：對(duì)象1 c:對(duì)象2
• 通過調(diào)用時(shí)保證類型正確
• x為空或者不是kc類型時(shí)返回空，否則返回k.compareTo(x)

4.tableSizeFor：HashMap的方法，計(jì)算目標(biāo)容量對(duì)應(yīng)的2的次方數(shù)容量

static final int tableSizeFor(int cap)

內(nèi)部變量

1.transient Node<K,V>[] table;

核心存儲(chǔ)變量，隨需要resize，初始化時(shí)，容量大小是2的次方

2.transient Set<Map.Entry<K,V>> entrySet;

保存緩存的entrySet

3.transient int size;

存儲(chǔ)當(dāng)前map的大小

4.transient int modCount;

存儲(chǔ)當(dāng)前map發(fā)生Structural modifications的次數(shù)，用于在迭代時(shí)快速失?。╢ail-fast)

5.int threshold;

下一次resize的閾值，比如當(dāng)前threshold為16，當(dāng)前要放17個(gè)元素進(jìn)去，則需要resize

6.final float loadFactor;

負(fù)載因子