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