安卓筆記俠

用到的符號:

     ^異或運算:兩個操作數相同,結果是0;兩個操作數不同,結果是1。

     &按位與:兩個操作數都是1,結果才是1。

一、HashMap概述

     在JDK1.8之前，HashMap采用數組+鏈表實現，即使用鏈表處理沖突，同一hash值的鏈表都存儲在一個鏈表里。但是當位于一個桶中的元素較多，即hash值相等的元素較多時，通過key值依次查找的效率較低。而JDK1.8中，HashMap采用數組+鏈表+紅黑樹(二叉樹的優化實現是一種平衡二叉樹,可以降低樹的深度)實現，當鏈表長度超過閾值（8）時，將鏈表轉換為紅黑樹，這樣大大減少了查找時間。

    jdk1.8之前的hashmap都采用上圖的結構，都是基于一個數組和多個單鏈表，hash值沖突的時候，就將對應節點以鏈表的形式存儲。如果在一個鏈表中查找其中一個節點時，將會花費O（n）的查找時間，會有很大的性能損失。到了jdk1.8，當同一個hash值的節點數不小于8時，不再采用單鏈表形式存儲，而是采用紅黑樹。

二、了解Hash函數

   我們先了解一下Hash的源碼：

    代碼執行過程:如果key為空,返回0;如果key不為空,返回原hash值和原hash值無符號右移16位的值按位異或的結果。(把低16位和高16位進行異或運算）。因為低位重復概率比較大,低位和高位異或運算可以提交數組的利用率,使數組分布均勻。

    按位異或就是把兩個數按二進制，相同就取0，不同就取1。

    比如：0101 ^ 1110 的結果為 1011,異或的速度是非常快的。

   把一個數右移16位即丟棄低16為，就是任何小于216的數，右移16后結果都為0（2的16次方再右移剛好就是1）。

   任何一個數，與0按位異或的結果都是這個數本身。

   所以這個hash()函數對于非null的hash值，僅在其大于等于216的時候才會重新調整其值。

   但是調整后又什么好處呢？

   我們先看下put的時候，這個hash值是怎么處理（部分源碼）的：

    在尋找桶位的時候，這個hash值為與上table的zise-1，初始為16，我們就拿16來舉例.

    以為算法是hashValue & size - 1 ,此時size-1=15的二進制為 1 1 1 1 ，也就是任意類似16進制0x?0（二進制最后四位為0000）的hash值，都會被存儲到位置為0的桶位上，一個桶中的元素太多，就一定會降低其性能。我們知道HashMap是一個數組+鏈表，就是在下標相同的位置下面掛一個單項的鏈表,那數組的下標需要計算出來,必須保證在一定的范圍內,是通過【(n-1)&hash】計算機計算的是二進制,比如數組大小必須是2的N次冪,權重是0.75,數組初始值是16,權重等于12(16*0.75)，當等于12數組會擴容。擴容之后對數組進行重新分配。當鏈表的大小大于8的時候會轉化為紅黑樹。數組下標計算方式:(0101010101010101010101010101&00000000000000000001111)以16來說,十六進制的二進制表示后面的0,N-1的二進制結尾是1111,兩者進行與操作最大值是1111，1111的16十六進制是15,然后把Node節點放入這個位置,這樣來計算下標。

總結如下: