HashMap詳解 - 簡書

問題導(dǎo)入：

?HashMap底層數(shù)據(jù)結(jié)構(gòu)塞淹，如何處理hash沖突位喂，為何HashMap的大小要設(shè)置為2的n次冪挠阁，為什么IndexFor方法里，需要hash&length-1硫朦，為什么HashMap允許null值贷腕，resize()過程，多線程下resize為什么會出現(xiàn)死循環(huán)咬展？

1. HashMap的底層數(shù)據(jù)結(jié)構(gòu)

? ? ? ? ?Hash采用的是鏈地址法(數(shù)組+鏈表)解決hash沖突問題(無外乎在取值和存值的時候泽裳，key會不會沖突)，其中在hashMap內(nèi)部定義了一個靜態(tài)的內(nèi)部類Entry破婆，Entry包含key,value涮总，next。

2.初始化HashMap

? ? 分為兩種情況祷舀，利用a.自定義的初始化的容量瀑梗，b.利用HashMap內(nèi)部定義的長度DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16默認(rèn)是16，利用默認(rèn)的長度就是創(chuàng)建一個Entry[] table = new Entry[DEFAULT_INITIAL_CAPACITY?];我們重點講解的是第一種情況蔑鹦，隨機(jī)定義一個初始化的容量夺克，

public?HashMap(int?initialCapacity,?float?loadFactor)?{

????????int?capacity?=?1;//默認(rèn)都是從1開始，位移嚎朽，達(dá)到所有的容量都是2的n次冪

????????while?(capacity?<?initialCapacity)

????????????capacity?<<=?1;//左移1位

????????this.loadFactor?=?loadFactor;

????????threshold?=?(int)(capacity?*?loadFactor);//閾值

????????table?=?new?Entry[capacity];//生成table數(shù)組

????????init();

????}

注意table初始大小并不是構(gòu)造函數(shù)中的initialCapacityＦ膛Α！

而是 >= initialCapacity的2的n次冪

引入新的問題：為什么這么設(shè)計數(shù)組的長度2的n次冪：其實為了更好的解決hash沖突

3. HashMap的存取

? 從? get(key)哟忍， put(key,value)入手狡门，這兩個容易發(fā)生hash沖突的地方，沖突主要是key的定位

存儲時:

?int?hash?=?hash(key.hashCode());//先計算key的hashCode锅很，然后再hash

?int?i?=?indexFor(hash,?table.length);//定位到具體的table數(shù)組中

取值時:

?int?hash?=?hash(key.hashCode());//先計算key的hashCode其馏，然后再hash

?int?i?=?indexFor(hash,?table.length);//定位到具體的table數(shù)組中

?Entry[i];

3.1 put(key,value)的詳解

? ? ? 當(dāng)存入值的時候，先計算key的hashCode,然后再hash爆安，然后通過indexFor()定位到具體的table數(shù)組中叛复，這時候出現(xiàn)當(dāng)多個key定位到數(shù)組的同一個位置，先遍歷該位置上的鏈表，判斷有沒有key相同,如果有的話褐奥，更新對應(yīng)key的value,如果沒有插入到頭節(jié)點

public?V?put(K?key,?V?value)?{

????????if?(key?==?null)

? ? ? returnputForNullKey(value);//放入null值的時候咖耘，null總是放在數(shù)組的第一個鏈表中

????????int?hash?=?hash(key.hashCode());

????????int?i?=?indexFor(hash,?table.length);//定位table的位置

????????//遍歷鏈表

????????for?(Entry<K,V>?e?=?table[i];?e?!=?null;?e?=?e.next)?{

????????????Object?k;

????????????if?(e.hash?==?hash?&&?((k?=?e.key)?==?key?||?key.equals(k)))?{

????????????????V?oldValue?=?e.value;

????????????????e.value?=?value;???????//如果key在鏈表中已存在，則替換為新value

????????????????e.recordAccess(this);

????????????????return?oldValue;

????????????}

????????}

????????modCount++;

????????addEntry(hash,?key,?value,?i);

????????return?null;

????}

void?addEntry(int?hash,?K?key,?V?value,?int?bucketIndex)?{

????Entry<K,V>?e?=?table[bucketIndex];

????table[bucketIndex]?=?new?Entry<K,V>(hash,?key,?value,?e);?//參數(shù)e, 是Entry.next

????if?(size++?>=?threshold)

????????????resize(2?*?table.length);????//如果size超過threshold撬码，則擴(kuò)充table大小儿倒，再散列

? ? ? ? //先加入值，再擴(kuò)容呜笑，可能導(dǎo)致最后一次擴(kuò)容的浪費(用不著了)

}

3.2 get(key)

?public?V?get(Object?key)?{

????????if?(key?==?null)

????????????return?getForNullKey();//當(dāng)key為null的時候

????????int?hash?=?hash(key.hashCode());? //先定位到數(shù)組元素夫否，再遍歷該元素處的鏈表

????????for?(Entry<K,V>?e?=?table[indexFor(hash,?table.length)]; e?!=?null;e?=?e.next)?{

????????????Object?k;

????????????if?(e.hash?==?hash?&&?((k?=?e.key)?==?key?||?key.equals(k)))

????????????????return?e.value;

????????}

????????return?null;

}

3.3 null的存取

null key總是存放在Entry[]數(shù)組的第一個元素。

???private?V?putForNullKey(V?value)?{

????????for?(Entry<K,V>?e?=?table[0];?e?!=?null;?e?=?e.next)?{

????????????if?(e.key?==?null)?{

????????????????V?oldValue?=?e.value;

????????????????e.value?=?value;

????????????????e.recordAccess(this);

????????????????return?oldValue;

????????????}

????????}

????????modCount++;

????????addEntry(0,?null,?value,?0);

????????return?null;

????}

????private?V?getForNullKey()?{

????????for?(Entry<K,V>?e?=?table[0];?e?!=?null;?e?=?e.next)?{

????????????if?(e.key?==?null)

????????????????return?e.value;

????????}

????????return?null;

}

3.4確定table數(shù)組的位置

????static?int?indexFor(int?h,?int?length)?{

????????return?h?&?(length-1);

????}

按位取并叫胁，作用上相當(dāng)于取模mod或者取余%凰慈。

因為hashMap容量的變化，我們總是將容量定位>=initCapacity的2的次冪曹抬，所以length-1,則每個位置上都是1溉瓶，這樣的與運算，可以保證均勻定位

3.5 resize()重新擴(kuò)容

void?resize(int?newCapacity)?{//newCapacity的值是舊的capacity的值的2倍谤民，保證容量一直是2的次冪

????????Entry[]?oldTable?=?table;

????????int?oldCapacity?=?oldTable.length;

????????if?(oldCapacity?==?MAXIMUM_CAPACITY)?{

????????????threshold?=?Integer.MAX_VALUE;

????????????return;

????????}

????????Entry[]?newTable?=?new?Entry[newCapacity];//創(chuàng)建新的table數(shù)組

????????transfer(newTable);//舊的hashMap到新的hashMap值的轉(zhuǎn)移

????????table?=?newTable;

????????threshold?=?(int)(newCapacity?*?loadFactor);

????}

?void?transfer(Entry[]?newTable)?{

????????Entry[]?src?=?table;

????????int?newCapacity?=?newTable.length;

????????for?(int?j?=?0;?j?<?src.length;?j++)?{

????????????Entry<K,V>?e?=?src[j];

????????????if?(e?!=?null)?{

????????????????src[j]?=?null;

????????????????do?{

????????????????????Entry<K,V>?next?=?e.next;

????????????????????int?i?=?indexFor(e.hash,?newCapacity);?//重新計算index

????????????????????e.next?=?newTable[i];

????????????????????newTable[i]?=?e;//頭插法插到鏈表中

????????????????????e?=?next;

????????????????}?while?(e?!=?null);

????????????}

????????}

????}

4.多線程并發(fā)的情況

在并發(fā)的情況下容易出現(xiàn)死循環(huán)

void transfer(Entry[] newTable) {

? ? ? ? Entry[] src = table;

? ? ? ? int newCapacity = newTable.length;

? ? ? ? for (int j = 0; j < src.length; j++) {

? ? ? ? ? ? Entry<K,V> e = src[j];

? ? ? ? ? ? if (e != null) {

? ? ? ? ? ? ? ? src[j] = null;

? ? ? ? ? ? ? ? do {

? ? ? ? ? ? ? ? ? ? Entry<K,V> next = e.next;//如果在線程一執(zhí)行到第9行代碼就被CPU調(diào)度掛起堰酿，去執(zhí)行線程2，且線程2把上面代碼都執(zhí)行完畢

? ? ? ? ? ? ? ? ? ? int i = indexFor(e.hash, newCapacity);

? ? ? ? ? ? ? ? ? ? e.next = newTable[i];

? ? ? ? ? ? ? ? ? ? newTable[i] = e;

? ? ? ? ? ? ? ? ? ? e = next;

? ? ? ? ? ? ? ? } while (e != null);

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ??http://www.reibang.com/p/1e9cf0ac07f4

https://www.cnblogs.com/dongguacai/p/5599100.html