一：HashMap 是計算機(jī)領(lǐng)域中一種很常見并且重要的復(fù)合數(shù)據(jù)結(jié)構(gòu)。
?????? 既然是復(fù)合數(shù)據(jù)結(jié)構(gòu)，那它由那些更基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)組成呢？
?????? 1：數(shù)組（橫向的. 為了效率）
?????? 2:?? 鏈表（縱向的. 為了解決沖突）
?????? 如下圖：
數(shù)組是hashmap 數(shù)據(jù)結(jié)構(gòu)的主干。數(shù)組中每個節(jié)點(diǎn)存儲結(jié)構(gòu)是什么樣的呢？
名字叫 Entry. 里面都有什么呢？
1. key(不解釋了)
2. value(不解釋了)
3. hash(用 key 通過一種算法的得到的值)
4. next(指向下一個節(jié)點(diǎn)的指針)
假設(shè)有如下3對key,value 要存儲到hashmap 中。
????? key? value?
a.?? 小張:170
b.?? 小李:175
c.?? 小王:166
數(shù)據(jù)是如何存儲的呢？
1.? 首先拿key? 用hash算法? 得到一個 hash 值（一個int類型），然后在 用這個hash值 經(jīng)過一些列運(yùn)算, 又的到一個int值A(chǔ)。最后這個A值有那些特點(diǎn)呢？
a.? A值的范圍在HashMap數(shù)組長度之內(nèi)
b.? 不同的key 在一定概率上得到A值是不同的。(也有相同的. 這就是hash 沖突)
假設(shè)上面3個key通過計算得到的A值(不是真正計算出來的)如下
小張--->2
小李--->5
小王--->2
按如下順序存放這3對值：
1.小張:170? 存儲到數(shù)組2的位置
2.小李:175? 存儲到數(shù)組5的位置
3.小王:166? 存儲到哪里呢？ 和小張的位置重疊了啊？
小張和小王這種現(xiàn)象 叫做?? hash沖突。
沖突的時候，鏈表的作用就來了。（用來解決沖突的）
把小張和小王都放在 2的位置。用鏈表存儲它們。
還有一個問題小張和小王的位置是怎么存放的呢？
小張先存放的。自然在鏈表的頭部。
當(dāng)在存放小王的時候，是把小王放在鏈表的頭部，小張放在小王的后面。以此類推。
結(jié)論是:?? 新插入的元素放到鏈表頭部
為什么要這樣放呢？
因?yàn)樾省Ｍㄟ^數(shù)組找到這個鏈表的時候，只知道頭指針。如果要把新元素放到鏈表末尾，需要遍歷鏈表才行。如果放到頭部就不需要遍歷鏈表了。
二.? HashMap 極端情況。
1. 所有插入的元素都發(fā)生了沖突，并且算出的A值都相同。hashmap 就變成了單向鏈表。(最壞情況)
2. 所有插入的元素都沒有沖突。hashmap 就變成了一維數(shù)組（最好情況）
3.可以把hashmap 中的單向鏈表 換成其他數(shù)據(jù)結(jié)構(gòu)。如: 紅黑樹()。
4.jdk1.6-1.7 HashMap使用單向鏈表 解決沖突。jdk1.8 采用 單向鏈表+紅黑樹 解決沖突。
5.紅黑樹的引入 終極目的就是提高查詢效率。例如：最壞情況下，用紅黑樹的查找算法一定優(yōu)于鏈表的查找算法。
