哈希表—超簡單的了解思路

一、啥是哈希表

哈希表又稱散清單，其實就是和數組、連結清單一樣的是一種資料結構，在你從來沒有接觸過這個概念的時候，覺得神秘而不可探測，其實就是一紙老虎，人狠話不多，先上一個相對官方的概念定義：

散列技術是在記錄的存儲位置和它的關鍵字之間建立一個确定的對應關系f，使得每個關鍵字key對應一個存儲位置f(key)。建立了關鍵字與存儲位置的映射關系，公式如下：

存儲位置 = f（關鍵字）

這裡把這種對應關系f稱為散列函數，又稱為哈希（Hash）函數。

采用散列技術将記錄存在在一塊連續的存儲空間中，這塊連續存儲空間稱為散清單或哈希表。那麼，關鍵字對應的記錄存儲位置稱為散列位址。

散列技術既是一種存儲方法也是一種查找方法。散列技術的記錄之間不存在什麼邏輯關系，它隻與關鍵字有關，是以，散列主要是面向查找的存儲結構。

人狠話不多，直接例子：

例1：現在我要你存儲4個元素 13 7 14 11，你将如何存儲？？？

答：顯然，我們可以用數組來存。也就是：a[1] = 13; a[2] = 7; a[3] = 14; a[4] = 11;

當然，我們也可以用Hash來存。下面給出一個簡單的Hash存儲：

先來确定那個函數。我們就用h(key) = key%5;(這個函數不用糾結，我們現在的目的是了解為什麼要有這麼一個函數)。那麼

對于第一個元素 h(13) = 13%5 = 3; 也就是說13的下标為3；即Hash[3] = 13;

對于第二個元素 h(7) = 7 % 5 = 2; 也就是說7的下标為2; 即Hash[2] = 7;

同理，Hash[4] = 14; Hash[1] = 11;

好了，存現在是存好了。但是，這并沒有展現出Hash的妙處，現在我要你查找11這個元素是否存在。你會怎麼做呢？

當然，對于數組來說，那是相當的簡單，一個for循環就可以了。也就是說我們要找4次。這是很笨的辦法，因為為了找一個數需要把整個序列循環一遍才行，太慢！

下面我們來用Hash找一下：

首先，我們将要找的元素11代入剛才的函數中來映射出它所在的位址單元。也就是h(11) = 11%5 = 1 了。下面我們來比較一下Hash[1]?=11, 這個問題就很簡單了。

也就是說我們就找了1次。我咧個去， 這個就是Hash的妙處了。

那麼，怎麼設計哈希函數呢，上邊的mod 5，我還mod 8 呢，是不是很氣？接下來咱們就看看哈希函數的設計

二、哈希函數的設計

1 直接定址法

　　取關鍵字或者關鍵字的某個線性函數為Hash位址，即address(key)=a*key+b;如知道學生的學号從2000開始，最大為4000，則可以将address(key)=key-2000作為Hash位址。

2 平方取中法

　　對關鍵字進行平方運算，然後取結果的中間幾位作為Hash位址。假如有以下關鍵字序列{421，423，436}，平方之後的結果為{177241，178929，190096}，那麼可以取中間的兩位數{72，89，00}作為Hash位址。

3 折疊法

　　将關鍵字拆分成幾部分，然後将這幾部分組合在一起，以特定的方式進行轉化形成Hash位址。假如知道圖書的ISBN号為8903-241-23，可以将address(key)=89+03+24+12+3作為Hash位址。

4 除留取餘法

　　如果知道Hash表的最大長度為m，可以取不大于m的最大質數p，然後對關鍵字進行取餘運算，address(key)=key%p。

在這裡p的選取非常關鍵，p選擇的好的話，能夠最大程度地減少沖突，p一般取不大于m的最大質數。

三、Hash表大小的确定

Hash表大小的确定也非常關鍵，如果Hash表的空間遠遠大于最後實際存儲的記錄個數，則造成了很大的空間浪費，如果選取小了的話，則容易造成沖突。在實際情況中，一般需要根據最終記錄存儲個數和關鍵字的分布特點來确定Hash表的大小。還有一種情況時可能事先不知道最終需要存儲的記錄個數，則需要動态維護Hash表的容量，此時可能需要重新計算Hash位址。

四、沖突的解決

沖突的發生：比如有一組關鍵字{12，13，25，23，38，34，6，84，91}，Hash表長為14，Hash函數為address(key)=key%11，當插入12，13，25時可以直接插入，而當插入23時，位址1被占用了，發生了沖突現象，是以需要辦法來解決，否則記錄無法進行正确的存儲。通常情況下有2種解決辦法：

1 開放定址法

　　即當一個關鍵字和另一個關鍵字發生沖突時，使用某種探測技術在Hash表中形成一個探測序列，然後沿着這個探測序列依次查找下去，當碰到一個空的單元時，則插入其中。比較常用的探測方法有線性探測法，比如有一組關鍵字{12，13，25，23，38，34，6，84，91}，Hash表長為14，Hash函數為address(key)=key%11，當插入12，13，25時可以直接插入，而當插入23時，位址1被占用了，是以沿着位址1依次往下探測(探測步長可以根據情況而定)，直到探測到位址4，發現為空，則将23插入其中。

2 鍊位址法

　　采用數組和連結清單相結合的辦法，将Hash位址相同的記錄存儲在一張線性表中，而每張表的表頭的序号即為計算得到的Hash位址。如上述例子中，采用鍊位址法形成的Hash表存儲表示為：

hash.jpg

雖然能夠采用一些辦法去減少沖突，但是沖突是無法完全避免的。是以需要根據實際情況選取解決沖突的辦法。

五、Hash表的平均查找長

Hash表的平均查找長度包括查找成功時的平均查找長度和查找失敗時的平均查找長度。

查找成功時的平均查找長度=表中每個元素查找成功時的比較次數之和/表中元素個數；

查找不成功時的平均查找長度相當于在表中查找元素不成功時的平均比較次數，可以了解為向表中插入某個元素，該元素在每個位置都有可能，然後計算出在每個位置能夠插入時需要比較的次數，再除以表長即為查找不成功時的平均查找長度。

下面的例子有助于了解。

例1

将關鍵字序列{7, 8, 30, 11, 18, 9, 14}散列存儲到散清單中。散清單的存儲空間是一個下标從0開始的一維數組，長度為10，即{0, 1,2, 3, 4, 5, 6, 7, 8, 9}。散列函數為： H(key) = (key * 3) % 7，處理沖突采用線性探測再散列法。

求等機率情況下查找成功和查找不成功的平均查找長度。

解：

1 求散清單

H(7) = (7 * 3) % 7 = 0
H(8) = (8 * 3) % 7 = 3
H(30) = 6
H(11) = 5
H(18) = 5
H(9) = 6
H(14) = 0
           

按關鍵字序列順序依次向哈希表中填入，發生沖突後按照“線性探測”探測到第一個空位置填入。

H(7) = 0，key = 7應插在第0個位置，因為第0個位置為空，可以直接插入。

H(8) = 3，key = 8應插在第3個位置，因為第3個位置為空，可以直接插入。

H(30) = 6，key = 30應插在第6個位置，因為第6個位置為空，可以直接插入。

H(11) = 5，key = 11應插在第5個位置，因為第5個位置為空，可以直接插入。

H(18) = 5，key = 18應插在第5個位置，但是第5個位置已經被key=11占據了，是以往後挪一位到第6個位置，但是第6個位置被key=30占據了，再往後挪一位到第7個位置，這個位置是空的，是以key=18就插到這個位置

H(9) = 6，key = 9應插在第6個位置，但是第6個位置已經被key = 30占據，是以需要往後挪一位到第7個位置，但是第7個位置已經被key = 18占據，是以再往後挪移到第8個位置，這個位置是空的，是以key = 9就插到這個位置。

H(14) = 0，key = 14應插在第0個位置，但第0個位置已被key=7占據，是以往後挪移一位到第1個位置，這個位置是空的，是以key=14就插到這個位置。

最終的插入結果如下表所示：

address	1	2	3	4	5	6	7	8	9
key	7	14	8	11	30	18	9

2 求查找成功的平均查找長度

查找7，H(7) = 0，在0的位置，一下子就找到了7，查找長度為1。

查找8，H(8) = 3，在3的位置，一下子就找到了8，查找長度為1。

查找30，H(30) = 6，在6的位置，一下子就找到了30，查找長度為1。

查找11，H(11) = 5，在5的位置，一下子就找到了11，查找長度為1。

查找18，H(18) = 5，第一次在5的位置沒有找到18，第二次往後挪移一位到6的位置，仍沒有找到，第三次再往後挪移一位到7的位置，找到了，查找長度為3。

查找9，H(9) = 6，第一次在6的位置沒找到9，第二次往後挪移一位到7的位置，仍沒有找到，第三次再往後挪移一位到8的位置，找到了，查找長度為3.

查找14，H(14) = 0，第一次在0的位置沒找到14，第二次往後挪移一位到1的位置，找到了，查找長度為2。

是以，查找成功的平均查找長度為(1 + 1 + 1 + 1 + 3 + 3 + 2) / 7 = 12 / 7。

3 求查找不成功的平均查找長度

查找不成功，說明要查找的數字肯定不在上述的散清單中。

因為這裡哈希函數的模為7，是以要查找的數的初始位址隻可能位于0~6的位置上。

位址0，到第一個關鍵字為空的位址2需要比較3次，是以查找不成功的次數為3。比如要查找的數為28，H(28) = (28 * 3) % 7 = 0。即28對應的位址是0，由于存放在0位置的數是7，是以往後挪移一位，發現在1位置存放的數是14，繼續往後挪一位，發現位置2上沒有數。至此就知道28不在這個哈希表裡，即查找28失敗。

位址1，到第一個關鍵字為空的位址2需要比較2次，是以查找不成功的次數為2。

位址2，到第一個關鍵字為空的位址2需要比較1次，是以查找不成功的次數為1。

位址3，到第一個關鍵字為空的位址4需要比較2次，是以查找不成功的次數為2。

位址4，到第一個關鍵字為空的位址4需要比較1次，是以查找不成功的次數為1。

位址5，到第一個關鍵字為空的位址9需要比較5次，是以查找不成功的次數為5。

比如要查找的數為4，H(4) = (4 * 3) % 7 = 5，是以從位址5開始查找，最終發現位址5、位址6、位址7、位址8上存放的數都不是5，并且位址9的位置上沒放資料，至此可知5不在這個哈希表裡。

位址6，到第一個關鍵字為空的位址9需要比較4次，是以查找不成功的次數為4。

是以，查找不成功的平均查找長度為（3 + 2 + 1 + 2 + 1 + 5 + 4）/ 7 = 18 / 7。

六、C語言的實作

/*采用數組實作哈希表*/ 

#include<stdio.h>
#define DataType int
#define Len 10
 
typedef struct HashNode    
{
    DataType data;    //存儲值 
    int isNull;       //标志該位置是否已被填充 
}HashTable;

HashTable hashTable[Len];

void initHashTable()     //對hash表進行初始化 
{
    int i;
    for(i = 0; i<Len; i++)
    {
        hashTable[i].isNull = 1;    //初始狀态為空 
    }
}

int getHashAddress(DataType key)    //Hash函數 
{
    return key * 3 % 7;      
}

int insert(DataType key)    
{
    int address = getHashAddress(key);       
    if(hashTable[address].isNull == 1)  //沒有發生沖突 
    {
        hashTable[address].data = key;
        hashTable[address].isNull = 0;
    }
    else    //當發生沖突的時候 
    {
        while(hashTable[address].isNull == 0 && address<Len)
        {
            address++;          //采用線性探測法，步長為1 
        }
        if(address == Len)      //Hash表發生溢出 
            return -1;
        hashTable[address].data = key;
        hashTable[address].isNull = 0;
    }
    
    return 0;
}

int find(DataType key)       
{
    int address = getHashAddress(key);
    while( !(hashTable[address].isNull == 0 && hashTable[address].data == key && address<Len))
    {
        address++;
    } 
    
    if( address == Len)
    {
        address = -1;
    }
    
    return address;
}


int main(int argc, char *argv[])
{
    int key[]={7,8,30,11,18,9,14};
    int i;
    initHashTable();
    
    for(i = 0; i<7; i++)
    {
        insert(key[i]);
    }
    
    for(i = 0; i<7; i++)
    {
        int address;
        address = find(key[i]);
        printf("key:%d\t address:%d\n", key[i],address);
    }
    
    return 0;
}
           

//運作結果
key:7    address:0
key:8    address:3
key:30   address:6
key:11   address:5
key:18   address:7
key:9    address:8
key:14   address:1
           

最後在加上一個用哈希表的LeetCode的例子：

例：給定一個贖金信 (ransom) 字元串和一個雜志(magazine)字元串，判斷第一個字元串ransom能不能由第二個字元串magazines裡面的字元構成。如果可以構成，傳回 true ；否則傳回 false。

(題目說明：為了不暴露贖金信字迹，要從雜志上搜尋各個需要的字母，組成單詞來表達意思。)

注意：

你可以假設兩個字元串均隻含有小寫字母。

canConstruct("a", "b") -> false

canConstruct("aa", "ab") -> false

canConstruct("aa", "aab") -> true

用C語言加哈希表實作如下：

bool canConstruct(char * ransomNote, char * magazine)
{

    int hash[26] = {0};
    for (int i = 0; i < strlen(magazine); i++)
    {
        hash[magazine[i] - 'a'] += 1;
    }

    for (int i = 0; i < strlen(ransomNote); i++)
    {
        hash[ransomNote[i] - 'a'] -= 1;
        if (hash[ransomNote[i] - 'a'] < 0)
        {
            return false;
        }
    }
    return true;
}
           

用C++沒用哈希表實作如下：

#include <string>
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine);
};

bool Solution::canConstruct(string ransomNote, string magazine)
{
    if (ransomNote.empty() )
    {
        return true;
    }
    if ( magazine.empty() || (ransomNote.size() > magazine.size()) )
    {
        return false;
    }
    for (int i = 0; i < ransomNote.size(); i++)
    {
        std::string::size_type pos = magazine.find(ransomNote[i]);
        if (pos != -1)
        {
            magazine.erase(pos, 1);
            continue;
        }
        else 
        {
            return false;
        }
    }
    return true;
}