問題導(dǎo)入：
?HashMap底層數(shù)據(jù)結(jié)構(gòu)，如何處理hash沖突，為何HashMap的大小要設(shè)置為2的n次冪，為什么IndexFor方法里，需要hash&length-1，為什么HashMap允許null值，resize()過程，多線程下resize為什么會(huì)出現(xiàn)死循環(huán)？
1. HashMap的底層數(shù)據(jù)結(jié)構(gòu)
? ? ? ? ?Hash采用的是鏈地址法(數(shù)組+鏈表)解決hash沖突問題(無外乎在取值和存值的時(shí)候，key會(huì)不會(huì)沖突)，其中在hashMap內(nèi)部定義了一個(gè)靜態(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)建一個(gè)Entry[] table = new Entry[DEFAULT_INITIAL_CAPACITY?];我們重點(diǎn)講解的是第一種情況，隨機(jī)定義一個(gè)初始化的容量，
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è)計(jì)數(shù)組的長度2的n次冪：其實(shí)為了更好的解決hash沖突
3. HashMap的存取
? 從? get(key)， put(key,value)入手，這兩個(gè)容易發(fā)生hash沖突的地方，沖突主要是key的定位
存儲(chǔ)時(shí):
?int?hash?=?hash(key.hashCode());//先計(jì)算key的hashCode，然后再hash
?int?i?=?indexFor(hash,?table.length);//定位到具體的table數(shù)組中
取值時(shí):
?int?hash?=?hash(key.hashCode());//先計(jì)算key的hashCode，然后再hash
?int?i?=?indexFor(hash,?table.length);//定位到具體的table數(shù)組中
?Entry[i];
3.1 put(key,value)的詳解
? ? ? 當(dāng)存入值的時(shí)候，先計(jì)算key的hashCode,然后再hash，然后通過indexFor()定位到具體的table數(shù)組中，這時(shí)候出現(xiàn)當(dāng)多個(gè)key定位到數(shù)組的同一個(gè)位置，先遍歷該位置上的鏈表，判斷有沒有key相同,如果有的話，更新對應(yīng)key的value,如果沒有插入到頭節(jié)點(diǎn)
public?V?put(K?key,?V?value)?{
????????if?(key?==?null)
? ? ? returnputForNullKey(value);//放入null值的時(shí)候，null總是放在數(shù)組的第一個(gè)鏈表中
????????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ò)容的浪費(fèi)(用不著了)
}
3.2 get(key)
?public?V?get(Object?key)?{
????????if?(key?==?null)
????????????return?getForNullKey();//當(dāng)key為null的時(shí)候
????????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ù)組的第一個(gè)元素。
???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或者取余%。
因?yàn)閔ashMap容量的變化，我們總是將容量定位>=initCapacity的2的次冪，所以length-1,則每個(gè)位置上都是1，這樣的與運(yùn)算，可以保證均勻定位
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);?//重新計(jì)算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://m.itdecent.cn/p/1e9cf0ac07f4
https://www.cnblogs.com/dongguacai/p/5599100.html
