摘要：當沖突的個數比較少時，使用鏈表，否則使用紅黑樹。這樣做的好處是，最壞的情況下即所有的都沖突，采用鏈表的話查找時間為而采用紅黑樹為，這也是中性能提升的奧秘，詳細的測試可以看這篇博文。

HashMap是我們最常用的集合之一，同時Java8也提升了HashMap的性能。本著學習的原則，在這探討一下HashMap。

簡單講解下HashMap的原理：HashMap基于Hash算法，我們通過put(key,value)存儲，get(key)來獲取。當傳入key時，HashMap會根據key.hashCode()計算出hash值，根據hash值將value保存在bucket里。當計算出的hash值相同時怎么辦呢，我們稱之為Hash沖突，HashMap的做法是用鏈表和紅黑樹存儲相同hash值的value。當Hash沖突的個數比較少時，使用鏈表，否則使用紅黑樹。

一圖勝千言：

我們可以在HashMap的源碼中找到這樣一句：

transient Node[] table;

很明顯，HashMap還是憑借數組實現的，輔以鏈表和紅黑樹。我們知道數組的特點：尋址容易，插入和刪除困難，而鏈表的特點是：尋址困難，插入和刪除容易，紅黑樹則對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔保。HashpMap將這三者結合在一起。

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

如果你也看過7之前的Hash算法，會發現這個版本的算法比之前的簡潔。

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

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

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

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

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry e = (Map.Entry)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

鏈表節點，存儲鍵值對，并含有一個next引用。

 static final class TreeNode extends LinkedHashMap.Entry {
        TreeNode parent;  // red-black tree links
        TreeNode left;
        TreeNode right;
        TreeNode prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node next) {
            super(hash, key, val, next);
        }

        /**
         * Returns root of tree containing this node.
         */
        final TreeNode root() {
            for (TreeNode r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }

        /**
         * Ensures that the given root is the first node of its bin.
         */
        static  void moveRootToFront(Node[] tab, TreeNode root) {
            int n;
            if (root != null && tab != null && (n = tab.length) > 0) {
                int index = (n - 1) & root.hash;
                TreeNode first = (TreeNode)tab[index];
                if (root != first) {
                    Node rn;
                    tab[index] = root;
                    TreeNode rp = root.prev;
                    if ((rn = root.next) != null)
                        ((TreeNode)rn).prev = rp;
                    if (rp != null)
                        rp.next = rn;
                    if (first != null)
                        first.prev = root;
                    root.next = first;
                    root.prev = null;
                }
                assert checkInvariants(root);
            }
        }

紅黑樹的節點

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            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;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

這是HashMap中的put函數，里面的參數boolean onlyIfAbsent,boolean evict我并不知道有什么用，因為put在調用的時候，是將這兩個參數寫死了，若知道請告知：

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

另外我們可以看到，當節點個數>= TREEIFY_THRESHOLD - 1時，HashMap將采用紅黑樹存儲。為什么這么做呢？正如我們前面提到的，當發生Hash沖突時，HashMap首先是采用鏈表將重復的值串起來，并將最后放入的值置于鏈首，java8對HashMap進行了優化。當節點個數多了之后使用紅黑樹存儲。這樣做的好處是，最壞的情況下即所有的key都Hash沖突，采用鏈表的話查找時間為O(n),而采用紅黑樹為O(logn)，這也是Java8中HashMap性能提升的奧秘，詳細的測試可以看這篇博文。

這篇文章簡單介紹了下Java8中的HashMap中的數據結構，Hash算法，內部類，簡單分析了Java8中性能提升的奧秘，由于水平原因難免會出現一些紕漏，希望各位能即時糾正。