hash是什么？

hash也稱為散列，就是把任意長度的輸入，通過散列算法，變成固定長度的輸出，這個輸出值就是散列值。

舉例來說明一下什么是hash：

假設我們要把1~12存入到一個大小是5的hash表中，我們就是用index=number%5的公式去計算索引存入數據

hash是一個神奇的數據結構，可以以接近O(1)的時間復雜度去進行查詢

但是很快我們就會發現一個問題，就是相同的余數的值儲存在同一個索引下，這樣就會造成一個問題，比如我查詢8是否存儲在結構中，我們能直接訪問array[3]這個位置，里面存儲8，會返回給我們的一個true，然后如果我們想要查詢13是否存在該結構中，還是會去array[3]中查找，發現里面沒存有數據13，返回false

如何解決hash沖突？

首先，先來說一下哈希沖突，哈希沖突（Hash Collision）是指在使用哈希表存儲數據時，兩個或多個不同的鍵（Key）被哈希函數映射到同一個位置的情況。這種情況會導致數據的存儲和查找變得復雜，因此需要采取一些措施來解決哈希沖突。

解決hash沖突的方法：

1.拉鏈法:

鏈地址法是一種處理哈希沖突的方法，它是將所有散列到同一個地址的數據項存儲在一個單鏈表中。這樣，當查找某個數據項時，只需要在對應的鏈表中進行搜索即可。例如，HashMap 在解決存儲對象存在 hash 沖突的問題時，采用的就是鏈地址法，將相同 hash 值的對象以鏈表的形式進行存儲。

2.再hash法

在發生沖突的時候，再用另一個哈希函數算出哈希值，直到算出的哈希值不同為止。

3.線性探測

就是發生hash沖突時，往后面繼續去找空的地方，找到后把沖突的值放到空的散列值的里面。

hashmap源碼

Ctrl+鼠標左鍵點進去

先來看一下hash這個方法

定義了一個h，如果key==null那么就返回0作為hash值，如果不等于null，那么首先把h無符號右移16位相當于保留了原哈希碼的高16位，并將它們放在低16位的位置（同時丟棄了原始的低16位）。然后，這個右移后的值與原始的哈希碼進行異或操作。異或操作的一個特性是，任何數與0異或都保持不變，而與自身異或則結果為0。這種變換有助于將哈希碼的不同部分混合在一起，從而增加哈希值的分布范圍，減少哈希沖突的可能性。這個稱之為一次擾動，每運算一次就算作一次擾動，就是為了讓hash碼的每一位都參與運算并減少沖突。

hash這個函數就是給一個對象經過一個算法處理返回一串數字作為hash碼。

然后我們回過來看putVal函數

首先是判斷table是否為空；如果是空的話，先進行一個初始化

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)//如果數組中這個位置是空的，那么直接創建一個新的點把key，hash，value裝進去tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) //先判斷我們取得的hash值和p的這個hash值是不是一樣如果一樣再開始判定key是不是一樣，判斷key相等的時候先判斷兩個key==，再判斷兩個key的值是不是一樣，如果一樣就令e=pe = p;else if (p instanceof TreeNode)//如果是樹結點就把樹結點按照樹結點的方式傳上去e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//如果一開始的頭不一樣//循環遍歷結點的鏈表//如果判斷為空就在尾部插一個結點for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//一旦發現有相等的就直接跳出循環if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//如果e不是空的，那就直接把這個值賦給老的，就是說當兩次put操作的key相等的時候后面put的值會覆蓋前面put的值if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

1.如果hashmap是空的話，也就是它內部的table數組是null，在添加第一個元素的時候會進行初始化，為table分配內存空間，設置初始容量為16，和加載因子0.75

2.對要插入的鍵，計算hash值，拿到hash值之后使用hash值得與table數組的長度來確定該鍵的存儲位置，萬一出現了產生相同的hash值的情況下，hashmap采用鏈表或紅黑樹（鏈表大于8的時候用紅黑樹）。如果該桶中沒有元素就直接創建一個新的結點，如果不是空就遍歷鏈表或者紅黑樹，查找是否存在相同的鍵，存在相同的鍵就用新的鍵代替舊的鍵，如果不存在就將新的結點添加到末尾，（紅黑樹就按紅黑樹規則插入）