很多人說(shuō)起“哈希表”，就會(huì)直接聚焦到hash函數(shù)、“散列”、“雜湊”等方向，會(huì)使得初學(xué)者一頭霧水，反而更加不理解什么，下面就會(huì)系統(tǒng)的給大家介紹一下什么是“哈希表”。

哈希表又稱(chēng)散列表，一種以「key-value」形式存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。所謂以「key-value」形式存儲(chǔ)數(shù)據(jù)，是指任意的鍵值 key 都唯一對(duì)應(yīng)到內(nèi)存中的某個(gè)位置。只需要輸入查找的鍵值，就可以快速地找到其對(duì)應(yīng)的 value?？梢园压１砝斫鉃橐环N高級(jí)的數(shù)組，這種數(shù)組的下標(biāo)可以是很大的整數(shù)，浮點(diǎn)數(shù)，字符串甚至結(jié)構(gòu)體。

哈希表的原理是將鍵通過(guò)函數(shù)映射到內(nèi)存特定位置，加快操作速度，該函數(shù)稱(chēng)為哈希函數(shù)或散列函數(shù)。

理想情況下，哈希表的每次操作的時(shí)間復(fù)雜度是 O(1)。

哈希函數(shù)

哈希函數(shù)的作用是將鍵映射到索引。哈希函數(shù)的設(shè)計(jì)很重要，決定了哈希表的時(shí)間與空間的平衡。

哈希函數(shù)應(yīng)滿(mǎn)足容易計(jì)算且能夠?qū)⑺械逆I均勻分布。理想情況下，不同的鍵應(yīng)該映射到不同的索引，但是實(shí)際情況下，因?yàn)楣：瘮?shù)的設(shè)計(jì)和索引空間限制等因素，可能出現(xiàn)不同的鍵映射到相同的索引的情況，稱(chēng)為哈希沖突。

哈希沖突

不同的鍵映射到相同的索引稱(chēng)為哈希沖突。哈希沖突的概率和哈希函數(shù)的設(shè)計(jì)有直接關(guān)系，好的哈希函數(shù)可以顯著減少哈希沖突的情況，但是很難完全避免哈希沖突。因此，需要有解決哈希沖突的方法。

有兩種常見(jiàn)的解決哈希沖突的方法，一是鏈地址法，二是開(kāi)放尋址法。

鏈地址法

鏈地址法也稱(chēng)拉鏈法，其思想是將映射到相同索引的值存入同一個(gè)鏈表中。

鏈地址法解決哈希沖突的做法簡(jiǎn)單，查找、添加和刪除操作的實(shí)現(xiàn)都較為簡(jiǎn)單，雖然鏈地址法的各項(xiàng)操作的時(shí)間復(fù)雜度在最壞情況下會(huì)退化為線(xiàn)性，但是在平均情況下仍然是 O(1)。

開(kāi)放尋址法

開(kāi)放尋址法的思想是：當(dāng)發(fā)生哈希沖突時(shí)，繼續(xù)探查哈希表中的其他索引位置，直到找到空的索引位置用于填入值。

和鏈地址法相比，開(kāi)放尋址法的刪除操作更為復(fù)雜。為了避免在刪除之后導(dǎo)致重新尋址的鍵無(wú)法找到，進(jìn)行刪除操作時(shí)，只能在被刪除的位置做刪除標(biāo)記而不能真正刪除。

開(kāi)放尋址法的常用探查做法有三種：線(xiàn)性探查、二次探查和雙重哈希。

閉散列法

閉散列方法把所有記錄直接存儲(chǔ)在散列表中，如果發(fā)生沖突則根據(jù)某種方式繼續(xù)進(jìn)行探查。

比如線(xiàn)性探查法：如果在 d 處發(fā)生沖突，就依次檢查 d+1，d+2……

哈希表的應(yīng)用場(chǎng)景和使用技巧

哈希表的應(yīng)用主要有以下場(chǎng)景：

（1）計(jì)數(shù)，使用哈希表記錄元素的次數(shù)；

（2）存儲(chǔ)已經(jīng)計(jì)算過(guò)的信息，避免重復(fù)計(jì)算，在動(dòng)態(tài)規(guī)劃中經(jīng)常會(huì)使用哈希表存儲(chǔ)已經(jīng)計(jì)算過(guò)的信息；

（3）判斷一個(gè)元素是否已經(jīng)訪(fǎng)問(wèn)過(guò)，該場(chǎng)景常用哈希集合，判斷鏈表是否有環(huán)問(wèn)題和搜索問(wèn)題中經(jīng)常使用哈希集合；

（4）和雙向鏈表結(jié)合，可以實(shí)現(xiàn)最近最少使用（LRU）緩存和最不經(jīng)常使用（LFU）緩存。

大多數(shù)情況下，使用哈希表和哈希集合的場(chǎng)景都會(huì)使用 HashMap 類(lèi)和 HashSet 類(lèi)的對(duì)象。如果哈希表的鍵范圍有限或者哈希集合的元素范圍有限，例如只能是數(shù)字或者只能是字母，則可以用數(shù)組代替哈希表。雖然從復(fù)雜度分析的角度而言，數(shù)組和哈希表的時(shí)間復(fù)雜度和空間復(fù)雜度相同，但是在實(shí)際運(yùn)行時(shí)，數(shù)組的操作時(shí)間和占用空間都優(yōu)于哈希表。

哈希表的主要考點(diǎn)

（1）是否會(huì)靈活的使用哈希表解決問(wèn)題；

（2）是否熟練掌握哈希表的基本原理；

（3）哈希沖突解決方法。