一、哈希表的概念

1、查找算法

  當(dāng)我們?cè)谝粋€(gè) 鏈表 或者 順序表 中 查找 一個(gè)數(shù)據(jù)元素 是否存在 的時(shí)候，唯一的方法就是遍歷整個(gè)表，這種方法稱為 線性枚舉。

  如果這時(shí)候，順序表是有序的情況下，我們可以采用折半的方式去查找，這種方法稱為 二分枚舉。
  線性枚舉 的時(shí)間復(fù)雜度為 O ( n ) O(n) O(n)。二分枚舉 的時(shí)間復(fù)雜度為 O(log2​n)。是否存在更快速的查找方式呢？這就是本要介紹的一種新的數(shù)據(jù)結(jié)構(gòu) —— 哈希表。

2、哈希表

  由于它不是順序結(jié)構(gòu)，所以很多數(shù)據(jù)結(jié)構(gòu)書上稱之為 散列表，下文會(huì)統(tǒng)一采用 哈希表 的形式來(lái)說(shuō)明，作為讀者，只需要知道這兩者是同一種數(shù)據(jù)結(jié)構(gòu)即可。
  我們把需要查找的數(shù)據(jù)，通過(guò)一個(gè) 函數(shù)映射，找到 存儲(chǔ)數(shù)據(jù)的位置 的過(guò)程稱為 哈希。這里涉及到幾個(gè)概念：
  a）需要 查找的數(shù)據(jù) 本身被稱為 關(guān)鍵字；
  b）通過(guò) 函數(shù)映射 將 關(guān)鍵字 變成一個(gè) 哈希值 的過(guò)程中，這里的 函數(shù) 被稱為 哈希函數(shù)；
  c）生成 哈希值 的過(guò)程過(guò)程可能產(chǎn)生沖突，需要進(jìn)行 沖突解決；
  d）解決完沖突以后，實(shí)際 存儲(chǔ)數(shù)據(jù)的位置 被稱為 哈希地址，通俗的說(shuō)，它就是一個(gè)數(shù)組下標(biāo)；
  e）存儲(chǔ)所有這些數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)就是 哈希表，程序?qū)崿F(xiàn)上一般采用數(shù)組實(shí)現(xiàn)，所以又叫 哈希數(shù)組。整個(gè)過(guò)程如下圖所示：

3、哈希數(shù)組

  為了方便下標(biāo)索引，哈希表 的底層實(shí)現(xiàn)結(jié)構(gòu)是一個(gè)數(shù)組，數(shù)組類型可以是任意類型，每個(gè)位置被稱為一個(gè)槽。如下圖所示，它代表的是一個(gè)長(zhǎng)度為 8 的 哈希表，又叫 哈希數(shù)組。

4、關(guān)鍵字

  關(guān)鍵字 是哈希數(shù)組中的元素，可以是任意類型的，它可以是整型、浮點(diǎn)型、字符型、字符串，甚至是結(jié)構(gòu)體或者類。如下的 A、C、M 都可以是關(guān)鍵字；

int A = 5;
char C[100] = "Hello World!";
struct Obj { };
Obj M;

  哈希表的實(shí)現(xiàn)過(guò)程中，我們需要通過(guò)一些手段，將一個(gè)非整型的 關(guān)鍵字 轉(zhuǎn)換成 數(shù)組下標(biāo)，也就是 哈希值，從而通過(guò)O(1) 的時(shí)間快速索引到它所對(duì)應(yīng)的位置。
  而將一個(gè)非整型的 關(guān)鍵字 轉(zhuǎn)換成 整型 的手段就是 哈希函數(shù)。

5、哈希函數(shù)

  哈希函數(shù)可以簡(jiǎn)單的理解為就是小學(xué)課本上那個(gè)函數(shù)，即

y = f ( x )

，這里的 f(x) 就是哈希函數(shù)，x是關(guān)鍵字，y是哈希值。好的哈希函數(shù)應(yīng)該具備以下兩個(gè)特質(zhì)：
  a）單射；
  b）雪崩效應(yīng)：輸入值x的 1比特的變化，能夠造成輸出值y至少一半比特的變化；
  單射很容易理解，圖 ( a ) (a) (a) 中已知哈希值 y 時(shí)，鍵 x 可能有兩種情況，不是一個(gè)單射；而圖 (b) 中已知哈希值 y時(shí)，鍵 x 一定是唯一確定的，所以它是單射。由于 x  和 y  一一對(duì)應(yīng)，這樣就從本原上減少了沖突。

雪崩效應(yīng)是為了讓哈希值更加符合隨機(jī)分布的原則，哈希表中的鍵分布的越隨機(jī)，利用率越高，效率也越高。
  常用的哈希函數(shù)有：直接定址法、除留余數(shù)法、數(shù)字分析法、平方取中法、折疊法、隨機(jī)數(shù)法 等等。有關(guān)哈希函數(shù)的內(nèi)容，下文會(huì)進(jìn)行詳細(xì)講解。

6、哈希沖突

  哈希函數(shù)在生成 哈希值 的過(guò)程中，如果產(chǎn)生 不同的關(guān)鍵字得到相同的哈希值 的情況，就被稱為 哈希沖突。
  即對(duì)于哈希函數(shù)y=f(x)，當(dāng)關(guān)鍵字 x1≠x2 ，但是卻有f(x1​)=f(x2​)，這時(shí)候，我們需要進(jìn)行沖突解決。
  沖突解決方法有很多，主要有：開放定址法、再散列函數(shù)法、鏈地址法、公共溢出區(qū)法 等等。有關(guān)解決沖突的內(nèi)容，下文會(huì)進(jìn)行詳細(xì)講解。

7、哈希地址

  哈希地址 就是一個(gè) 數(shù)組下標(biāo) ，即哈希數(shù)組的下標(biāo)。通過(guò)下標(biāo)獲得數(shù)據(jù)，被稱為 索引。通過(guò)數(shù)據(jù)獲得下標(biāo)，被稱為 哈希。平時(shí)工作的時(shí)候，和同事交流時(shí)用到的一個(gè)詞 反查 就是說(shuō)的 哈希。

二、常用哈希函數(shù)

1、直接定址法

  直接定址法 就是 關(guān)鍵字 本身就是 哈希值，表示成函數(shù)值就是

f(x)=x

  例如，我們需要統(tǒng)計(jì)一個(gè)字符串中每個(gè)字符的出現(xiàn)次數(shù)，就可以通過(guò)這種方法。任何一個(gè)字符的范圍都是 [0,255]，所以只要用一個(gè)長(zhǎng)度為 256 的哈希數(shù)組就可以存儲(chǔ)每個(gè)字符對(duì)應(yīng)的出現(xiàn)次數(shù)，利用一次遍歷枚舉就可以解決這個(gè)問(wèn)題。C代碼實(shí)現(xiàn)如下：

int i, hash[256];
for(i = 0; str[i]; ++i) {
    ++hash[ str[i] ];
}

  這個(gè)就是最基礎(chǔ)的直接定址法的實(shí)現(xiàn)。hash[c]代表字符c在這個(gè)字符串str中的出現(xiàn)次數(shù)。

2、平方取中法

  平方取中法 就是對(duì) 關(guān)鍵字 進(jìn)行平方，再取中間的某幾位作為 哈希值。
  例如，對(duì)于關(guān)鍵字 1314，得到平方為1726596，取中間三位作為哈希值，即265。
  平方取中法 比較適用于 不清楚關(guān)鍵字的分布，且位數(shù)也不是很大 的情況。

3、折疊法

  折疊法 是將關(guān)鍵字分割成位數(shù)相等的幾部分（注意最后一部分位數(shù)不夠可以短一些），然后再進(jìn)行求和，得到一個(gè) 哈希值。
  例如，對(duì)于關(guān)鍵字 5201314，將它分為四組，并且相加得到：52+01+31+4=88，這就是哈希值。
  折疊法 比較適用于 不清楚關(guān)鍵字的分布，但是關(guān)鍵字位數(shù)較多 的情況。

4、除留余數(shù)法

  除留余數(shù)法 就是 關(guān)鍵字 模上 哈希表 長(zhǎng)度，表示成函數(shù)值就是

f(x)=x mod m

  其中 m 代表了哈希表的長(zhǎng)度，這種方法，不僅可以對(duì)關(guān)鍵字直接取模，也可以在 平方取中法、折疊法 之后再取模。
  例如，對(duì)于一個(gè)長(zhǎng)度為 4 的哈希數(shù)組，我們可以將關(guān)鍵字 模 4 得到哈希值，如圖所示：

5、位與法

  哈希數(shù)組的長(zhǎng)度一般選擇 2 的冪，因?yàn)槲覀冎廊∧＿\(yùn)算是比較耗時(shí)的，而位運(yùn)算相對(duì)較為高效。
  選擇 2 的冪作為數(shù)組長(zhǎng)度，可以將 取模運(yùn)算 轉(zhuǎn)換成 二進(jìn)制位與。
  令 m = 2^k，那么它的二進(jìn)制表示就是：

，任何一個(gè)數(shù)模上 m，就相當(dāng)于取了 m  的二進(jìn)制低 k 位，而

，所以和 位與m−1 的效果是一樣的。即：

  除了直接定址法，其它三種方法都有可能導(dǎo)致哈希沖突，接下來(lái)，我們就來(lái)討論下常用的一些哈希沖突的解決方案。

三、常見哈希沖突解決方案

1、開放定址法

1）原理講解

  開放定址法 就是一旦發(fā)生沖突，就去尋找下一個(gè)空的地址，只要哈希表足夠大，總能找到一個(gè)空的位置，并且記錄下來(lái)作為它的 哈希地址。公式如下：

  這里的di​ 是一個(gè)數(shù)列，可以是常數(shù)列(1,1,1,...,1)，也可以是等差數(shù)列(1,2,3,...,m−1)。

2）動(dòng)畫演示

  上圖中，采用的是哈希函數(shù)算法是 除留余數(shù)法，采用的哈希沖突解決方案是 開放定址法，哈希表的每個(gè)數(shù)據(jù)就是一個(gè)關(guān)鍵字，插入之前需要先進(jìn)行查找，如果找到的位置未被插入，則執(zhí)行插入；否則，找到下一個(gè)未被插入的位置進(jìn)行插入；總共插入了 6 個(gè)數(shù)據(jù)，分別為：11、12、13、20、19、28。
  這種方法需要注意的是，當(dāng)插入數(shù)據(jù)超過(guò)哈希表長(zhǎng)度時(shí)，不能再執(zhí)行插入。

  本文在第四章講解 哈希表的現(xiàn)實(shí) 時(shí)采用的就是常數(shù)列的開放定址法。

2、再散列函數(shù)法

1）原理講解

  再散列函數(shù)法 就是一旦發(fā)生沖突，就采用另一個(gè)哈希函數(shù)，可以是 平方取中法、折疊法、除留余數(shù)法 等等的組合，一般用兩個(gè)哈希函數(shù)，產(chǎn)生沖突的概率已經(jīng)微乎其微了。
  再散列函數(shù)法 能夠使關(guān)鍵字不產(chǎn)生聚集，當(dāng)然，也會(huì)增加不少哈希函數(shù)的計(jì)算時(shí)間。

2）動(dòng)畫演示

待補(bǔ)充

3、鏈地址法

1）原理講解

  當(dāng)然，產(chǎn)生沖突后，我們也可以選擇不換位置，還是在原來(lái)的位置，只是把 哈希值 相同的用鏈表串聯(lián)起來(lái)。這種方法被稱為 鏈地址法。

2）動(dòng)畫演示

  上圖中，采用的是哈希函數(shù)算法是 除留余數(shù)法，采用的哈希沖突解決方案是 鏈地址法，哈希表的每個(gè)數(shù)據(jù)保留了一個(gè) 鏈表頭結(jié)點(diǎn) 和 尾結(jié)點(diǎn)，插入之前需要先進(jìn)行查找，如果找到的位置，鏈表非空，則插入尾結(jié)點(diǎn)并且更新尾結(jié)點(diǎn)；否則，生成一個(gè)新的鏈表頭結(jié)點(diǎn)和尾結(jié)點(diǎn)；總共插入了 6 個(gè)數(shù)據(jù)，分別為：11、12、13、20、19、28。

4、公共溢出區(qū)法

1）原理講解

  一旦產(chǎn)生沖突的數(shù)據(jù)，統(tǒng)一放到另外一個(gè)順序表中，每次查找數(shù)據(jù)，在哈希數(shù)組中到的關(guān)鍵字和給定關(guān)鍵字相等，則認(rèn)為查找成功；否則，就去公共溢出區(qū)順序查找，這種方法被稱為 公共溢出區(qū)法。
  這種方法適合沖突較少的情況。

2）動(dòng)畫演示

待補(bǔ)充

四、哈希表的實(shí)現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)定義

  由于哈希表的底層存儲(chǔ)還是數(shù)組，所以我們可以定義一個(gè)結(jié)構(gòu)體，結(jié)構(gòu)體中定義一個(gè)數(shù)組類型的成員，如果需要記錄哈希表元素的個(gè)數(shù)，還可以記錄一個(gè) size字段。
  C語(yǔ)言實(shí)現(xiàn)如下：

#define maxn (1<<17)          // (1)
#define mask (maxn-1)         // (2)
#define DataType int          // (3)
#define Boolean int           // (4)
#define NULLKEY (maxn+2)      // (5)
typedef struct {
    DataType data[maxn];
}HashTable;

(1) 利用位運(yùn)算計(jì)算哈希函數(shù)進(jìn)行加速，哈希表的長(zhǎng)度為 2 的冪；

(2) 利用上文提到的 位與法 作為哈希函數(shù)，進(jìn)行位與的掩碼必須是二進(jìn)制表示都是1的，所以等于 2 的冪減一；

(3) 定義關(guān)鍵字類型為整型int；

(4) 定義一個(gè)布爾變量類型；

(5) NULLKEY作為哈希表對(duì)應(yīng)位置為空時(shí)的標(biāo)記，必須是一個(gè)非關(guān)鍵字能取到的值；

2、哈希表初始化

  哈希表初始化要做的事情，就是把哈希表的每個(gè)位置都置空。C語(yǔ)言代碼實(shí)現(xiàn)如下：

void HashInit(HashTable *ht) {
    int i;
    for(i = 0; i < maxn; ++i) {
        ht->data[i] = NULLKEY;      // (1)
    }
}

• (1) 將哈希表的每個(gè)位置都置空；

3、哈希函數(shù)計(jì)算

  哈希函數(shù)計(jì)算采用 除留余數(shù)法 的優(yōu)化版本 位與法。C語(yǔ)言代碼實(shí)現(xiàn)如下：

int HashGetAddr(DataType key) {
    return key & mask;
}

4、哈希表查找

  查找需要采用和插入時(shí)相同的哈希沖突方案，即開放尋址法。C語(yǔ)言代碼實(shí)現(xiàn)如下：

Boolean HashSearchKey(HashTable *ht, DataType key, int *addr) {
    int startaddr = HashGetAddr(key);    // (1)
    *addr = startaddr;                   // (2)
    while(ht->data[*addr] != key) {      // (3)
        *addr = HashGetAddr(*addr + 1);  // (4)
        if(ht->data[*addr] == NULLKEY)   // (5)
            return 0;                     
        if(*addr == startaddr)           // (6)
            return 0;                    
    }
    return 1;                            // (7)
}

(1) 根據(jù) 哈希函數(shù)HashGetAddr計(jì)算得到一個(gè)哈希值startaddr；

(2) addr是需要作為返回值的，所以要用解引用；

(3) 在哈希表的addr對(duì)應(yīng)查找，如果不是空位，則繼續(xù)(4)；否則，跳出循環(huán)；

(4) 往后找一個(gè)位置；

(5) 如果發(fā)現(xiàn)一個(gè)空位，說(shuō)明這個(gè)關(guān)鍵字在哈希表中沒(méi)有對(duì)應(yīng)數(shù)據(jù)，直接返回 0，代表查找失?。?/p>

(6) 代表整個(gè) 哈希表 都已經(jīng)遍歷完畢，都沒(méi)有找到合適的關(guān)鍵字，直接返回 0，代表查找失??；

(7) 否則，返回 1 代表查找成功；

5、哈希表插入

  哈希沖突時(shí)（即當(dāng)沒(méi)有合適位置），就找下一相鄰位置，即尋址數(shù)列為常數(shù)列 (1,1,1,...,1)。插入需要注意當(dāng)哈希表慢時(shí)，不能再執(zhí)行插入操作。C語(yǔ)言代碼實(shí)現(xiàn)如下：

int HashInsert(HashTable *ht, DataType key) {
    int addr = HashGetAddr(key);               // (1)
    int retaddr;
    if ( HashSearchKey(ht, key, &retaddr ) ) { // (2)
        return retaddr;
    } 
    while(ht->data[addr] != NULLKEY)           // (3)
        addr = HashGetAddr(addr + 1);          // (4)
    ht->data[addr] = key;                      // (5)
    return addr;                               // (6)
}

 (1) 根據(jù) 哈希函數(shù)HashGetAddr計(jì)算得到一個(gè)哈希值addr；

(2) 插入前需要先查找是否存在，如果已經(jīng)存在，則不執(zhí)行插入；

(3) 在哈希表的addr對(duì)應(yīng)查找，如果不是空位，則繼續(xù) (3)；否則，跳出循環(huán)；

(4) 往后找一個(gè)位置，繼續(xù)判斷是否為空； 

(5) 跳出循環(huán)則代表當(dāng)前哈希表的addr位置沒(méi)有其它元素占據(jù)，則可以作為當(dāng)前key的位置進(jìn)行插入；

(6) 返回addr作為key的哈希地址；

6、哈希表刪除

  有了查找的基礎(chǔ)，刪除操作就比較簡(jiǎn)單了，如果不能找到一個(gè)關(guān)鍵字的位置，則不對(duì)哈希表進(jìn)行任何操作，返回空關(guān)鍵字；否則，將找到的位置賦為空關(guān)鍵字，并且返回刪除的位置；

int HashRemove(HashTable *ht, DataType key) {
    int addr;
    if ( !HashSearchKey(ht, key, &addr ) ) {     // (1)
        return NULLKEY;
    } 
    ht->data[addr] = NULLKEY;                    // (2)
    return addr;
}

 (1) 首先執(zhí)行查找；

(2) 對(duì)找到的位置，將找到位置關(guān)鍵字清空；

7、哈希表完整實(shí)現(xiàn)

  最后，給出一個(gè) 開放定址法 的哈希表的完整實(shí)現(xiàn)，如下：

/******************** 哈希表 開放定址法 ********************/
#define maxn (1<<17)
#define mask (maxn-1)
#define DataType int
#define Boolean int
#define NULLKEY (1<<30)

typedef struct {
    DataType data[maxn];
}HashTable;

void HashInit(HashTable *ht) {
    int i;
    for(i = 0; i < maxn; ++i) {
        ht->data[i] = NULLKEY;
    }
}

int HashGetAddr(DataType key) {
    return key & mask; 
}

Boolean HashSearchKey(HashTable *ht, DataType key, int *addr) {
    int startaddr = HashGetAddr(key);
    *addr = startaddr;
    while(ht->data[*addr] != key) {
        *addr = HashGetAddr(*addr + 1);
        if(ht->data[*addr] == NULLKEY) {
            return 0;
        }
        if(*addr == startaddr) {
            return 0;
        }
    }
    return 1;
}

int HashInsert(HashTable *ht, DataType key) {
    int addr = HashGetAddr(key);
    int retaddr;
    if ( HashSearchKey(ht, key, &retaddr ) ) {
        return retaddr;
    } 
    while(ht->data[addr] != NULLKEY)
        addr = HashGetAddr(addr + 1);
    ht->data[addr] = key;
    return addr;
}

int HashRemove(HashTable *ht, DataType key) {
    int addr;
    if ( !HashSearchKey(ht, key, &addr ) ) {
        return NULLKEY;
    } 
    ht->data[addr] = NULLKEY;
    return addr;
}

/******************** 哈希表 開放定址法 ********************/

到此這篇關(guān)于簡(jiǎn)單講解哈希表的文章就介紹到這了,更多相關(guān)哈希表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論