1. HashMap底層的數(shù)據(jù)結(jié)構(gòu)是什么？
1.8 數(shù)組+鏈表+紅黑樹
2. JDK 1.8中對hash算法和尋址算法是如何優(yōu)化的？
hash算法優(yōu)化
// JDK 1.8以后的HashMap里面hash源碼
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
比如說：有一個key的hash值
1111 1111 1111 1111 1111 1010 0111 1100
0000 0000 0000 0000 1111 1111 1111 1111
1111 1111 1111 1111 0000 0101 1000 0011 -> int值，32位
hash值一樣 -> 他們其實都會在數(shù)組里放在一個位置，進(jìn)行復(fù)雜的hash沖突的處理
[16個元素] -> hash值對數(shù)組長度取模，定位到數(shù)組的一個位置，塞進(jìn)去就ok了
高低16位都參與運算
尋址算法優(yōu)化
(n - 1) & hash -> 數(shù)組里的一個位置
1111 1111 1111 1111 1111 1010 0111 1100（沒有經(jīng)過優(yōu)化的hash值）
0000 0000 0000 0000 0000 0000 0000 1111
取模運算，他是性能比較差一些，為了優(yōu)化這個數(shù)組尋址的過程
hash & (n - 1) -> 效果是跟hash對n取模，效果是一樣的，但是與運算的性能要比hash對n取模要高很多，數(shù)學(xué)問題，數(shù)組的長度會一直是2的n次方，只要他保持?jǐn)?shù)組長度是2的n次方
hash對n取模的效果 -> hash & (n - 1)，效果是一樣的，后者的性能更高
1111 1111 1111 1111 1111 1010 0111 1100（沒有經(jīng)過優(yōu)化的hash值）
0000 0000 0000 0000 0000 0000 0000 1111
相當(dāng)于，你直接這么搞，高16位之間的與運算，是可以忽略的，核心點在于低16位的與運算，hash值的高16位沒有參與到與運算里來啊
假設(shè)有兩個hash值
1111 1111 1111 1111 1111 1010 0111 1100 -> 1111 1111 1111 1111 0000 0101 1000 0011
1111 1111 1111 1110 1111 1010 0111 1100 -> 1111 1111 1111 1110 0000 0101 1000 0010
1111 1111 1111 1111 0000 0101 1000 0011（經(jīng)過優(yōu)化和二進(jìn)制位運算的新的hash值）
0000 0000 0000 0000 0000 0000 0000 1111
配合起來講
hash算法的優(yōu)化：對每個hash值，在他的低16位中，讓高低16位進(jìn)行了異或，讓他的低16位同時保持了高低16位的特征，盡量避免一些hash值后續(xù)出現(xiàn)沖突，大家可能會進(jìn)入數(shù)組的同一個位置。
尋址算法的優(yōu)化：用與運算替代取模，提升性能
3. HashMap是如何解決hash碰撞問題的嗎？
hash沖突問題，鏈表+紅黑樹，O(n)和O(logn)
map.put和map.get -> hash算法優(yōu)化（避免hash沖突），尋址性能優(yōu)化
算出key的hash值，到數(shù)組中尋址，找到一個位置，把key-value對放進(jìn)數(shù)組，或者從數(shù)組里取出來
兩個key，多個key，他們算出來的hash的值，與n-1，與運算之后，發(fā)現(xiàn)定位出來的數(shù)組的位置還是一樣的，hash碰撞，hash沖突。
還有一個重要的原因是:hash值與n-1與運算，實際上高16為并沒有參與運算，原因是n-1的高16為都是0,和hash的高16位進(jìn)行與運算的時候，都為0.
[<> -> <> -> <>, ]
array[0]這個位置，就是一個鏈表
會在這個位置掛一個鏈表，這個鏈表里面放入多個元素，讓多個key-value對，同時放在數(shù)組的一個位置里
get，如果定位到數(shù)組里發(fā)現(xiàn)這個位置掛了一個鏈表，此時遍歷鏈表，從里面找到自己的要找的那個key-value對就可以了
假設(shè)你的鏈表很長，可能會導(dǎo)致遍歷鏈表，性能會比較差，O(n)
優(yōu)化，如果鏈表的長度達(dá)到了一定的長度之后，其實會把鏈表轉(zhuǎn)換為紅黑樹，遍歷一顆紅黑樹找一個元素，此時O(logn)，性能會比鏈表高一些。
說說HashMap是如何進(jìn)行擴容的可以嗎？
底層是一個數(shù)組，當(dāng)這個數(shù)組滿了之后，他就會自動進(jìn)行擴容，變成一個更大的數(shù)組，讓你在里面可以去放更多的元素
2倍擴容
[16位的數(shù)組，<> -> <> -> <>]
[32位的數(shù)組，<> -> <>, <>]
數(shù)組長度=16
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
&結(jié)果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
n - 1 0000 0000 0000 0000 0000 0000 0000 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
&結(jié)果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
在數(shù)組長度為16的時候，他們兩個hash值的位置是一樣的，用鏈表來處理，出現(xiàn)一個hash沖突的問題
如果數(shù)組的長度擴容之后 = 32，重新對每個hash值進(jìn)行尋址，也就是用每個hash值跟新數(shù)組的length - 1進(jìn)行與操作
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
&結(jié)果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
&結(jié)果 0000 0000 0000 0000 0000 0000 0001 0101 = 21（index = 21的位置）
判斷二進(jìn)制結(jié)果中是否多出一個bit的1，如果沒多，那么就是原來的index，如果多了出來，那么就是index + oldCap，通過這個方式，就避免了rehash的時候，用每個hash對新數(shù)組.length取模，取模性能不高，位運算的性能比較高
