作者：NYfor2020
https://blog.csdn.net/NYfor2017/article/details/105454097
有很多東西之前在學的時候沒怎么注意，筆者也是在重溫HashMap的時候發現有很多可以去細究的問題，最終是會回歸于數學的，如HashMap的加載因子為什么是0.75？
本文主要對以下內容進行介紹：
-
為什么HashMap需要加載因子？
-
解決沖突有什么方法？
-
為什么加載因子一定是0.75？而不是0.8，0.6？
若文章有不正之處，或難以理解的地方，請多多諒解，歡迎指正，
為什么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就是一個插入慢、查詢快的資料結構，
但這種資料結構容易產生兩種問題：
① 如果空間利用率高，那么經過的哈希演算法計算存盤位置的時候，會發現很多存盤位置已經有資料了（哈希沖突）；
② 如果為了避免發生哈希沖突，增大陣列容量，就會導致空間利用率不高，
而加載因子就是表示Hash表中元素的填滿程度，
加載因子 = 填入表中的元素個數 / 散串列的長度
加載因子越大，填滿的元素越多，空間利用率越高，但發生沖突的機會變大了；
加載因子越小，填滿的元素越少，沖突發生的機會減小，但空間浪費了更多了，而且還會提高擴容rehash操作的次數，
沖突的機會越大，說明需要查找的資料還需要通過另一個途徑查找，這樣查找的成本就越高，因此，必須在“沖突的機會”與“空間利用率”之間，尋找一種平衡與折衷，
所以我們也能知道，影響查找效率的因素主要有這幾種：
散列函式是否可以將哈希表中的資料均勻地散列？
怎么處理沖突？
哈希表的加載因子怎么選擇？
本文主要對后兩個問題進行介紹，
解決沖突有什么方法？
1. 開放定址法
Hi = (H(key) + di) MOD m，其中i=1,2,…,k(k<=m-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. 再哈希法
Hi = RHi(key), 其中i=1,2,…,k
RHi()函式是不同于H()的哈希函式，用于同義詞發生地址沖突時，計算出另一個哈希函式地址，直到不發生沖突位置，這種方法不容易產生堆集，但是會增加計算時間，
所以再哈希法的缺點是：
增加了計算時間，
3. 建立一個公共溢位區
假設哈希函式的值域為[0, m-1]，設向量HashTable[0,…,m-1]為基本表，每個分量存放一個記錄，另外還設定了向量OverTable[0,…,v]為溢位表，基本表中存盤的是關鍵字的記錄，一旦發生沖突，不管他們哈希函式得到的哈希地址是什么，都填入溢位表，
但這個方法的缺點在于：
查找沖突資料的時候，需要遍歷溢位表才能得到資料，
4. 鏈地址法（拉鏈法）
將沖突位置的元素構造成鏈表，在添加資料的時候，如果哈希地址與哈希表上的元素沖突，就放在這個位置的鏈表上，
拉鏈法的優點：
處理沖突的方式簡單，且無堆集現象，非同義詞絕不會發生沖突，因此平均查找長度較短；
由于拉鏈法中各鏈表上的結點空間是動態申請的，所以它更適合造表前無法確定表長的情況；
洗掉結點操作易于實作，只要簡單地洗掉鏈表上的相應的結點即可，
拉鏈法的缺點：
需要額外的存盤空間，
從HashMap的底層結構中我們可以看到，HashMap采用是陣列+鏈表/紅黑樹的組合來作為底層結構，也就是開放地址法+鏈地址法的方式來實作HashMap，
至于為什么在JDK1.8的時候要運用到紅黑樹，下篇文章會介紹，關注微信公眾號：Java技術堆疊，在后臺回復：新特性，可以獲取我整理的 N 篇 Java 新特性教程，都是干貨，
為什么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分鐘教程
等號的左邊，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的情況，按公式：
計算結果如上述的串列所示，當一個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作為默認的加載因子，完全是時間和空間成本上尋求的一種折衷選擇，
結語
曾經有一堆高數、線性代數、離散數學擺在我面前，但是我沒有珍惜，等到碰到各種數學問題的時候，才后悔莫及，學計算機的時候最痛苦的事，莫過于此，如果老天可以再給我一個，再來一次的機會的話，我會跟當時的我，說三個字——“學數學！”
數學真的太重要，離開大學之后，該怎么學數學啊，有什么好的建議嗎？
如果本文對你有幫助，請給一個贊吧，這會是我最大的動力~
關注公眾號Java技術堆疊回復"面試"獲取我整理的2020最全面試題及答案，
推薦去我的博客閱讀更多：
1.Java JVM、集合、多執行緒、新特性系列教程
2.Spring MVC、Spring Boot、Spring Cloud 系列教程
3.Maven、Git、Eclipse、Intellij IDEA 系列工具教程
4.Java、后端、架構、阿里巴巴等大廠最新面試題
覺得不錯，別忘了點贊+轉發哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/158268.html
標籤：Java
上一篇：JAVA自學筆記（7）—檔案