[转]为什么Java中的HashMap默认加载因子是0.75
前幾天在一個群里看到有人討論hashmap中的加載因子為什么是默認0.75。
HashMap源碼中的加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;當時想到的是應(yīng)該是“哈希沖突”和“空間利用率”矛盾的一個折衷。
跟數(shù)據(jù)結(jié)構(gòu)要么查詢快要么插入快一個道理，hashmap就是一個插入慢、查詢快的數(shù)據(jù)結(jié)構(gòu)。
加載因子是表示Hash表中元素的填滿的程度。
加載因子越大,填滿的元素越多,空間利用率越高，但沖突的機會加大了。
反之,加載因子越小,填滿的元素越少,沖突的機會減小,但空間浪費多了。
沖突的機會越大,則查找的成本越高。反之,查找的成本越小。
因此,必須在 "沖突的機會"與"空間利用率"之間尋找一種平衡與折衷。
哈希沖突主要與兩個因素有關(guān)，（1）填裝因子，填裝因子是指哈希表中已存入的數(shù)據(jù)元素個數(shù)與哈希地址空間的大小的比值，a=n/m ; a越小，沖突的可能性就越小，相反則沖突可能性較大；但是a越小空間利用率也就越小，a越大，空間利用率越高，為了兼顧哈希沖突和存儲空間利用率，通常將a控制在0.6-0.9之間，而.net中的HashTable則直接將a的最大值定義為0.72 （雖然微軟官方MSDN中聲明HashTable默認填裝因子為1.0，但實際上都是0.72的倍數(shù)），（2）與所用的哈希函數(shù)有關(guān)，如果哈希函數(shù)得當，就可以使哈希地址盡可能的均勻分布在哈希地址空間上，從而減少沖突的產(chǎn)生，但一個良好的哈希函數(shù)的得來很大程度上取決于大量的實踐，不過幸好前人已經(jīng)總結(jié)實踐了很多高效的哈希函數(shù)，可以參考大神Lucifer文章：數(shù)據(jù)結(jié)構(gòu)：HashTable： http://www.cnblogs.com/lucifer1982/archive/2008/06/18/1224319.html
但是為什么一定是0.75？而不是0.8，0.6
本著不嫌事大的精神繼續(xù)深挖，在此之前先簡單補充點本文需要的基礎(chǔ)知識：
1.沖突定義：假設(shè)哈希表的地址集為［0，ｎ），沖突是指由關(guān)鍵字得到的哈希地址為j（0<=j<=n-1）的位置上已經(jīng)有記錄。在關(guān)鍵字得到的哈希地址上已經(jīng)有記錄，那么就稱之為沖突。
2.處理沖突：就是為該關(guān)鍵字的記錄扎到另一個“空”的哈希地址。即在處理哈希地址的沖突時，若得到的另一個哈希地址H1仍然發(fā)生沖突，則再求下一個地址H2，若H2仍然沖突，再求的H3，直至Hk不發(fā)生沖突為止，則Hk為記錄在表中的地址。
處理沖突的幾種方法：
一、 開放定址法
Hi=(H(key) + di) MOD m i=1,2,...k(k<=m-1)其中H(key)為哈希函數(shù)；m為哈希表表長；di為增量序列。
開放定址法根據(jù)步長不同可以分為３種：
1）線性探查法(Linear Probing)：di=1,2,3,...,m-1
簡單地說就是以當前沖突位置為起點，步長為１循環(huán)查找，直到找到一個空的位置就把元素插進去，循環(huán)完了都找不到說明容器滿了。就像你去一條街上的店里吃飯，問了第一家被告知滿座，然后挨著一家家去問是否有位置一樣。
2）線性補償探測法：di=Ｑ 下一個位置滿足 Hi=(H(key) + Ｑ) mod m i=1,2,...k(k<=m-1) ，要求 Q 與 m 是互質(zhì)的，以便能探測到哈希表中的所有單元。
繼續(xù)用上面的例子，現(xiàn)在你不是挨著一家家去問了，拿出計算器算了一下，然后隔Ｑ家問一次有沒有位置。
3）偽隨機探測再散列：di=偽隨機數(shù)序列。還是那個例子，這是完全根據(jù)心情去選一家店來問了
缺點：
- 這種方法建立起來的hash表當沖突多的時候數(shù)據(jù)容易堆聚在一起，這時候?qū)Σ檎也挥押?#xff1b;
- 刪除結(jié)點不能簡單地將被刪結(jié) 點的空間置為空，否則將截斷在它之后填人散列表的同義詞結(jié)點的查找路徑。因此在 用開放地址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點上做刪除標記，而不能真正刪除結(jié)點
- 當空間滿了，還要建立一個溢出表來存多出來的元素。
二、再哈希法
Hi = RHi（key），i=1,2,...k
RHi均是不同的哈希函數(shù)，即在同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，直到不發(fā)生沖突為止。這種方法不易產(chǎn)生聚集，但是增加了計算時間。
缺點：增加了計算時間。
三、建立一個公共溢出區(qū)
假設(shè)哈希函數(shù)的值域為[0,m-1]，則設(shè)向量HashTable[0...m-1]為基本表，每個分量存放一個記錄，另設(shè)立向量OverTable[0....v]為溢出表。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管他們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。
簡單地說就是搞個新表存沖突的元素。
四、鏈地址法（拉鏈法）
將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中，也就是把沖突位置的元素構(gòu)造成鏈表。
拉鏈法的優(yōu)點:
- 拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會發(fā)生沖突，因此平均查找長度較短；
- 由于拉鏈法中各鏈表上的結(jié)點空間是動態(tài)申請的，故它更適合于造表前無法確定表長的情況；
- 在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點的操作易于實現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的結(jié)點即可。
拉鏈法的缺點：
- 指針需要額外的空間，故當結(jié)點規(guī)模較小時，開放定址法較為節(jié)省空間，而若將節(jié)省的指針空間用來擴大散列表的規(guī)模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度
Java中HashMap的數(shù)據(jù)結(jié)構(gòu)
HashMap實際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即數(shù)組和鏈表的結(jié)合體。
HashMap數(shù)據(jù)結(jié)構(gòu)，來源于網(wǎng)絡(luò)看圖就可以知道Java中的hashMap使用了拉鏈法處理沖突。
HashMap有一個初始容量大小，默認是16
為了減少沖突的概率，當hashMap的數(shù)組長度到了一個臨界值就會觸發(fā)擴容，把所有元素rehash再放到擴容后的容器中，這是一個非常耗時的操作。
而這個臨界值由【加載因子】和當前容器的容量大小來確定：DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR ，即默認情況下是16x0.75=12時，就會觸發(fā)擴容操作。
所以使用hash容器時盡量預(yù)估自己的數(shù)據(jù)量來設(shè)置初始值。具體代碼實現(xiàn)自行去研究HashMap的源碼。
基礎(chǔ)知識補充完畢，回到正題，為什么加載因子要默認是0.75？
從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
注意wiki鏈接中的關(guān)鍵字：Poisson_distribution
泊淞分布啊
簡單翻譯一下就是在理想情況下,使用隨機哈希碼,節(jié)點出現(xiàn)的頻率在hash桶中遵循泊松分布，同時給出了桶中元素個數(shù)和概率的對照表。
從上面的表中可以看到當桶中元素到達8個的時候，概率已經(jīng)變得非常小，也就是說用0.75作為加載因子，每個碰撞位置的鏈表長度超過８個是幾乎不可能的。
好了，再深挖就要挖到統(tǒng)計學(xué)那邊去了，就此打住，重申一下使用hash容器請盡量指定初始容量，且是2的冪次方。
關(guān)于泊淞分布的知識請看
http://www.ruanyifeng.com/blog/2015/06/poisson-distribution.html#comment-356111
作者：Eric新之助
鏈接：https://www.jianshu.com/p/dff8f4641814
來源：簡書
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
轉(zhuǎn)載于:https://www.cnblogs.com/DarrenChan/p/8854859.html
總結(jié)
以上是生活随笔為你收集整理的[转]为什么Java中的HashMap默认加载因子是0.75的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C#电视节目单展示案例
- 下一篇： 关于图片裁剪