哈希表（Hash table），也叫散列表，是根據(jù)關(guān)鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。哈希（hashing）是電腦科學(xué)中一種對資料的處理方法，通過某種特定的函數(shù)/算法（稱為散列函數(shù)/算法）將要檢索的項與用來檢索的索引（稱為哈希，或者哈希值）關(guān)聯(lián)起來，生成一種便于搜索的數(shù)據(jù)結(jié)構(gòu)（稱為哈希表表）。

散列函數(shù)能使對一個數(shù)據(jù)序列的訪問過程更加迅速有效，通過散列函數(shù)，數(shù)據(jù)元素將被更快地定位。

下面為大家介紹6種哈希表常用方法：

1.直接尋址法：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即H(key)=key或H(key) = a·key + b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）。若其中H(key）中已經(jīng)有值了，就往下一個找，直到H(key）中沒有值了，就放進去。

2.數(shù)字分析法：分析一組數(shù)據(jù)，比如一組員工的出生年月日，這時我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同，這樣的話，出現(xiàn)沖突的幾率就會很大，但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大，如果用后面的數(shù)字來構(gòu)成散列地址，則沖突的幾率會明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址。

3.平方取中法：當無法確定關(guān)鍵字中哪幾位分布較均勻時，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因為：平方后中間幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵字會以較高的概率產(chǎn)生不同的哈希地址。 [1]

例：我們把英文字母在字母表中的位置序號作為該英文字母的內(nèi)部編碼。例如K的內(nèi)部編碼為11，E的內(nèi)部編碼為05，Y的內(nèi)部編碼為25，A的內(nèi)部編碼為01, B的內(nèi)部編碼為02。由此組成關(guān)鍵字“KEYA”的內(nèi)部代碼為11052501，同理我們可以得到關(guān)鍵字“KYAB”、“AKEY”、“BKEY”的內(nèi)部編碼。之后對關(guān)鍵字進行平方運算后，取出第7到第9位作為該關(guān)鍵字哈希地址。

4. 折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進位）作為散列地址。數(shù)位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割后的每一部分的最低位對齊，然后相加；間界疊加是從一端向另一端沿分割界來回折疊，然后對齊相加。

5. 隨機數(shù)法：選擇一隨機函數(shù)，取關(guān)鍵字的隨機值作為散列地址，即H(key)=random(key)其中random為隨機函數(shù),通常用于關(guān)鍵字長度不等的場合。

6. 除留余數(shù)法：取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對關(guān)鍵字直接取模，也可在折疊、平方取中等運算之后取模。對p的選擇很重要，一般取素數(shù)或m，若p選的不好，容易產(chǎn)生同義詞。

以上就是6種哈希表常用方法，使用哈希表可以進行非?？焖俚牟檎也僮?，很多語言的內(nèi)置數(shù)據(jù)結(jié)構(gòu)像python中的字典，java中的HashMap，都是基于哈希表實現(xiàn)的。所以，哈希表的學(xué)習(xí)是必然的，在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中還有更多的數(shù)據(jù)結(jié)構(gòu)等你來學(xué)！