HashMap分析
2019-11-09 15:53:22
供稿：網(wǎng)友
一 .概況1.概念和相關(guān)需要了解的基礎(chǔ)知識點1.1 HashMap也是我們使用非常多的Collection，它是基于哈希表(散列表)的 Map 接口的實現(xiàn)，以key-value的形式存在。在HashMap中，key-value總是會當(dāng)做一個整體來處理，系統(tǒng)會根據(jù)hash算法來來計算key-value的存儲位置，我們總是可以通過key快速地存、取value。HashMap的底層實現(xiàn)還是數(shù)組（table）。1.2 散列表散列地址：數(shù)組的索引角標(biāo)（table中的index）散列函數(shù)：散列表算法希望能盡量做到不經(jīng)過任何比較，通過一次存取就能得到所查找的數(shù)據(jù)元素，因而必須要在數(shù)據(jù)元素的存儲位置和它的關(guān)鍵字（可用key表示）之間建立一個確定的對應(yīng)關(guān)系，使每個關(guān)鍵字和散列表中一個唯一的存儲位置相對應(yīng)。因此在查找時，只要根據(jù)這個對應(yīng)關(guān)系找到給定關(guān)鍵字在散列表中的位置即可。這種對應(yīng)關(guān)系被稱為散列函數(shù)(可用h(key)表示)。1.3常用的散列函數(shù)有（1）、直接定址法取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址，即：h(key) = key 或 h(key) = a * key + b其中a和b為常數(shù)。（2）、數(shù)字分析法（3）、平方取值法取關(guān)鍵字平方后的中間幾位為散列地址。（4）、折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進位）作為散列地址。（5）、除留余數(shù)法取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址，即： h(key) = key MOD p p ≤ m（6）、隨機數(shù)法選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的散列地址，即：h(key) = random(key)其中random為隨機函數(shù)。1.4、處理沖突1.4.1產(chǎn)生沖突的原因?qū)Σ煌年P(guān)鍵字可能得到同一散列地址，即key1 ≠ key2，而h(key1)= h(key2)，這種現(xiàn)象稱為沖突。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱作同義詞。在一般情況下，散列函數(shù)是一個壓縮映像，這就不可避免地會產(chǎn)生沖突，因此，在創(chuàng)建散列表時不僅要設(shè)定一個好的散列函數(shù)，而且還要設(shè)定一種處理沖突的方法。1.4.2解決沖突的方法（1）、開放定址法hi =(h(key) + di) MOD m i =1,2,…,k(k ≤ m-1)其中，h(key)為散列函數(shù)，m為散列表表長，di為增量序列，可有下列三種取法：1)、di = 1,2,3,…,m-1，稱線性探測再散列；2）、di = 12,-12,22,-22,32,…,±k2 (k ≤m/2)，稱二次探測再散列；3）、di = 偽隨機數(shù)序列，稱偽隨機探測再散列。（2）、再散列法hi = rhi(key) i = 1,2,…,krhi均是不同的散列函數(shù)。（3）、鏈地址法將所有關(guān)鍵字為同義詞的數(shù)據(jù)元素存儲在同一線性鏈表中。假設(shè)某散列函數(shù)產(chǎn)生的散列地址在區(qū)間[0,m-1]上，則設(shè)立一個指針型向量void *vec[m],其每個分量的初始狀態(tài)都是空指針。凡散列地址為i的數(shù)據(jù)元素都插入到頭指針為vec[i]的鏈表中。在鏈表中的插入位置可以在表頭或表尾，也可以在表的中間，以保持同義詞在同一線性鏈表中按關(guān)鍵字有序排列。（4）、建立一個公共溢出區(qū)二.HashMap的詳細(xì)說明HashMap提供了三個構(gòu)造函數(shù)：HashMap()：構(gòu)造一個具有默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75) 的空 HashMap。HashMap(int initialCapacity)：構(gòu)造一個帶指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap。HashMap(int initialCapacity, float loadFactor)：構(gòu)造一個帶指定初始容量和加載因子的空 HashMap。在這里提到了兩個參數(shù)：初始容量，加載因子。這兩個參數(shù)是影響HashMap性能的重要參數(shù)，其中容量表示哈希表中桶的數(shù)量，初始容量是創(chuàng)建哈希表時的容量，加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度，它衡量的是一個散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。對于使用鏈表法的散列表來說，查找一個元素的平均時間是O(1+a)，因此如果負(fù)載因子越大，對空間的利用更充分，然而后果是查找效率的降低；如果負(fù)載因子太小，那么散列表的數(shù)據(jù)將過于稀疏，對空間造成嚴(yán)重浪費。系統(tǒng)默認(rèn)負(fù)載因子為0.75，一般情況下我們是無需修改的。HashMap是一種支持快速存取的數(shù)據(jù)結(jié)構(gòu)，要了解它的性能必須要了解它的數(shù)據(jù)結(jié)構(gòu)。其內(nèi)部的數(shù)據(jù)結(jié)構(gòu)就是哈希表，也就是散列表而相關(guān)的特性在上面已經(jīng)都列出了，這里做一個總結(jié)：（1）HashMap內(nèi)部存儲使用的是哈希表（散列表），底層是數(shù)組（2）HashMap使用的散列表中散列函數(shù)為：直接定地址法（key的hashcode）；解決沖突用的鏈地址法（3）默認(rèn)初始容量 (16) 和默認(rèn)加載因子 (0.75)（4）value作為key值的“附帶物“保存（5）數(shù)據(jù)在hashmap中的存，取過程：存：a.根據(jù)key的hashcode得到哈希值，再經(jīng)int hash = hash(key.hashCode())得到其在table數(shù)組中的索引b.判斷索引位上有沒有數(shù)據(jù)，沒有就直接存；有看key是不是相同，若相同則新value值取代老value值，若不同則以鏈表的方式存入取：就是存的反向過程，沒有就只能返回null（6）對于HashMap的table而言，數(shù)據(jù)分布均勻問題：最好每項都只有一個元素，這樣就可以直接找到，不能太緊也不能太松，太緊會導(dǎo)致查詢速度慢，太松則浪費空間.具體的分析參考：http://www.cnblogs.com/chenssy/p/3521565.html中的分析 參考：HashMap：http://www.cnblogs.com/chenssy/p/3521565.html 散列表：http://blog.csdn.net/npy_lp/article/details/7390378
