HashMap
HashMap 的數(shù)據(jù)結(jié)構(gòu)
HashMap 的底層實現(xiàn)是 Entry數(shù)組捺宗,(如圖1結(jié)構(gòu))柱蟀。
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能<0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ initialCapacity);
//初始容量不能 > 最大容量值媳溺,HashMap的最大容量值為2^30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//負載因子不能 < 0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "
+ loadFactor);
// 計算出大于 initialCapacity 的最小的 2 的 n 次方值进每。
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
//設(shè)置HashMap的容量極限夕土,當(dāng)HashMap的容量達到該極限時就會進行擴容操作
threshold = (int) (capacity * loadFactor);
//初始化table數(shù)組
table = new Entry[capacity];
init();
}
從 HashMap 構(gòu)造方法可以看出:
- 每次實例化一個 HashMap芯侥,其內(nèi)部會自動初始化一個 Entry數(shù)組澎埠;
- HashMap 支持帶參構(gòu)造祈噪,
int initCapacity
(初始化數(shù)組大小雕擂,默認值是16)踊东,另一個是float loadFactor
(負載因子贰健,默認值是0.75)胞四。HashMap 內(nèi)部實現(xiàn)會根據(jù)initCapacity 與 loadFactor 計算出一個臨界值即threshold = (int) (capacity * loadFactor);
,當(dāng)HashMap 存放的元素數(shù)量達到這個臨界值時會自動進行擴容伶椿。容易得出結(jié)論辜伟,負載因子是用戶用于確定當(dāng)存儲的數(shù)量達到存儲容量的比例時再進行擴容(后有詳細解釋)。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
... ...
}
Entry是 HashMap 的內(nèi)部類脊另,其中 Entry 為 HashMap 的內(nèi)部類导狡,它包含了鍵 key、值 value偎痛、下一個節(jié)點 next旱捧,以及 hash 值,正是由于 Entry 才構(gòu)成了 table 數(shù)組的項為鏈表看彼。
HashMap 添加(put)數(shù)據(jù)(包括key和value)
public V put(K key, V value) {
//當(dāng)key為null廊佩,調(diào)用putForNullKey方法囚聚,保存null于table第一個位置中,這是HashMap允許為null的原因
if (key == null) {
return putForNullKey(value);
}
//計算key的hash值
int hash = hash(key.hashCode()); // -------------------------(1)
//計算key hash 值在 table 數(shù)組中的位置
int i = indexFor(hash, table.length); // ----------------------(2)
//從i出開始迭代 e,找到 key 保存的位置
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k = null;
//判斷該條鏈上是否有hash值相同的(key相同)
//若存在相同标锄,則直接覆蓋value顽铸,返回舊value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //舊值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //返回舊值
}
}
//修改次數(shù)增加1
modCount++;
//將key、value添加至i位置處
addEntry(hash, key, value, i);
return null;
}
由 put()方法源碼可見料皇,添加數(shù)據(jù)時谓松,首先判斷 key 是否為 null,若為 null践剂,則直接調(diào)用 putForNullKey 方法(這也是 HashMap 不同于 HashTable 支持鍵值為null的原因)鬼譬。若不為空則先計算 key 的 hash 值(hashCode())得到長度固定(10)的整型值。
然后根據(jù) hash 值搜索在 table 數(shù)組中的索引位置逊脯,如果 table 數(shù)組在該位置處有元素优质,需要比較是否存在相同的 key 值。若存在军洼,則覆蓋之前的 value巩螃;若不存在,則直接將數(shù)據(jù)存放于鏈表頭部(每個節(jié)點包括了存放的數(shù)據(jù)(key匕争、value)避乏,指向下一節(jié)點的指針。數(shù)據(jù)保存為”頭插入“)甘桑。如果 table 數(shù)組在該位置處無元素拍皮,直接保存。
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12); // >>> 無符號右移
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length - 1);
}
hash()
方法可以保證所求得的 hash 值為正數(shù)跑杭,HashMap 的底層數(shù)組長度總是 2 的 n 次方铆帽,在構(gòu)造函數(shù)中存在:capacity <<= 1;
這樣做總是能夠保證 HashMap 的底層數(shù)組長度為 2 的 n 次方。當(dāng) length 為 2 的 n 次方時艘蹋,h & (length – 1)
就相當(dāng)于對 length 取模锄贼,從而確保 index 的值一定在 0 ~ length-1 之間。而且速度比直接取呐В快得多宅荤,這是 HashMap 在速度上的一個優(yōu)化。
實際上浸策,indexFor() 方法中的唯一語句 h & (length - 1)
除了計算下標(biāo)外還有一個重要作用:加以條件length = 2^n
從而均勻分布 table 數(shù)據(jù)和充分利用空間冯键。如下表:
h | length-1 | h & (length - 1) |
index |
---|---|---|---|
0 | 14 | 0000 & 1110 |
0 |
1 | 14 | 0001 & 1110 |
0 |
2 | 14 | 0010 & 1110 |
2 |
3 | 14 | 0011 & 1110 |
2 |
4 | 14 | 0100 & 1110 |
4 |
5 | 14 | 0101 & 1110 |
4 |
6 | 14 | 0110 & 1110 |
6 |
7 | 14 | 0111 & 1110 |
6 |
8 | 14 | 1000 & 1110 |
8 |
9 | 14 | 1001 & 1110 |
8 |
... | ... | ... | ... |
14 | 14 | 1110 & 1110 |
14 |
15 | 14 | 1111 & 1110 |
14 |
... | ... | ... | ... |
容易看出,當(dāng)length為15時庸汗,只有在下標(biāo)為 0惫确、2、4、6改化、8……的空間下保存數(shù)據(jù)掩蛤,不曾且也不會為下標(biāo)為 1、3陈肛、5揍鸟、7……分配數(shù)據(jù)。不僅增大了碰撞的概率句旱,空間也產(chǎn)生了很大程度上的浪費阳藻。
而當(dāng) length = 16 時,length – 1 = 15 即 1111
谈撒,那么進行低位 & 運算時腥泥,值總是與原來 hash 值相同;而進行高位運算時啃匿,其值等于其低位值蛔外。所以說當(dāng) length = 2^n
時,不同的 hash 值發(fā)生碰撞的概率比較小立宜,這樣就會使得數(shù)據(jù)在 table 數(shù)組中分布較均勻冒萄,查詢速度也較快。
void addEntry(int hash, K key, V value, int bucketIndex) {
//獲取bucketIndex處的Entry
Entry<K, V> e = table[bucketIndex];
//將新創(chuàng)建的 Entry 放入 bucketIndex 索引處橙数,并讓新的 Entry 指向原來的 Entry
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
//若HashMap中元素的個數(shù)超過極限了,則容量擴大兩倍
if (size++ >= threshold) {
resize(2 * table.length);
}
}
以上源碼為“鏈”的產(chǎn)生過程帅戒。
HashMap
為數(shù)據(jù)鏈添加新節(jié)點的方式總是“頭插入”灯帮。即,總是將新的 Entry 添加到數(shù)組的bucketIndex
處逻住。如果 bucketIndex
處已有對象钟哥,則新添加的 Entry 對象指向原有的 Entry 對象,從而形成一條 Entry 鏈瞎访。若 bucketIndex
處無對象腻贰,即 e = null
, 那么新添加的 Entry 就指向了 null,也就不會產(chǎn)生 Entry 鏈了扒秸。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
??隨著 HashMap 中元素越來越多播演,發(fā)生“碰撞”的該與也就越來越高,鏈表長度也會越來越長伴奥,這樣勢必會影響 HashMap 的速度写烤,為了保證 HashMap 的效率,系統(tǒng)必須在某個臨界點對數(shù)組進行擴容處理拾徙。這個臨界點是“ HashMap 中元素的數(shù)量等于 table 數(shù)組長度 * 加載因子”洲炊,及(size >= threshold
)。載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度,它衡量的是一個散列表的空間的使用程度暂衡,負載因子越大表示散列表的裝填程度越高询微,反之愈小。對于使用鏈表法的散列表來說狂巢,查找一個元素的平均時間是 O(1+a)撑毛,因此如果負載因子越大,對空間的利用更充分隧膘,然而后果是查找效率的降低代态;如果負載因子太小,那么散列表的數(shù)據(jù)將過于稀疏疹吃,對空間造成嚴重浪費蹦疑。但是需要注意的是擴容處理是一個極為耗時的操作,因為這存在對原有數(shù)據(jù)位置重新運算萨驶、移動歉摧、復(fù)制。所以當(dāng)我們能夠最大程度上預(yù)知存放元素的個數(shù)腔呜,就可以一定程度上避免這種耗時操作的發(fā)生叁温,從而提高效率。
HashMap 取得(get)數(shù)據(jù)(value)
public V get(Object key) {
// 若為null核畴,調(diào)用getForNullKey方法返回相對應(yīng)的value
if (key == null) {
return getForNullKey();
}
// 根據(jù)該 key 的 hashCode 值計算它的 hash 碼
int hash = hash(key.hashCode());
// 取出 table 數(shù)組中指定索引處的值
for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
//若搜索的key與查找的key相同膝但,則返回相對應(yīng)的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
return e.value;
}
}
return null;
}
相較 HashMap 的保存(put)數(shù)據(jù),取得(get)數(shù)據(jù)就顯得異常簡單了谤草。當(dāng)取得數(shù)據(jù)時跟束,先判斷鍵值是否為 null,若是 null 則調(diào)用 getForNullKey();
返回鍵值為null 所對應(yīng)的value丑孩。若不為 null冀宴,則計算鍵值在數(shù)組中的位置下標(biāo) bucketIndex,再遍歷table數(shù)組 bucketIndex 處的鏈表温学,比較每個節(jié)點( Entry) 的 hash 值與 key 值略贮。若找到則返回對應(yīng)的 value ,未找到返回 null 。
有關(guān) HashMap 線程并發(fā)
在 HashMap 官方文檔描述中提到:
it is unsynchronized and permits nulls仗岖。
也就是說逃延,如果多個線程同時訪問一個 HashMap,而其中至少一個線程從結(jié)構(gòu)上(指添加或者刪除一個或多個映射關(guān)系的任何操作)修改了箩帚,則必須保持外部同步真友,以防止對映射進行意外的非同步訪問〗襞粒”僅改變與實例已經(jīng)包含的鍵關(guān)聯(lián)的值不是結(jié)構(gòu)上的修改盔然。顯而易見桅打,HashMap 并不是線程安全的。
解決方案:
- 這一般通過對自然封裝該映射的對象進行同步操作來完成愈案。如果不存在這樣的對象挺尾,則應(yīng)該使用
Collections.synchronizedMap(new HashMap())
方法來“包裝”該映射。最好在創(chuàng)建時完成這一操作站绪,以防止對映射進行意外的非同步訪問遭铺。 - 可以在實例化 HashMap 時對其使用
volatile
關(guān)鍵字禁止JVM對 HashMap 的內(nèi)存優(yōu)化,使得所有線程都直接對“主內(nèi)存”的空間進行操作恢准,從而保證 HashMap 的數(shù)據(jù)同步魂挂。除此之外,使用synchronized
關(guān)鍵字對操作進行加鎖馁筐。這樣就可以保證 HashMap 的線程安全性涂召。
HashTable
HashTable的數(shù)據(jù)結(jié)構(gòu)
HashTable 內(nèi)部實現(xiàn)與 HashMap 幾乎相同。同樣采用“拉鏈法”實現(xiàn)散列表敏沉,在數(shù)據(jù)結(jié)構(gòu)上同樣使用“Entry 數(shù)組”果正。
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
... ...
}
可以看出,構(gòu)造方法執(zhí)行過程也幾乎與 HashMap 完全相同盟迟。Entry 是HashTable 的內(nèi)部類秋泳,與 HashMap 相同。
HashTable添加(put)數(shù)據(jù)(包括key和value)
public synchronized V put(K key, V value) {
// 確保value不為null
if (value == null) {
throw new NullPointerException();
}
/*
* 確保key在table[]是不重復(fù)的
* 處理過程:
* 1攒菠、計算key的hash值迫皱,確認在table[]中的索引位置
* 2、迭代index索引位置辖众,如果該位置處的鏈表中存在一個一樣的key舍杜,則替換其value,返回舊值
*/
Entry<?,?> tab[] = table;
int hash = key.hashCode(); // 計算key的hash值
int index = (hash & 0x7FFFFFFF) % tab.length; // 計算key的索引位置
//迭代赵辕,尋找該key,替換
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
//如果容器中的元素數(shù)量已經(jīng)達到閥值概龄,則進行擴容操作
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// 在索引位置處插入一個新的節(jié)點
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// 擴容后容量擴大兩倍 + 1还惠,
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
可以看到與 HashMap 不同的是,HashTable中的 put() 方法是有synchronized
關(guān)鍵詞修飾的私杜。其計算 key 索引地址index 的方式也有所不同蚕键,(hash & 0x7FFFFFFF) % tab.length
,將 hash 與 0x7FFFFFFF按位與相當(dāng)于給 hash 取絕對值衰粹,再與length進行取模運算锣光。
在這個 rehash() 方法中同時需要將原來 HashTable 中的元素一一復(fù)制到新的 HashTable 中,這個過程是比較消耗時間的铝耻。這里對閥值啰嗦一下:比如初始值 11誊爹、加載因子默認 0.75蹬刷,那么這個時候閥值 threshold=8,當(dāng)容器中的元素達到 8 時频丘,HashTable 進行一次擴容操作办成,容量 = 8 * 2 + 1 =17,而閥值 threshold=17*0.75 = 13搂漠,當(dāng)容器元素再一次達到閥值時迂卢,HashTable 還會進行擴容操作,一次類推桐汤。
HashTable取得(get)數(shù)據(jù)(value)
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
分析可見 HashMap get() 方法而克。唯一不同的是HashTable中的 get() 方法有synchronized
關(guān)鍵詞修飾。
有關(guān) HashTable線程并發(fā)
對 HashTable 進行的絕大多數(shù)的方法都有synchronized
關(guān)鍵詞修飾怔毛,這也就使得所有對 HashTable 的操作都是同步的员萍,這樣就保證了,在多線程訪問Hashtable時馆截,不需要開發(fā)人員對其進行同步充活。也就是說,HashTable 是線程安全的蜡娶。
HashMap 與 HashTable 的區(qū)別
- HashMap 可以允許存在一個為 null 的 key 和任意個為 null 的 value混卵,但是 HashTable 中的 key 和 value 都不允許為 null。
??當(dāng)HashMap 遇到為 null 的鍵值:
if (key == null)
return putForNullKey(value);
??而當(dāng) HashTable 遇到 null 的鍵值:
if (value == null) {
throw new NullPointerException();
}
Hashtable 的方法是同步(對數(shù)據(jù)的操作是同步寫入“堆內(nèi)存”)窖张,而 HashMap 的方法不是幕随。這也就意味著,Hashtable在性能方面會遜色于HashMap宿接。
HashMap中不再使用Hashtable的contains()方法赘淮,取而代之的是,containsValue()和containsKey()方法睦霎,在語義和實用性上都有了質(zhì)的提升梢卸。
兩者的迭代容器不同。Hashtable為Enumeration副女,HashMap為Iterator蛤高。
本篇文章是寫于 2017.08.07 的學(xué)習(xí)筆記,與筆者另一篇 關(guān)于散列表的學(xué)習(xí)筆記 本是同屬一篇碑幅,現(xiàn)在為了明確其分類將兩者分開戴陡。
另外,由于筆者寫這篇文章時是基于 JDK7 的源碼沟涨,所以其 HashMap 與
HashTable 的實現(xiàn)方案同為“Entry數(shù)組”恤批。后來當(dāng)我查看 JDK8 的源碼時,發(fā)現(xiàn) HashTable仍然是“Entry數(shù)組”裹赴,但HashMap 似乎更改了實現(xiàn)方案喜庞。但由于筆者自己對 “紅黑樹” 的數(shù)據(jù)結(jié)構(gòu)不是很了解也就沒有再重新寫關(guān)于新實現(xiàn)方案的分析诀浪,以后會更新。
如果您發(fā)現(xiàn)了文章中的錯誤赋荆、漏洞以及需要補充的地方笋妥,歡迎留言交流。