HashMap實現(xiàn)原理
底層：
哈希表（數(shù)組鏈表紅黑樹） JDK 1.8
兩個比較重要的參數(shù)
LOAD_Factor和Capacity
在HashMap源代碼 236 行可以看到初始 capacity 是16

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

248 行 初始的負載因子是0.75

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap的默認構造方法 475 行

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

設置默認負載因子為0.75，默認數(shù)組大小是16
什么是capactiy：
HashMap底層數(shù)組，就是這個數(shù)組大小

什么是load_factor？
當數(shù)組被占用超過 capacity*load_factor的時候
數(shù)組需要重新創(chuàng)建
初始capacity是16
load_factor是0.75
超過12 就需要重建數(shù)組

為什么重建？
數(shù)組太小，同一個數(shù)組位置會存儲太多相同hash_value的數(shù)值，影響效率

看一下對象存儲的過程（建議打開hashmap源代碼查看）
使用put方法：
調用了611行
put 方法又調用了putVal方法

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

putVal調用了Hash方法
看一下Hash方法是如何實現(xiàn)的

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

HashCode 的數(shù)值 右移16位，然后和原本的數(shù)值做了一個異或的操作
目的是什么？
增加散列度 盡可能避免不同的數(shù)值產生相同的哈希值
這里Object.hashCode 是底層C++實現(xiàn)，不過多討論

再看put方法調用的putVal的方法：（624行）

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;

putVal 里面使用了一個Node的數(shù)組， 哈希表的數(shù)據就是存在這個數(shù)組里

Node類的實現(xiàn)：

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

Node是一個鏈表節(jié)點的結構
存儲有 哈希值 key value 和next指針，指向下一個節(jié)點

回到 putVal方法（628行）
如果發(fā)現(xiàn)哈希表當前table為空或者哈希表的長度為0
調用resize()方法 創(chuàng)建一個新的數(shù)組

if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

然后
用當前的哈希值和（哈希表數(shù)組長度-1） 做&運算，得到存儲位置location i

如果數(shù)組當前位置是空
就把一個Node放進tab[i]

if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

如果當前位置不為空，
這里p是上一步獲取的原本在位置i的 元素
）

else {
      Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;

如果現(xiàn)在key的數(shù)值和之前p key的數(shù)值相同
那么把p的數(shù)值賦值給e（e 在后面有用）

            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

如果（key和p.key 不相同）
如果p是一個treeNode,（紅黑樹結構）
就把p加到紅黑樹里面

如果這個節(jié)點不是tree（說明當前位置存儲的是鏈表）
遍歷當前鏈表，
到底然后加一個Node

如果發(fā)現(xiàn)BinCount大于等于TREEIFY_THRESHOLD-1
TREEIFY_THRESHOLD默認是8
代表鏈表過長，調用treefyBin方法，把數(shù)組轉化為紅黑樹

else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }

如果在遍歷過程中發(fā)現(xiàn)了同樣的key節(jié)點,就把當前節(jié)點的數(shù)值賦給e

                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }

最后如果發(fā)現(xiàn)e的數(shù)值不是null代表有節(jié)點被替換
就把老的數(shù)值返回，然后把新的數(shù)值寫給e

            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

再看一下resize的方法
擴充算法
當前數(shù)組容量左移一位（相當于*2），擴大一倍，非常消耗性能擴充次數(shù)過多，會影響性能，表示哈希表重新散列，需要重新計算每個對象的存儲位置。我們在開發(fā)中盡量要減少擴充次數(shù)帶來的性能問題

線程不安全