hashmap的hash演算法

① HashMap底層實現原理剖析

Hashmap是一種非常常用的、應用廣泛的數據類型，最近研究到相關的內容，就正好復習一下。網上關於hashmap的文章很多，但到底是自己學習的總結，就發出來跟大家一起分享，一起討論。

1.HashMap的數據結構：在java 中 數據結構，最基本 也就兩種 一種數組 一種模擬指針。所有的數據結構都可以用這兩個基本結構來構造的，hashmap也不例外。Hashmap實際上是一個數組和鏈表的結合體。數組的默認長度為16，

2.hashMap源碼解析

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化容量大小 

static final int MAXIMUM_CAPACITY = 1 << 30; ///容器最大值

static final float DEFAULT_LOAD_FACTOR = 0.75f; //載入影子

static final Entry[] EMPTY_TABLE = {}; //null 的hashMap

transient Entry[] table = (Entry[]) EMPTY_TABLE;///動態擴大容器時使用的一個hashMap

transient int size;//當前數據量

int threshold;//擴大容器時的大小 為 capacity * load factor

final float loadFactor;//使用率閥值，默認為：DEFAULT_LOAD_FACTOR

存取元素 ：調用put方法

public V put(K key, V value) { 

//判斷當前table 為Null 第一次Put 

 if (table == EMPTY_TABLE) {

     inflateTable(threshold);  //初始化容器的大小

 }

 if (key == null) 

 return putForNullKey(value); //判斷當前key 為null 將Null key添加到數組的第一個位置

 int hash = hash(key); //將當前key進行hash 詳情見下方

 int i = indexFor(hash, table.length); //調用完hash演算法後，詳情見下方

 for (Entry e = table[i]; e != null; e = e.next) { //循環判斷當前數組下標為Entry的實體 將當前key相同的替換為最新的值

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(hash, key, value, i); //如果key都不同 則添加Entry.詳情見下方

        return null;

    }

hashMap的hash演算法剖析

final int hash(Object k) {

        int h = hashSeed;

        if (0 != h && k instanceof String) {  //判斷當前k是否為string 和

            return sun.misc.Hashing.stringHash32((String) k); //使用stringHash32演算法得出key   的hash值

        }

        h ^= k.hashCode(); //調用key的hashCode 得出值 後使用"或"運算符 

        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

前面說過HashMap的數據結構是數組和鏈表的結合，所以我們當然希望這個HashMap裡面的 元素位置盡量的分布均勻些，盡量使得每個位置上的元素數量只有一個，那麼當我們用hash演算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去遍歷鏈表，這樣就大大優化了查詢的效率。

一個十進制數32768(二進制1000 0000 0000 0000)，經過上述公式運算之後的結果是35080(二進制1000 1001 0000 1000)。看出來了嗎？或許這樣還看不出什麼，再舉個數字61440(二進制1111 0000 0000 0000)，運算結果是65263(二進制1111 1110 1110 1111)，現在應該很明顯了，它的目的是讓「1」變的均勻一點，散列的本意就是要盡量均勻分布。使用上述演算法後 "1"就變得很均勻了。

我們用table[index]表示已經找到的元素需要存儲的位置。先判斷該位置上有沒有元素（這個元素是HashMap內部定義的一個類Entity， 基本結構它包含三個類，key，value和指向下一個Entity的next）,沒有的話就創建一個Entity對象，在 table[index]位置上插入，這樣插入結束；如果有的話，通過鏈表的遍歷方式去逐個遍歷，看看有沒有已經存在的key，有的話用新的value替 換老的value；如果沒有，則在table[index]插入該Entity，把原來在table[index]位置上的Entity賦值給新的 Entity的next，這樣插入結束

    }

indexFor 返回當前數組下標 ，

static int indexFor(int h, int length) {

        return h & (length-1);

    }

那麼得到key 之後的hash如何得到數組下標呢 ？把h與HashMap的承載量（HashMap的默認承載量length是16，可以自動變長。在構造HashMap的時候也可以指定一個長 度。這個承載量就是上圖所描述的數組的長度。）進行邏輯與運算，即 h & (length-1)，這樣得到的結果就是一個比length小的正數，我們把這個值叫做index。其實這個index就是索引將要插入的值在數組中的 位置。第2步那個演算法的意義就是希望能夠得出均勻的index，這是HashTable的改進，HashTable中的演算法只是把key的 hashcode與length相除取余，即hash % length，這樣有可能會造成index分布不均勻。

首先來解釋一下為什麼數組大小為2的冪時hashmap訪問的性能最高？

看下圖，左邊兩組是數組長度為16（2的4次方），右邊兩組是數組長度為15。兩組的hashcode均為8和9，但是很明顯，當它們和1110「與」的時候，產生了相同的結果，也就是說它們會定位到數組中的同一個位置上去，這就產生了碰撞，8和9會被放到同一個鏈表上，那麼查詢的時候就需要遍歷這個鏈表，得到8或者9，這樣就降低了查詢的效率。同時，我們也可以發現，當數組長度為15的時候，hashcode的值會與14（1110）進行「與」，那麼最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數組可以使用的位置比數組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率！ 

void addEntry(int hash, K key, V value, int bucketIndex) {

  //// 若HashMap的實際大小 不小於 「閾值」，則調整HashMap的大小

        if ((size >= threshold) && (null != table[bucketIndex])) {

            resize(2 * table.length);

            hash = (null != key) ? hash(key) : 0;

          //// 設置「bucketIndex」位置的元素為「新Entry」，// 設置「e」為「新Entry的下一個節點」

            bucketIndex = indexFor(hash, table.length);

        }

        createEntry(hash, key, value, bucketIndex);

    }

//將當前key 和value添加到Entry[]中

void createEntry(int hash, K key, V value, int bucketIndex) { 

        Entry e = table[bucketIndex];  //將第一個就得table 復制個新的entry 

        table[bucketIndex] = new Entry<>(hash, key, value, e); //將當前新的Entry 復制個table[bucketIndex]  舊的table[bucketIndex] 和新的table[buckIndex]之間用next關聯。第一個鍵值對A進來，通過計算其key的hash得到的index=0，記做:table[0] = A。一會後又進來一個鍵值對B，通過計算其index也等於0，現在怎麼辦？HashMap會這樣做: B.next = A ,table[0] = B,如果又進來C,index也等於0,那麼 C.next = B ,table[0] = C；這樣我們發現index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起

        size++; //容量加1

    }

以上就是HashMap添加元素時的過程解析

那麼如何get元素呢？

public V get(Object key) {

 if (key == null) return getForNullKey(); //當前key是否為null 如果為null值返回table[0]這個value

    Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();

    }

final EntrygetEntry(Object key) {

 if (size == 0) { return null; }  //判斷容量是否大於0 

 int hash = (key == null) ? 0 : hash(key); //對當前key 進行hash hash後得到一個值

 for (Entry e = table[indexFor(hash, table.length)]; //獲取當前Entry 循環遍歷

            e != null;

            e = e.next) {

            Object k;

            if (e.hash == hash &&

                ((k = e.key) == key || (key != null && key.equals(k))))

                return e;

        }

        return null;

    }

擴展問題:

1.當前我們的hashMap中越來越大的之後，"碰撞"就越來越明顯，那麼如何解決碰撞呢？擴容！

當hashmap中的元素個數超過數組大小capti*loadFactor時，就會進行數組擴容，loadFactor的默認值為0.75，也就是說，默認情況下，數組大小為16，那麼當hashmap中元素個數超過16*0.75=12的時候，就把數組的大小擴展為2*16=32，即擴大一倍，然後重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知hashmap中元素的個數，那麼預設元素的個數能夠有效的提高hashmap的性能。比如說，我們有1000個元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合適，不過上面annegu已經說過，即使是1000，hashmap也自動會將其設置為1024。 但是new HashMap(1024)還不是更合適的，因為0.75*1000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合適，既考慮了&的問題，也避免了resize的問題

HashMap的兩種遍歷方式

第一種

Map map = newHashMap();

Iterator iter = map.entrySet().iterator();

while(iter.hasNext()) {

Map.Entry entry = (Map.Entry) iter.next();

Object key = entry.getKey();

Object val = entry.getValue();

}

效率高,以後一定要使用此種方式！

第二種

Map map = newHashMap();

Iterator iter = map.keySet().iterator();

while(iter.hasNext()) {

Object key = iter.next();

Object val = map.get(key);

}

效率低,以後盡量少使用！

歸納

簡單地說，HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層採用一個 Entry[] 數組來保存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據hash演算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的鏈表中的存儲位置；當需要取出一個Entry時，

也會根據hash演算法找到其在數組中的存儲位置，再根據equals方法從該位置上的鏈表中取出該Entry。

② 面試中如何回答HashMap的工作原理

用過哪些Map類，都有什麼區別，HashMap是線程安全的嗎,並發下使用的Map是什麼，他們
內部原理分別是什麼，比如存儲方式，hashcode，擴容，默認容量等。
JAVA8的ConcurrentHashMap為什麼放棄了分段鎖，有什麼問題嗎，如果你來設計，你如何
設計。
有沒有有順序的Map實現類，如果有，他們是怎麼保證有序的。

hashmap的實現原理，https://blog.csdn.net/mbshqqb/article/details/79799009

下面是自己的總結:

存儲結構:
裡面存儲的是一個entry數組，每個數組元素中的結構是一個entry鏈表
Entry是map中的一個靜態內部類，其中的變數有:key,value,hashcocd,下一個Entry

什麼是hash？
又稱散列，將任意長度的輸入通過散列演算法轉換成固定長度的輸出，該輸出就是散列值。這是一種壓縮映射，散列值的空間通常遠小於輸出的空間。不同的輸入有可能會散列出相同的輸出，因此不能從散列值來確定唯一的輸入值。這也是為什麼比較兩個對象不能僅僅使用hashcode方法比較的原因。

hash碰撞:
對不同的值進行hash運算生成了相同的散列值。這個是不可避免的，但是我們需要盡量的減少其帶來的損失。
(1)設計好的hash演算法讓其盡可能的分布均勻
hashmap中的hash演算法解析
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
讓key的hashcode本身與它右移16位異或，是為了讓它的高位與低位混合，增加低位的隨機性，同時也變相保持了高位的特徵

計算元素位置的演算法:
int index = hash & (arrays.length-1);
那麼這也就明白了為什麼HashMap的數組長度是2的整數冪。比如以初始長度為16為例，16-1 = 15，15的二進制數位00000000 00000000 00001111。可以看出一個基數二進制最後一位必然位1，當與一個hash值進行與運算時，最後一位可能是0也可能是1。但偶數與一個hash值進行與運算最後一位必然為0，造成有些位置永遠映射不上值。

對於null值的處理
hashmap是接受null值的，null值被放在數組的第一個元素當中，取出來的時候怎麼處理呢？

hashmap的工作原理？
它的裡面有一個Entry數組，在put時我們先根據key值計算出hashcode，進而計算出該元素在數組中的位置，將健值對封裝在Map.Entry對象中，然後存儲在數組中

若產生hash沖突怎麼辦？
每個數組元素的位置都是一個鏈表結構，若計算出來的hashcode相同則將元素追加到該鏈表當中，這是hashmap的處理方式

在取元素的時候，先計算key值對應的hashcode ，找到元素所在的位置，然後調用key的equals方法去遍歷鏈表，最後找到元素

還有哪些解決hash沖突的方法？
開放定址法
這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H（key）出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。
再哈希法
這種方法是同時構造多個不同的哈希函數：
Hi=RH1（key） i=1，2，…，k
當哈希地址Hi=RH1（key）發生沖突時，再計算Hi=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。
鏈地址法
這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，並將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用於經常進行插入和刪除的情況。
建立公共溢出區
這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表。

默認的負載因子0.75
當map的大小超過當前容量的百分之75時會進行自動擴容，會將原來的對象重新放到新的數組中

rehash 的過程是什麼樣子的？
說白了就是先resize，生成一個新的Entry數組，再transfer將原數組中的值重新計算index放入新的數組中，然後改變閾值為新的長度x負載因子

如果key為null，這始終會被散列到table[0]的桶中，即使是rehash的過程也是一樣。非null的key也有可能會被散列到table[0]的位置，例如上圖中key=「f」，而且相同的key在在不同的時間可能會被散列到不同的位置，這與rehash有關。

這個過程中容易發生什麼問題呢？
容易產生條件競爭，如果在擴容的過程中put數據，會造成意想不到的結果。或者如果兩個線程都觸發了擴容，也會存在問題

這塊有沒有遇到過什麼比較好的例子？

jdk1.8以後改成了紅黑樹，為什麼？說一下紅黑樹的原理？

hashmap與hashtable的區別？
HashTable和HashMap的實現原理幾乎一樣，差別無非是
HashTable不允許key和value為null
HashTable是線程安全的
但是HashTable線程安全的策略實現代價卻太大了，簡單粗暴，get/put所有相關操作都是synchronized的，這相當於給整個哈希表加了一把大鎖。
多線程訪問時候，只要有一個線程訪問或操作該對象，那其他線程只能阻塞，相當於將所有的操作串列化，在競爭激烈的並發場景中性能就會非常差。

篇幅有限，未完待續

③ HashMap是什麼東西

HashMap，中文名哈希映射，HashMap是一個用於存儲Key-Value鍵值對的集合，每一個鍵值對也叫做Entry。這些個鍵值對（Entry）分散存儲在一個數組當中，這個數組就是HashMap的主幹。HashMap數組每一個元素的初始值都是Null。

HashMap是基於哈希表的 Map 介面的實現。此實現提供所有可選的映射操作，並允許使用 null 值和 null 鍵。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序，特別是它不保證該順序恆久不變。

(3)hashmap的hash演算法擴展閱讀：

因為HashMap的長度是有限的，當插入的Entry越來越多時，再完美的Hash函數也難免會出現index沖突的情況。

HashMap數組的每一個元素不止是一個Entry對象，也是一個鏈表的頭節點。每一個Entry對象通過Next指針指向它的下一個Entry節點。當新來的Entry映射到沖突的數組位置時，只需要插入到對應的鏈表即可。