kurenai
做JAVA開發的程序員們，每天都在用hashMap，可是你真的瞭解hashMap嗎？
hashMap作為一個key-value形式的數據結構，以鍵值對的方式存儲數據，下面以鏈地址法為例，簡單來說就是通過計算key的hashCode然後使用equals方法進行比較，把相同hashcode值的數放在一個桶裡(其實就是一個數組)，在一個數組中的元素又怎麼存儲呢？通過單向鏈表，一個接一個的接起來！
這是鏈地址法hashMap的圖示:
再來看個概念，大O表示法:一定量的運算所需要的時間級別！比如一串無序的數據量為N的數據，通過順序查找的方式查找某個數，找到的這個數所需要的比較次數評論為N/2，我們就用O(N)來表示查找時間為線性級別的！如果是一個數組，假設數量為500，那麼查找某個數的比較次數就一定不超過500，這樣就使用O(1)來表示這個查找是常量級的查找！
hash函數的定義往往是為了獲得更為平均的hashcode，讓key對應的value能平均分配在不同的桶裡，為什麼平均分配是最好的？我們用極限理論來舉個栗子:
假設有數量為250000(1-250000)的數據，如果按照500來取模作為hash函數，餘數為0-499的分別放在不同的500個桶裡(數組)，需要查找某個數的時候，只需要先計算餘數獲得數組下標(O(N))，再從這個數組元素(鏈表)中取出這個數即可(O(N))，就是250+250＝500次就能得到這個數，但是如果這250000個數的值都是250000，也就是說數組下標為1-499(當然這時候已經不存在了)的數組元素中都是空的，而下標為0(數組第一個元素)的鏈表個數為250000，這時候查找某個數的比較次數平均為125000，性能下降為O(N)，從O(1)-->O(N)差別很大很大！
總之，hashMap中的hash算法是為了儘量讓key分配在不同的桶裡，減少衝突的產生，如果能讓數據平均分配到桶裡，那麼hashMap的查詢將得到最大化的提升！
在JAVA8中，hashMap對於衝突問題，有了極大的性能提升，如果出現的衝突達到某個閾值(源碼中使用TREEIFY_THRESHOLD表示)，會把原來的鏈表結構動態的變為紅黑樹進行存儲，把O(N)級別的的查找變為O(logn)，性能提升不要太多。。
下面是JAVA8hashMap的圖示:
從源碼中獲取到算法和數據結構的使用，才能真正對自己掌握底層技術，和優化性能有直接作用，文中提到的紅黑樹為什麼查找快，改天會進行分享，更多的技術分享，敬請關注。。
謝逅架構
HashMap的hash函數需要衡量兩方面：降低hash衝突和儘量減少hash計算性能消耗。
HashMap插入數據時會先計算KEY的hash值，然後根據這個hash值確定數據在table中的下標。計算方法如下，用table的長度減1後與hash值進行位運算與操作，由於hashmap的長度一般不大，所以hash值參與計算的都是後面幾位，容易造成衝突。
為了減少這種衝突，HashMap的hash函數，將KEY的hashcode前16位和後16位進行異或計算，這樣會有效的降低衝突機率，同時運算量也非常小。代碼如下
希望能解答題主的疑惑。
