概述

散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
給定表M，存在函數(shù)f(key)，對任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)。

哈希表是一種通過哈希函數(shù)將特定的鍵映射到特定值的一種數(shù)據(jù)結(jié)構(gòu)，他維護(hù)者鍵和值之間一一對應(yīng)關(guān)系。

• 鍵(key)：又稱為關(guān)鍵字。唯一的標(biāo)示要存儲的數(shù)據(jù)，可以是數(shù)據(jù)本身或者數(shù)據(jù)的一部分。
• 槽(slot/bucket)：哈希表中用于保存數(shù)據(jù)的一個單元，也就是數(shù)據(jù)真正存放的容器。
• 哈希函數(shù)(hash function)：將鍵(key)映射(map)到數(shù)據(jù)應(yīng)該存放的槽(slot)所在位置的函數(shù)。
• 哈希沖突(hash collision)：哈希函數(shù)將兩個不同的鍵映射到同一個索引的情況。

這么講真的太太太抽象了，我舉個例子吧

Example1這里面的h函數(shù)即為哈希函數(shù)，由算法很容易知道為x對5取余數(shù) h(47)明顯為2
Example2中的函數(shù)同理

訪問鍵值k

對于一個存儲n個數(shù)據(jù)的哈希表，則哈希表中為HT[0]~HT[N-1]，但我們對于訪問的鍵值為2的槽，只需要使用HT[2]即可

Hash Fuction哈希函數(shù)

這個有很多，舉幾個經(jīng)典的算法

int h1(int x){
  return (x%5);
}

int h2(char* x){
  int i,sum;
  for(sum=0, i=0; x[i] != '\0'; i++)
    sum += (int)x[i];
  return (sum%5);
}

int ELFhash(char*key)
{
    unsigned long h=0;
    while(*key)
    {
        h = (h << 4) + *key++;
        unsigned long g = h & 0xF0000000L;
        if(g)
            h ^= g >> 24;
        h &= ~g;
    }
    return h % MOD;
}

ELFhash這個字符串hash函數(shù)中涉及許多位運(yùn)算，有興趣的可以上網(wǎng)查查，這里就不詳述了。

Hash Collision哈希沖突

顯而易見，哈希沖突就是指不同的鍵值k1,k2在哈希函數(shù)h(x)映射下到了相同的slot
自然，有沖突就會有解決方案。

Open Hashing 拉鏈法

名詞解釋：叫拉鏈，是因?yàn)楣_突后，用鏈表去延展來解決。

1. 拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會發(fā)生沖突，因此平均查找長度較短；
2. 在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)

缺點(diǎn)：
在對鏈表進(jìn)行存儲空間分配的時(shí)候，會降低整個程序的運(yùn)行速率

Closed Hashing 開地址法 （Open Addressing）

名詞解釋：叫Closed，是因?yàn)楣_突后，并不會在本身之外開拓新的空間，而是繼續(xù)順延下去某個位置來存放，所以是一個密閉的空間，所以叫“Closed”，至于開地址（Open Addressing），這個應(yīng)該相對于那種通過鏈表來開拓新空間，它是在本身地址上，另外找個位置。所以叫開地址。

以下介紹常用的開地址法

1. Bucket Hashing哈希桶
2. Probing 探測

Bucket Hashing 哈希桶

這一頁P(yáng)PT應(yīng)該很好理解，采用的是哈希桶(Bucket Hashing)，每個桶的大小為2，一共有5個桶，所以一共有5*2=10個槽(slot)
插入的算法很簡單

1. 把數(shù)據(jù)放到經(jīng)過哈希函數(shù)后得到key值第一個slot里
2. 若slot已經(jīng)被占用，用下一個slot
3. 如果bucket滿了，把數(shù)據(jù)放到overflow里面

查找算法也很簡單

1. 先得到鍵值key
2. 再在bucket中找第一個第二個
3. 若找不到再在overflow中找

Probing探測

p(k,i)探測函數(shù)。其值為第i次探測時(shí)相對h(k)的便宜

Pos(i)=(h(k) + p(k ,i)) % M;

p(i) = i ;

p(i) = i * c ;

注意這里的c必須與表的大小M互質(zhì)

但是線性探測有一個很明顯的缺點(diǎn)，就是數(shù)據(jù)很可能會聚集在一塊
Quadratic Probing 平方探測

例子

p(1)=1;
p(2)=4;
p(2)=9;

對于h(k1)=3
h(k1)+p(1)=h(k1)+1=4
h(k1)+p(2)=h(k1)+4=7
h(k1)+p(3)=h(k1)+9=12

Random Probing 隨機(jī)探測

p(k,i) = random();

但是并不存在真隨機(jī)，如果存在真隨機(jī)，會出現(xiàn)slot無法被哈希函數(shù)搜索到
Pseudo-Random Probing 偽隨機(jī)探測

看圖中的
探測序列為r1,r2,r3...即

p(1)=r1;
p(2)=r2;
p(2)=r3;

對于h(k1)=30
h(k1)+p(1)=h(k1)+2=32
h(k1)+p(2)=h(k1)+5=35
h(k1)+p(3)=h(k1)+32=62

Double Hashing 雙重散列
這是用于開放尋址法的最好方法之一，具有隨機(jī)選擇排列的許多特性

刪除

1. Tombstones墓碑
2. Local Reorganization
3. Rehash

where $\mu$ is the mean value, $\sigma^2$ is standard deviation

參考

• 百度百科
• 哈希表概述
• Open Hash
• 算法導(dǎo)論第三版
• 華工計(jì)算機(jī)科學(xué)與工程學(xué)院數(shù)據(jù)結(jié)構(gòu)課程PPT