Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.
基于Map接口實現(xiàn)、允許null鍵/值砚作、非同步蛤袒、不保證有序(比如插入的順序)、也不保證序不隨時間變化膜赃。
hash函數(shù)的實現(xiàn)
通過hash的方法，通過put和get存儲和獲取對象揉忘。存儲對象時跳座，我們將K/V傳給put方法時端铛，它調(diào)用hashCode計算hash從而得到bucket位置，進一步存儲疲眷，HashMap會根據(jù)當(dāng)前bucket的占用情況自動調(diào)整容量(超過Load Facotr則resize為原來的2倍)禾蚕。獲取對象時，我們將K傳給get狂丝，它調(diào)用hashCode計算hash從而得到bucket位置换淆，并進一步調(diào)用equals()方法確定鍵值對。如果發(fā)生碰撞的時候几颜，Hashmap通過鏈表將產(chǎn)生碰撞沖突的元素組織起來倍试，在Java 8中，如果一個bucket中碰撞沖突的元素超過某個限制(默認(rèn)是8)蛋哭，則使用紅黑樹來替換鏈表易猫，從而提高速度。
put 函數(shù)的實現(xiàn) 思路
1具壮，對key 的hashCode（）做hash 然后再計算index
2准颓，如果沒用碰撞直接放到bucket
3，如果碰撞了 棺妓，以鏈表的形式存在buckets
4攘已，如果碰撞導(dǎo)致鏈表過長 就把鏈表轉(zhuǎn)換成紅黑樹
5，如果節(jié)點已經(jīng)存在就替換old value（保證key 的唯一性）
6怜跑， 如果bucket 滿了 （超過load factory * current capacity） 就resize
get 函數(shù)的實現(xiàn)
1样勃，bucket 里的第一個節(jié)點 直接命中
2，如果有沖突 性芬，則通過key.equals(k) 去查找對應(yīng)的entry
若為樹 則在樹種通過 key.equals(k) o(logn)
若為鏈表 峡眶，則在鏈表中通過 key.equals(k) 查找 ，o(n)
hash的實現(xiàn)
在Java 1.8的實現(xiàn)中植锉，是通過hashCode()的高16位異或低16位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)辫樱，主要是從速度、功效俊庇、質(zhì)量來考慮的狮暑，這么做可以在bucket的n比較小的時候，也能保證考慮到高低bit都參與到hash的計算中辉饱，同時不會有太大的開銷搬男。
