關鍵字：get，put，紅黑樹，自動擴容，數(shù)組，鏈表
在看完spring之后才知道HashMap使用的有多頻繁，spring兩個特性，面向切面編程，面向內(nèi)存編程(并不，是控制反轉）。
控制反轉就是將類初始化，儲存在內(nèi)存中，以HashMap的形式。
底層原理
hashMap中get是如何實現(xiàn)的？
怎么樣通過get直接找到值？程序運行就3件事，循環(huán)/分叉/按順序，
先猜一下，key應該是有一個單獨存儲的空間，循環(huán)key找到要get的那個key，然后怎么拿到值？（這是MySQL索引的原理，MySQL用到的B+tree也是一種平衡二叉樹）
并不是！key沒有獨立空間。
先計算key的hash
tab[hash]直接拿到HashMap中這個hash下標的值
鏈表就是遍歷所有鍵值對，用==或equals來比對鍵，然后拿值；看上去挺粗暴的。
當然其中還有很多非空，長度的判斷，還有是否紅黑樹的判斷。
一些小問題
數(shù)組是怎么查詢的？
數(shù)組可以隨機訪問，這是數(shù)組的一大特點，它不需要從0數(shù)起；因為數(shù)組是先申請一塊連續(xù)空間（所以數(shù)組定長），所以儲存空間是連續(xù)的，tab[3]就直接訪問第4個值，而不需要遍歷前面的幾個值。
為什么用鏈表？
鏈表可以申請不連續(xù)的空間，通過一個指針按順序將這些空間串起來。數(shù)組是定長的，鏈表不是。鏈表的檢索能力偏弱（只能遍歷），作為彌補，它在動態(tài)調整上會更容易。這也是為什么要用紅黑樹的原因，為了查詢快。
集合也是可變的，為什么不用集合？
ArrayList底層由數(shù)組實現(xiàn)；集合中的數(shù)組默認是10的容量，在調用add方法時如果容量已滿，會將數(shù)組的容量擴大1.5倍的容量。
其他的所有儲存方式也只不過是數(shù)組和鏈表的組合和變化。
紅黑樹
hashMap有兩種儲存方式，一種是鏈表，數(shù)據(jù)多了就會轉紅黑樹。
紅黑樹怎么查詢呢？看這個結構就是要做2分查找了，確實數(shù)據(jù)多了比for循環(huán)快很多很多。
這看上去應該是有序的，key是怎么排序的？字符串是通過ASCII碼比較大小。
為什么要叫紅黑？不是為了好看，還是有意義的。為了確保樹的平衡
1.根節(jié)點是黑的。
2.葉子節(jié)點也是黑的（指的是NIL/null）。
3.紅色節(jié)點不能連續(xù)，父節(jié)點/子節(jié)點都必須是黑的。
4.從任一節(jié)點到其子樹中每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點。（這個很神奇，數(shù)一下還是真的）
5.新加入到紅黑樹的節(jié)點為紅色節(jié)點。（如果加到紅色節(jié)點下就需要調整了）
每個節(jié)點都只能有兩個子節(jié)點（因為是二叉樹）。
hashMap中put是如何實現(xiàn)的？
先計算key的hash值，找到tab[hash]的值，
鏈表就沒什么好說的，遍歷鏈表，key存在就覆蓋值，不存在就新增；主要說紅黑樹的put。
這個紅黑樹樹的結構要保持平衡（是一種平衡二叉樹），子節(jié)點高度要一致。
所有put還是需要技巧的，不能隨便插入；
如果插入的數(shù)據(jù)導致樹不符合上面的規(guī)則，就會開始變色和旋轉；
直到調整到符合上面的規(guī)則，符合規(guī)則后樹又剛好平衡了。
等我看完算法導論再來自己說說。
自動擴容
什么時候擴容？
負載因子默認是0.75，就是容量達到3/4的時候會擴容。
擴容多少？
擴大一倍。
怎么樣擴容？
原來是新建一個更大的數(shù)組，在轉移過去。同時hash算法也會發(fā)生變化，因為開始只能最大生成15的值，擴容之后可以生成到31。
相關hash算法估計和nginx負載均衡用的hash類似，hash（key）%16，這樣他永遠不會超過16。
怪不得網(wǎng)易的面試官會問我數(shù)組怎么擴容？數(shù)組怎么能擴容，幸好機制的我還是猜到了這個方法。
一些構不成問題的疑問
擴容是只擴容數(shù)組，所以鏈表和紅黑樹里數(shù)據(jù)多少都不會觸發(fā)擴容？
并不！是鍵值對的個數(shù)觸發(fā)的。也就是tab[0]的紅黑樹里有12個數(shù)據(jù)，tab數(shù)組其他位置下一個數(shù)據(jù)也沒有，也會觸發(fā)擴容。
這樣的機制下，紅黑樹出現(xiàn)的幾率不高?。。ㄦ湵碇荡笥?個轉紅黑樹，低了還會變回鏈表）
如果紅黑樹里數(shù)據(jù)很多，擴容之后更新hash算法，分散了數(shù)據(jù)后，又達到擴容要求，那就要連續(xù)擴容了?
好像也不會，觸發(fā)擴容的那個值所在的位置一定沒有hash沖突。所以不會連續(xù)觸發(fā)擴容。
考慮到擴容時紅黑樹也要重組，擴容是個比較消耗資源的操作。
hash是什么?
散列，把任意長度的字符經(jīng)過hash算法都能生成相同長度的輸出。hashMap中應該是把key散列成數(shù)字，這樣就可以組成數(shù)組下標。
hashmap和hashtable
//todo
treeMap怎么排序？
//todo
