HashMap
引言
哈希表(HashTable)
也稱散列表,是一種非常重要的數(shù)據(jù)結構,應用場景機器豐富,許多緩存技術的核心其實就是在內(nèi)存中維護一張大的哈希表,本文會對java集合框架中HashMap的實現(xiàn)原理進行講解,并對JDK7的HashMap袁愛民進行分析
什么是哈希表
首先來了解下其他的數(shù)據(jù)結構再講
- 數(shù)組
采用一段連續(xù)的存儲單元來存儲數(shù)據(jù).對于制定下標的查找,時間復雜度為O(1),通過給定值進行查找,需要遍歷數(shù)組,注意對比給定關鍵字和數(shù)組元素,時間復雜度為O(n),當然對于有序數(shù)組,正則可以采用二分查找,插值查找,斐波那契查找等方式,可將復雜度提高到O(logn)
- 線性鏈表:
對于鏈表新增,刪除等操作(在找到指定操作位置后,僅需要處理節(jié)點之間的引用即可,時間復雜度為O(1),而查找操作需要遍歷鏈表逐一進行比對,復雜度為O(n)
- 二叉樹:
對一棵數(shù)相對平和有序的二叉樹,對其進行插入,查找,刪除等操作,平均復雜度為O(logn)
- 哈希表:
相對上述幾種數(shù)據(jù)結構,在哈希表中進行添加,刪除,查找等操作,性能十分之高,不考慮哈希沖突情況下,僅需一次定位即可完成,時間復雜度為O(1)接下啦Hash表是如何時間復雜度最低的
Tip:
數(shù)組簡單搜下標快,搜元素慢
線性鏈表增刪快,查找慢
二叉樹都差不多
哈希表增刪查都快
我們知道數(shù)據(jù)結構的物理存儲結構只有兩種:順序存儲結構和鏈式存儲結構,而在上面我們提到過,在數(shù)組中根據(jù)下標查找某個元素,一次定位就可達到,哈希表利用了這種特性,哈希表的主干就是數(shù)組.
比如我們要新增或查找某個元素,我們通過吧當前元素的關鍵字通過某個函數(shù) 映射到數(shù)組中的某個位置,通過數(shù)組下標一次定位就可完成操作
這個函數(shù)可以簡單抽象為:cunchuweizhi =f(關鍵字),這個函數(shù)f一般稱為hash函數(shù),函數(shù)的好壞直接影響Hash表的優(yōu)劣,如下執(zhí)行插入數(shù)據(jù)
查找的時候也是同理,先通過哈希函數(shù)計算出實際存儲地址,然后從數(shù)組中對應地址去除即可
哈希沖突
然而Hash并不是完美的.如果兩個不同的元素通過Hash函數(shù)得出的實際存儲地址相同怎么辦?也就是說,當我們對某個元素進行哈希運算,得到一個存儲地址,然后要進行插入的時候,發(fā)現(xiàn)已經(jīng)被其他元素占用了,其實這就是所謂的hash沖突,也叫哈希碰撞,前面我們提到過,哈希函數(shù)的設計至關重要,好的函數(shù)會盡可能的保證計算簡單和散列地址分布均勻,但是,我們需要清楚的是,數(shù)組是一塊連續(xù)的固定長度的內(nèi)存空間,再好的哈希函數(shù)不能保證得到的存儲地址絕不發(fā)生沖突.
那么Hash沖突如何解決呢?哈希沖突解決方案有很多中,開放定址法(發(fā)生沖突,繼續(xù)尋找下一塊未被占用的存儲地址),再散列函數(shù)算法,而HashMap即采用了鏈地址法,也就是數(shù)組+鏈表的方式.
HashMap的實現(xiàn)原理
HashMap的主干是一個Entry數(shù)組.Entry是HashMap的基本組成單元.每一個Entry包含一個key-value鍵值對.其實所謂Map其實就是保存了兩個對象之間映射關系的一種集合.
HashMap中Entry相關代碼
//HashMap的主干數(shù)組,可以看到就是一個Entry數(shù)組,,初始值為空數(shù)組{},,主干數(shù)組的長度一定是2的次冪。
//至于為什么這么做,,后面會有詳細分析,。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Entry是hashMap中的一個靜態(tài)內(nèi)部類.代碼如下
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存儲指向下一個Entry的引用,單鏈表結構
int hash;//對key的hashcode值進行hash運算后得到的值,,存儲在Entry,,避免重復計算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
下圖表示Entry是怎樣存在的
簡單來說,HashMap由數(shù)組+鏈表組成的,數(shù)組是HashMap的主題,鏈表則主要為了解決哈希沖突存在的,如果定位到的數(shù)組位置不含鏈表(如當前Entry的下一個指向的是null)那么查找,添加等操作很快,僅需一次尋址即可;如果定位到數(shù)組包含鏈表,對于添加操作,其復雜度為O(n)首先遍歷表,存在即覆蓋,否則新增;對于查找操作來講,仍需遍歷鏈表,然后通過對key對象的equals方法注意比對查找.所以,性能考慮,HashMap中的鏈表出現(xiàn)越少,性能才會越好
其他幾個重要字段
/**實際存儲的key-value鍵值對的個數(shù)*/
transient int size;
/**閾值,當table == {}時,,該值為初始容量(初始容量默認為16),;當table被填充了,也就是為table分配內(nèi)存空間后,,
threshold一般為 capacity*loadFactory,。HashMap在進行擴容時需要參考threshold,后面會詳細談到*/
int threshold;
/**負載因子,,代表了table的填充度有多少,,默認是0.75
加載因子存在的原因,,還是因為減緩哈希沖突,如果初始桶為16,,等到滿16個元素才擴容,,某些桶里可能就有不止一個元素了。
所以加載因子默認為0.75,,也就是說大小為16的HashMap,,到了第13個元素,就會擴容成32,。
*/
final float loadFactor;
/**HashMap被改變的次數(shù),由于HashMap非線程安全,,在對HashMap進行迭代時,,
如果期間其他線程的參與導致HashMap的結構發(fā)生變化了(比如put,remove等操作),,
需要拋出異常ConcurrentModificationException*/
transient int modCount;
HashMap的數(shù)組長度一定是2的次冪
重寫equals方法須同時重寫hashcode方法
JDK1.8中HashMap的性能優(yōu)化
假如一個數(shù)組槽位上鏈上數(shù)據(jù)過多導致性能下降怎么辦?
1.8在1.7的基礎上針對增加了紅黑樹進行優(yōu)化.即當鏈表超過8是,鏈表就轉換為紅黑樹,利用紅黑樹快速增刪改查的特點提高HashMap的性能,其中會用到紅黑樹的插入,刪除,查找等算法.
總結(重點)
HashMap在底層數(shù)據(jù)結構上采用了數(shù)組+鏈表+紅黑樹,通過散列映射來存儲鍵值對數(shù)據(jù)因為在查詢上使用散列碼(通過鍵生產(chǎn)一個數(shù)字作為數(shù)組下標,這個數(shù)字就是hashcode)所以在查詢上的訪問速度比較快,HashMap最多運行一對鍵值對的Key為NULL,允許多對鍵值對的value為Null.他是非線程安全的,在排序上是無序的
|