提到哈希，我們腦袋中立馬就會閃過一個方法，就是hashCode()，沒錯，就是這個！
我們知道HashMap是通過 陣列+鏈表 的結構進行資料存盤的，有陣列就會有索引，而HashMap內的資料要存盤在哪塊索引上，則是基于HashMap內部的hash方法計算出來的，
我們常用的 get put 也離不開這個 hash 方法，
我們先從hash方法入手！
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
首先通過 hashCode() 方法得到 h ，然后在把 h 無符號右移16位，最后通過異或演算法得到hash值，我們找個key展開運算一下
假設有一個key
String key = "hello world";
那么這個key的hashCode的二進制為
0110 1010 1110 1111 1110 0010 1100 0100
然后把這個二進制資料向右無符號移動16位，得到如下
0000 0000 0000 0000 0110 1010 1110 1111
最后通過把高16位和低16位做異或運算均勻分布
0110 1010 1110 1111 1000 1000 0010 1011
給hash做異或運算主要還是為了降低hash沖突的概率（這個是查閱資料得知的）
我們說完hash的運算程序后，看一下HashMap里邊都是哪里有用到吧
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
這三個方法，算是HashMap內最常用的三個方法了，可以看到從應用層傳遞進來的key全部都經過了hash(key)而比較細心的朋友們還會發現HashMap內陣列的索引，是通過 i = (n - 1) & hash 計算得出的
我們接下來在展開一下索引計算公式
n是HashMap內的哈希表的長度，默認是16，每次擴容都是一倍一倍的擴容，就是 16 << 1 ，我們拿16來展開運算，而hash用上面的key來繼續運算
i = (16 - 1) & hash
15的二進制結果是
0000 0000 0000 0000 0000 0000 0000 1111
hash的再拿過來用吧～（十進制：1794082859）
0110 1010 1110 1111 1000 1000 0010 1011
在通過&運算，可以得到（十進制：11）
0000 0000 0000 0000 0000 0000 0000 1011
十進制計算：
1794082859 & 15 = 11
1794082859 % 16 = 11
首先n在HashMap里的設定是永遠都是2次冪，因為 2次冪 & hash(key) 等價于 hash(key) % n
而眾所周知，& 比 % 效率要高10倍的，
但這個公式只有 n 是2次冪的時候才成立，所以才有了2次冪的設定，
HashMap的索引都是通過這個演算法得出來的，所以HashMap查找起來特別快～
好了，通過這篇文章，大家應該也對HashMap的hash有點概念了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/25903.html
標籤：Java
上一篇：為什么我的答案對了卻wa
下一篇：檔案夾 壓縮原理