?HashMap的原理和問題：
? ? ? ? ?First.? ? ? 基本原理
? ? ? ? Second. HashMap的初始長(zhǎng)度，以及原因
? ? ? ? Third.? ? ?loadFactor以及resize
? ? ? ? Fourth.? ? 高并發(fā)下的死鎖問題
First,some fundamental theory:
? ? ?1.hashMap存儲(chǔ)的是key-value的鍵值對(duì)集合。
? ? ? ?每一個(gè)鍵值對(duì)也叫Entry，Entry分散分布在一個(gè)數(shù)組里。比如說這里的hashMap的一個(gè)實(shí)例x對(duì)應(yīng)的數(shù)組a長(zhǎng)度為6.
? ? ?2.put和get方法：
? ? ? ?(1)put
? ? ? ?比如說x.put("apple",0)，就是一個(gè)Entry，記作entryOne。
? ? ? ?在放入entryOne之前，我們要知道究竟放在數(shù)組a的哪個(gè)位置。在這里要先計(jì)算index=Hash("apple")，我們暫時(shí)不管怎么計(jì)算，如果最終index=2的話，那么entryOne就放在a[2]處。
? ? ? ?那么就有一個(gè)問題，因?yàn)閍的長(zhǎng)度有限，再放入別的Entry的時(shí)候會(huì)不會(huì)和前面所放的沖突，答案是會(huì)的。此時(shí)怎么解決這個(gè)問題呢？
? ? ? ?java選擇開辟鏈表法，也就是說在發(fā)生沖突的位置用鏈表的形式存儲(chǔ)index為該位置的Entries.比如說x.put("orange",1)，index=Hash("orange")=2，把記作entryTwo。此時(shí)a[2]處的頭節(jié)點(diǎn)為entryTwo，然后entryTwo指向entryOne。至于為什么后放入的要放在頭部（頭部插入），這是因?yàn)橥虏迦氲谋辉L問的幾率更高。
? ? ? ?(2)get
? ? ? ?我們根據(jù)key，在hashMap x中找到相應(yīng)的Entry。
? ? ? ?同理，比如找“apple”，同樣計(jì)算index=Hash("apple")=2，但就在a[2]處我們發(fā)現(xiàn)了一個(gè)鏈表，依次遍歷直到找到Entry y，使得y.key==apple,或者沒找到，返回null。
Second,the initial length of capacity and the reason
? ? ? ?java的hashMap的初始長(zhǎng)度為16，2的4次方：
/*** The default initial capacity - MUST be a power of two.*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
? ? 以上是源碼的初始化，但為什么說初始的容量必須是2的冪次呢？
? ? 我們上面提到計(jì)算index=Hash("key")，具體我們是怎么計(jì)算的呢？
? ? 實(shí)際上，index=Hash("key")=HashCode("key")%length.這里HashCode("key")是key對(duì)應(yīng)的哈希碼，至于怎么產(chǎn)生的后面再介紹。
那么對(duì)于index=Hash("key")的映射函數(shù)，我們希望這個(gè)hash函數(shù)盡量分布均勻。
? ? 另外，由于取模運(yùn)算效率極低，hashMap的開發(fā)者使用的是位運(yùn)算。
? ? 有：index=HashCode(key)&(length-1);
? ? 為了具體說明，比如說apple的hashCode為xxxxxxxxxxxxx1001(高位值不影響結(jié)果)，hashMap的length初始值為16，length-1=15=1111。則，結(jié)果為1001。其實(shí)就是保留hashCode的低位，由于是&運(yùn)算，只有l(wèi)ength-1為全1時(shí)保留的最多，結(jié)果最均勻。
我們可以假設(shè)length=10，length=9=1001,xxxxxxxxxxxxx1111和xxxxxxxxxxxxx1001
結(jié)果都為1001，實(shí)際上x11x的情況根本不會(huì)出現(xiàn)。這會(huì)導(dǎo)致，hashMap的一些位置根本就沒有entry，而別的位置擠滿了entry。??
?Third.? ? ?loadFactor? and resize the hashMap
? ?我們知道哪怕再平均的hash映射函數(shù)，只要插入的數(shù)據(jù)夠多，就會(huì)影響速度，這個(gè)時(shí)候就要擴(kuò)大hashMap，我們把擴(kuò)大的過程叫做resize。另一方面，什么時(shí)候我們決定resize呢？換句話說，插入的數(shù)據(jù)多到什么程度我們r(jià)esize hashMap呢？這取決于loadFactor，在java的hashMap中取其為0.75。
/*** The load factor used when none specified in constructor.*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
至于為什么是0.75，開發(fā)者在一開始就給出了解釋：
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs.? Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put).
這是時(shí)間和空間代價(jià)的平衡點(diǎn)。
而resize所做的操作則是，在插入占到0.75以上時(shí)，HashMap使用新數(shù)組代替舊數(shù)組，對(duì)原有的元素根據(jù)hash值重新就算索引位置，重新安放所有對(duì)象。
要注意！之前的鏈表在resize之后，相當(dāng)于反序了，因?yàn)閞esize遍歷的過程從頭到尾將entry放入新的hashMap中，而且是頭部插入。
Fourth.? deadlock caused by high concurrency?
為什么高并發(fā)下hashMap容易出現(xiàn)死鎖？就是resize的問題，當(dāng)hashMap處于閾值，也就是即將被擴(kuò)容，如果此時(shí)有兩個(gè)進(jìn)程同時(shí)對(duì)其resize，因?yàn)閔ashMap是沒有加鎖機(jī)制的。因?yàn)閞esize遍歷的過程從頭到尾將entry放入新的hashMap中，而且是頭部插入。沒有鏈表存在還好，一旦有鏈表存在，極易形成環(huán)鏈。
? ? 比如說同一index下的鏈表中有a,b，進(jìn)程1此時(shí)e指向a,e.next指向b，進(jìn)程2此時(shí)e指向b,e.next指向a。如此執(zhí)行下去新的hashMap就會(huì)產(chǎn)生環(huán)鏈。
? ? 有人向Sun公司反映，然而人家說了，這本來就不是給多線程使用的，想保證線程安全自己用concurrentHashMap去。
