什么是哈希表？

哈希表也叫散列表，它是基于數(shù)組的。這間接帶來(lái)了一個(gè)優(yōu)點(diǎn)：查找的時(shí)間復(fù)雜度為 O(1)、當(dāng)然，它的插入時(shí)間復(fù)雜度也是 O(1)。還有一個(gè)缺點(diǎn)：數(shù)組創(chuàng)建后擴(kuò)容成本較高。
哈希表中有一個(gè)“主流”思想：轉(zhuǎn)換。一個(gè)重要的概念是將「鍵」或「關(guān)鍵字」轉(zhuǎn)換成數(shù)組下標(biāo)。這由“哈希函數(shù)”完成。

什么是哈希函數(shù)？

由上，其作用就是將非 int 的鍵/關(guān)鍵字轉(zhuǎn)化為 int 的值，使可以用來(lái)做數(shù)組下標(biāo)。
比如，HashMap 中就這樣實(shí)現(xiàn)了哈希函數(shù)：

static final int hash(Object key){int h;return (key==null)?0:(h=key.hashCode())^(h>>>16); // 通過(guò)異或提高h(yuǎn)ash的“散列度”，降低沖突 }

其中利用了 hashCode 完成轉(zhuǎn)換。雖然哈希函數(shù)有很多種實(shí)現(xiàn)，但都應(yīng)當(dāng)滿足這三點(diǎn)：

• 計(jì)算得到的是非負(fù)整數(shù)；
• 如果 key1==key2，則 hash(key1)==hash(key2)；
• 如果 key1!=key2，則 hash(key1)!=hash(key2)；

并不是所有的鍵/關(guān)鍵字都需要被轉(zhuǎn)換才能做下標(biāo)（索引）

就像 JS 中也有類似的、但僅用于檢測(cè)鍵是否能用來(lái)做數(shù)組下標(biāo)的方法：JavaScript數(shù)組索引檢測(cè)中的數(shù)據(jù)類型問(wèn)題

什么是哈希沖突？

上面提到了 hashMap —— 一個(gè)java中提供的數(shù)據(jù)集。我們先來(lái)了解下：首先，hashMap 本質(zhì)上是一個(gè)容器，它為了達(dá)到快速索引的目的，使用了數(shù)組結(jié)構(gòu)“快速定位”的特性。
hashMap 中為了更快找到插入的值，建立了插入值和數(shù)組下標(biāo)的關(guān)系：pos(下標(biāo))=key(值)%size(數(shù)組大小)。

比如：數(shù)組長(zhǎng)度為10

插入100，有100%10=0；

插入201，有201%10=1；

插入403，有403%10=3；

但是如果這樣設(shè)計(jì)的話，我現(xiàn)在再插入200，會(huì)怎么樣？
這就是數(shù)組的一個(gè)缺點(diǎn)：插入特殊值比較“費(fèi)勁”。不如我們干脆將數(shù)組涉及成這樣：

引入鏈表特性，一個(gè)節(jié)點(diǎn)就包括一個(gè)值和一個(gè)next指針。

現(xiàn)在再插入上面那些值，就變成了這樣：

這時(shí)候如果再插入值300，怎么做？

類似這樣（當(dāng)兩個(gè)或以上的key的pos相同，且key不同）其實(shí)就是我們提到的“hash沖突”，而 hashMap 中解決hash沖突的方法就是上面說(shuō)的“單鏈表”！
但是這又有一個(gè)問(wèn)題：雖然用有序鏈表的方式可以減少不成功的查找時(shí)間(因?yàn)橹灰幸豁?xiàng)比查找值大，就說(shuō)明沒(méi)有我們需要查找的值)，但是不能加快成功的查找。如果沖突的鏈表太長(zhǎng)，則鏈表查找時(shí)需要從“頭”遍歷的劣勢(shì)就暴露出來(lái)了 —— 針對(duì)這個(gè)問(wèn)題，JDK1.8后用 紅黑樹 做了優(yōu)化！

但是我們先撇開(kāi)紅黑樹，用單鏈表的形式說(shuō)明一下哈希表的操作：

/*** 鏈表基類：鏈表法解決哈希沖突用的是有序鏈表！ */ public class SortedLinkList {private Link first;public SortedLinkList(){first = null;}/*** 鏈表插入* @param link*/public void insert(Link link){int key = link.getKey();Link previous = null;Link current = first;while (current!=null && key >current.getKey()){previous = current;current = current.next;}if (previous == null)first = link;elseprevious.next = link;link.next = current;}/*** 鏈表刪除* @param key*/public void delete(int key){Link previous = null;Link current = first;while (current !=null && key !=current.getKey()){previous = current;current = current.next;}if (previous == null)first = first.next;elseprevious.next = current.next;}/*** 鏈表查找* @param key* @return*/public Link find(int key){Link current = first;while (current !=null && current.getKey() <=key){if (current.getKey() == key){return current;}current = current.next;}return null;} }

鏈表法哈希表插入：

public void insert(int data) {Link link = new Link(data);int key = link.getKey();int hashVal = hash(key);array[hashVal].insert(link); }

鏈表法哈希表查找：

public Link find(int key) {int hashVal = hash(key);return array[hashVal].find(key); }

鏈表法哈希表刪除：

public void delete(int key) {int hashVal = hash(key);array[hashVal].delete(key); }

---

除了鏈表法，解決哈希沖突還有一個(gè)方法：開(kāi)放尋址法。
在開(kāi)放地址法中，若數(shù)據(jù)不能直接存放在哈希函數(shù)計(jì)算出來(lái)的數(shù)組下標(biāo)時(shí)，就需要尋找其他位置來(lái)存放。在開(kāi)放地址法中有三種方式來(lái)尋找其他的位置，分別是

• 線性探測(cè)
• 二次探測(cè)
• 再哈希法

總結(jié)

以上是生活随笔為你收集整理的三问了解哈希表和哈希冲突的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。