點擊上方“ 搜雲庫技術團隊 ”關注，選擇“ 設爲星標 ”

回覆“ 面試題 ”領 《96份：3265頁面試題》

前言

有很多東西之前在學的時候沒怎麼注意，筆者也是在重溫HashMap的時候發現有很多可以去細究的問題，最終是會迴歸於數學的，如HashMap的加載因子爲什麼是0.75？

本文主要對以下內容進行介紹：

  • 爲什麼HashMap需要加載因子？

  • 解決衝突有什麼方法？

  • 爲什麼加載因子一定是0.75？而不是0.8，0.6？

（若文章有不正之處，或難以理解的地方，請多多諒解，歡迎指正）

爲什麼HashMap需要加載因子？

HashMap的底層是哈希表，是存儲鍵值對的結構類型，它需要通過一定的計算纔可以確定數據在哈希表中的存儲位置：

一般的數據結構，不是查詢快就是插入快，HashMap就是一個插入慢、查詢快的數據結構。但這種數據結構容易產生兩種問題：① 如果空間利用率高，那麼經過的哈希算法計算存儲位置的時候，會發現很多存儲位置已經有數據了（ 哈希衝突 ）；② 如果爲了避免發生哈希衝突，增大數組容量，就會導致空間利用率不高。

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

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

加載因子越大，填滿的元素越多，空間利用率越高，但發生衝突的機會變大了；

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

衝突的機會越大，說明需要查找的數據還需要通過另一個途徑查找，這樣查找的成本就越高。因此，必須在“衝突的機會”與“空間利用率”之間，尋找一種平衡與折衷。

所以我們也能知道，影響查找效率的因素主要有這幾種：

  • 散列函數是否可以將哈希表中的數據均勻地散列？

  • 怎麼處理衝突？

  • 哈希表的加載因子怎麼選擇？

本文主要對後兩個問題進行介紹。

解決衝突有什麼方法？

1. 開放定址法

H(key)爲哈希函數，m爲哈希表表長，di爲增量序列，i爲已發生衝突的次數。其中，開放定址法根據步長不同可以分爲3種：

1.1 線性探查法（Linear Probing）：di = 1,2,3,…,m-1

簡單地說，就是以當前衝突位置爲起點，步長爲1循環查找，直到找到一個空的位置，如果循環完了都佔不到位置，就說明容器已經滿了。舉個栗子，就像你在飯點去街上喫飯，挨家去看是否有位置一樣。

1.2 平方探測法（Quadratic Probing）：di = ±12, ±22，±32，…，±k2（k≤m/2）

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

1.3 僞隨機探測法：di = 僞隨機數序列

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

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

  • 這種方法建立起來的哈希表，當衝突多的時候數據容易堆集在一起，這時候對查找不友好；

  • 刪除結點的時候不能簡單將結點的空間置空，否則將截斷在它填入散列表之後的同義詞結點查找路徑。因此如果要刪除結點，只能在被刪結點上添加刪除標記，而不能真正刪除結點；

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

2. 再哈希法

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

所以再哈希法的 缺點 是：

  • 增加了計算時間。

3. 建立一個公共溢出區

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

但這個方法的 缺點 在於：

  • 查找衝突數據的時候，需要遍歷溢出表才能得到數據。

4. 鏈地址法（拉鍊法）

將衝突位置的元素構造成鏈表。在添加數據的時候，如果哈希地址與哈希表上的元素衝突，就放在這個位置的鏈表上。

拉鍊法的 優點 ：

  • 處理衝突的方式簡單，且無堆集現象，非同義詞絕不會發生衝突，因此平均查找長度較短；

  • 由於拉鍊法中各鏈表上的結點空間是動態申請的，所以它更適合造表前無法確定表長的情況；

  • 刪除結點操作易於實現，只要簡單地刪除鏈表上的相應的結點即可。

拉鍊法的 缺點 ：

需要額外的存儲空間。

從HashMap的底層結構中我們可以看到，HashMap採用是數組+鏈表/紅黑樹的組合來作爲底層結構，也就是開放地址法+鏈地址法的方式來實現HashMap。

至於爲什麼在JDK1.8的時候要運用到紅黑樹，下篇文章會介紹。

爲什麼HashMap加載因子一定是0.75？而不是0.8，0.6？

從上文我們知道，HashMap的底層其實也是哈希表（散列表），而解決衝突的方式是鏈地址法。HashMap的初始容量大小默認是16，爲了減少衝突發生的概率，當HashMap的數組長度到達一個臨界值的時候，就會觸發擴容，把所有元素rehash之後再放在擴容後的容器中，這是一個相當耗時的操作。

而這個臨界值就是由加載因子和當前容器的容量大小來確定的：

臨界值 = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR

即默認情況下是16x0.75=12時，就會觸發擴容操作。

那麼爲什麼選擇了0.75作爲HashMap的加載因子呢？筆者不才，通過看源碼解釋和大佬的文章，才知道這個跟一個統計學裏很重要的原理—— 泊松分佈 有關。

泊松分佈是統計學和概率學常見的離散概率分佈， 適用於描述單位時間內隨機事件發生的次數的概率分佈 。有興趣的讀者可以看看維基百科或者阮一峯老師的這篇文章：[泊松分佈和指數分佈：10分鐘教程][10]

等號的左邊，P 表示概率，N表示某種函數關係，t 表示時間，n 表示數量。等號的右邊，λ 表示事件的頻率。

在HashMap的源碼中有這麼一段註釋：

筆者拙譯：在理想情況下，使用隨機哈希碼， 在擴容閾值（加載因子）爲0.75的情況下，節點出現在頻率在Hash桶（表）中遵循參數平均爲0.5的泊松分佈 。忽略方差，即X = λt，P(λt = k)，其中λt = 0.5的情況，按公式：

計算結果如上述的列表所示，當一個bin中的鏈表長度達到8個元素的時候，概率爲0.00000006，幾乎是一個不可能事件。

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

那麼爲什麼不可以是0.8或者0.6呢？

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

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

對於開放定址法，加載因子是特別重要因素， 應嚴格限制在0.7-0.8以下。超過0.8，查表時的CPU緩存不命中（cache missing）按照指數曲線上升 。因此，一些採用開放定址法的hash庫，如Java的系統庫限制了加載因子爲0.75，超過此值將resize散列表。

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

選擇0、75作爲默認的加載因子， 完全是時間和空間成本上尋求的一種折衷選擇 。

結語

曾經有一堆高數、線性代數、離散數學擺在我面前，但是我沒有珍惜。等到碰到各種數學問題的時候，才後悔莫及。學計算機的時候最痛苦的事，莫過於此。如果老天可以再給我一個，再來一次的機會的話。我會跟當時的我，說三個字——“學數學！”

數學真的太重要。離開大學之後，該怎麼學數學啊，有什麼好的建議嗎？

如果本文對你有幫助，請給一個贊吧，這會是我最大的動力~

作者：NYfor2020

來源：8rr.co/8V9Q

《第2版：互聯網大廠面試題》

最近又趕上跳槽的高峯期，好多粉絲，都問我要有沒有最新面試題，索性，我就把我看過的和我面試中的真題，及答案都整理好， 整理了 《第2版：互聯網大廠面試題》 並 分類  92 份  PDF ， 累計 3625頁！ 我會持續更新中，馬上就出第三版，涵蓋大廠算法會更多！

第2版：題庫非常全面

包括 Java 集合、JVM、多線程、併發編程、設計模式、Spring全家桶、Java、MyBatis、ZooKeeper、Dubbo、Elasticsearch、Memcached、MongoDB、Redis、MySQL、RabbitMQ、Kafka、Linux、Netty、Tomcat、Python、HTML、CSS、Vue、React、JavaScript、Android 大數據、阿里巴巴等大廠面試題等、等技術棧！

第2版：面試題，怎麼領取？

掃碼關注， 我另一個公衆號 ， 架構師專欄

（對，就是我小號）

沒錯，掃碼關注，即可下載

（這是神奇的二維碼，你不用回覆關鍵字）

相關文章