HashMap源碼分析——預設參數問題

關鍵的預設參數

//哈希表預設容量，即桶數
 	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
    //預設負載因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

	//樹型門檻值，即将桶結構轉成紅黑樹的節點門檻值
    static final int TREEIFY_THRESHOLD = 8;

	//非樹型門檻值，将桶結構轉回連結清單形式的門檻值
    static final int UNTREEIFY_THRESHOLD = 6;
	
           

為什麼初始容量是16？

  這個應該是一個經驗值吧，太小會容易頻繁擴容，太大又浪費空間。

預設負載因子為什麼是0.75？

  負載因子是擴容機制的一個路徑成本，當 哈希表的K-V鍵值對數量>目前容量×負載因子 會發生擴容。

從極端情況分析：

  1、令負載因子為1，則擴容隻在條目數>目前容量的時候，才發生擴容，雖然所有的空間都利用完了，但是發生哈希沖突變得不可避免了，是以會降低查詢的效率。

  2、當負載因子取值接近0，隻用到比較少的空間就開始擴容，之後發生哈希沖突的機率也比較小，時間效率是得到提高，但是空間使用率降低了。

  是以，在負載因子是0.75的時候，在時間和空間上取得了良好的折中。如果設定更大的值，可以提高空間的使用率，但是會降低時間效率。

為什麼設定樹型門檻值為8？

可以看源碼的開頭的一段注釋：

* Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million
           

大意是：

  1、因為樹節點的存儲空間大約是普通節點記錄的兩倍，如果一開始就使用樹節點存儲太浪費空間，是以要選擇一個合适的值才轉樹節點。當低于一定值轉回普通節點。

  2、在理想情況，随機哈希下，哈希表的桶内節點分布遵循泊松分布，當負載因子是0.75，桶中節點達到8個的機率已經低于千萬分之1了。

普通節點源碼：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        //其餘方法
}
           

樹節點源碼：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        //其餘方法
}