天天看點

為什麼HashMap的加載因子是0.75

一、為什麼HashMap需要加載因子?

HashMap的底層是哈希表,是存儲鍵值對的結構類型,它需要通過一定的計算才可以确定資料在哈希表中的存儲位置:

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

// AbstractMap
public int hashCode() {
  int h = 0;
  Iterator<Entry<K, V>> i = entrySet().iterator();
  while (i.hasNext()) {
    h += i.next().hashCode();
  }
  return h;
}           

一般的資料結構,不是查詢快就是插入快,HashMap就是一個插入慢、查詢快的資料結構。

但這種資料結構容易産生兩種問題:

(1)如果空間使用率高,那麼經過的雜湊演算法計算存儲位置的時候,會發現很多存儲位置已經有資料了(哈希沖突);

(2)如果為了避免發生哈希沖突,增大數組容量,就會導緻空間使用率不高。

而加載因子就是表示Hash表中元素的填滿程度。

加載因子 = 填入表中的元素個數 / 散清單的長度

加載因子越大,填滿的元素越多,空間使用率越高,但發生沖突的機會變大了;

加載因子越小,填滿的元素越少,沖突發生的機會減小,但浪費了更多的空間,而且還會提高擴容rehash操作的次數。

沖突的機會越大,說明需要查找的資料還需要通過另一個途徑查找,這樣查找的成本就越高。是以,必須在“沖突的機會”與“空間使用率”之間,尋找一種平衡與折衷。

是以我們也能知道,影響查找效率的因素主要有這幾種:

(1)散列函數是否可以将哈希表中的資料均勻地散列?

(2)怎麼處理沖突?

(3)哈希表的加載因子怎麼選擇?

二、解決沖突有什麼方法?

1. 開放定址法

Hi = (H(key) + di) MOD m,其中i = 1, 2, …, k (k <= m-1)

H(key)為哈希函數,m為哈希表表長,di為增量序列,i為已發生沖突的次數。

其中,開放定址法根據步長不同可以分為3種:

(1)線性探查法(Linear Probing):di = 1, 2, 3, …, m-1

簡單地說,就是以目前沖突位置為起點,步長為1循環查找,直到找到一個空的位置,如果循環完了都占不到位置,就說明容器已經滿了。舉個例子,就像你在飯點去街上吃飯,挨家去看是否有位置一樣。

(2)平方探測法(Quadratic Probing):di = ±1^2, ±2^2,±3^2,…,±k^2(k ≤ m/2)

相對于線性探查法,這就相當于的步長為di = i2來循環查找,直到找到空的位置。以上面那個例子來看,現在你不是挨家去看有沒有位置了,而是拿手機算去第i2家店,然後去問這家店有沒有位置。

(3)僞随機探測法:di = 僞随機數序列

這個就是取随機數來作為步長。還是用上面的例子,這次就是完全按心情去選一家店問有沒有位置了。

但開放定址法有這些缺點:

(1)這種方法建立起來的哈希表,當沖突多的時候資料容易堆集在一起,這時候對查找不友好;

(2)删除結點的時候不能簡單将結點的空間置空,否則将截斷在它填入散清單之後的同義詞結點查找路徑。是以如果要删除結點,隻能在被删結點上添加删除标記,而不能真正删除結點;

(3)如果哈希表的空間已經滿了,還需要建立一個溢出表,來存入多出來的元素。

2. 再哈希法

Hi = RHi(key),其中i = 1, 2, …, k

RHi(key)函數是不同于H(key)的哈希函數,用于同義詞發生位址沖突時,計算出另一個哈希函數位址,直到不發生沖突位置。這種方法不容易産生堆集,但是會增加計算時間。

是以再哈希法的缺點是:增加了計算時間。

3. 建立一個公共溢出區

假設哈希函數的值域為[0, m-1],設向量HashTable[0, …, m-1]為基本表,每個分量存放一個記錄,另外還設定了向量OverTable[0, …, v]為溢出表。基本表中存儲的是關鍵字的記錄,一旦發生沖突,不管他們哈希函數得到的哈希位址是什麼,都填入溢出表。

但這個方法的缺點在于:查找沖突資料的時候,需要周遊溢出表才能得到資料。

4. 鍊位址法(拉鍊法)

将沖突位置的元素構造成連結清單。在添加資料的時候,如果哈希位址與哈希表上的元素沖突,就放在這個位置的連結清單上。

拉鍊法的優點:

(1)處理沖突的方式簡單,且無堆集現象,非同義詞絕不會發生沖突,是以平均查找長度較短;

(2)由于拉鍊法中各連結清單上的結點空間是動态申請的,是以它更适合造表前無法确定表長的情況;

(3)删除結點操作易于實作,隻要簡單地删除連結清單上的相應的結點即可。

拉鍊法的缺點:需要額外的存儲空間。

從HashMap的底層結構中我們可以看到,HashMap采用是數組+連結清單/紅黑樹的組合來作為底層結構,也就是開放位址法+鍊位址法的方式來實作HashMap。

為什麼HashMap的加載因子是0.75

三、為什麼HashMap加載因子一定是0.75?而不是0.8,0.6?

從上文我們知道,HashMap的底層其實也是哈希表(散清單),而解決沖突的方式是鍊位址法。HashMap的初始容量大小預設是16,為了減少沖突發生的機率,當HashMap的數組長度到達一個臨界值的時候,就會觸發擴容,把所有元素rehash之後再放在擴容後的容器中,這是一個相當耗時的操作。

而這個臨界值就是由加載因子和目前容器的容量大小來确定的:

臨界值 = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR

即預設情況下是16x0.75=12時,就會觸發擴容操作。

那麼為什麼選擇了0.75作為HashMap的加載因子呢?這個跟一個統計學裡很重要的原理——泊松分布有關。

泊松分布是統計學和機率學常見的離散機率分布,适用于描述機關時間内随機事件發生的次數的機率分布。有興趣的讀者可以看看維基百科或者阮一峰老師的這篇文章:泊松分布和指數分布

為什麼HashMap的加載因子是0.75

等号的左邊,P表示機率,N表示某種函數關系,t表示時間,n表示數量。等号的右邊,λ表示事件的頻率。

在HashMap的源碼中有這麼一段注釋:

/*
 * 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
 */
           

在理想情況下,使用随機哈希碼,在擴容門檻值(加載因子)為0.75的情況下,節點出現在頻率在Hash桶(表)中遵循參數平均為0.5的泊松分布。忽略方差,即X = λt,P(λt = k),其中λt = 0.5的情況,按公式:

為什麼HashMap的加載因子是0.75

計算結果如上述的清單所示,當一個bin中的連結清單長度達到8個元素的時候,機率為0.00000006,幾乎是一個不可能事件。

是以我們可以知道,其實常數0.5是作為參數代入泊松分布來計算的,而加載因子0.75是作為一個條件,當HashMap長度為length/size ≥ 0.75時就擴容,在這個條件下,沖突後的拉鍊長度和機率結果為:

/*
 * 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
 */           

四、那麼為什麼不可以是0.8或者0.6呢?

HashMap中除了雜湊演算法之外,有兩個參數影響了性能:初始容量和加載因子。初始容量是哈希表在建立時的容量,加載因子是哈希表在其容量自動擴容之前可以達到多滿的一種度量。

在維基百科來描述加載因子:

對于開放定址法,加載因子是特别重要因素,應嚴格限制在0.7-0.8以下。超過0.8,查表時的CPU緩存不命中(cache missing)按照指數曲線上升。是以,一些采用開放定址法的hash庫,如Java的系統庫限制了加載因子為0.75,超過此值将resize散清單。

在設定初始容量時應該考慮到映射中所需的條目數及其加載因子,以便最大限度地減少擴容rehash操作次數,是以,一般在使用HashMap時建議根據預估值設定初始容量,以便減少擴容操作。

選擇0.75作為預設的加載因子,完全是時間和空間成本上尋求的一種折衷選擇。

繼續閱讀