哈希沖突

如果兩個不同的?key?通過哈希函數得到了相同的索引，這種情況就叫做「哈希沖突」。

哈希沖突不可能避免，只能在算法層面妥善處理出現哈希沖突的情況。

哈希沖突是一定會出現的，因為這個?hash?函數相當于是把一個無窮大的空間映射到了一個有限的索引空間，所以必然會有不同的?key?映射到同一個索引上。

哈希沖突的解決辦法

出現哈希沖突的情況怎么解決？兩種常見的解決方法，一種是拉鏈法，另一種是線性探查法（也經常被叫做開放尋址法）。

就是縱向延伸和橫向延伸兩種思路：

1、拉鏈法：

拉鏈法相當于是哈希表的底層數組并不直接存儲?value?類型，而是存儲一個鏈表，當有多個不同的?key?映射到了同一個索引（節點）上，這些?key -> value?對兒就存儲在這個鏈表中，這樣就能解決哈希沖突的問題。

2、開放尋址法

而線性探查法的思路是，一個?key?發現算出來的?index?值已經被別的?key?占了，那么它就去?index + 1?的位置看看，如果還是被占了，就繼續往后找，直到找到一個空的位置為止。

比方說上圖，key 的插入順序是?k2, k4, k5, k3, k1，那么哈希表底層就會變成這樣：