散列（2）線性探測法和雙重散列法

接上篇 散列的簡要描述和鍊位址法

解決散列沖突的方法：

1. 線性探測法

如果我們能夠預測将要存入表中元素的數目，而且我們有足夠的記憶體空間可以容納帶有空閑空間的所有關鍵字，那麼使用鍊位址法是不值得的。我們依靠空的存儲空間解決沖突：設計表長M大于元素數目N，開放位址法，最簡單的開放位址法是線性探測法：

初始化

該符号表的實作将元素儲存到大小是元素個數兩倍的散清單中。

void HashTableInit(int max)
{
    N = ;
    M = *max;
    hash_table = new Item[M];
    for(int i = ; i < M; i++)
        hash_table[i] = NULLItem;
}
           

插入

（1）當沖突發生時，即準備插入的位置已被占用，我們檢查表中的下一個位置，

（2）如果下一個位置也被占用，繼續檢查下一個，知道遇到一個空位，然後将其插入

在搜尋時：

void HashTableInsert(Item item)
{
    int hash_key = Hash(GetKey(item), M);
    while (hash_table[hash_key] != NULLItem) {
        hash_key = (hash_key+) % M;
    }
    hash_table[hash_key] = item;
    N++;
}
           

搜尋

我們将檢查表中是否存在與搜尋關鍵字比對的元素成為探測。線性探測法的特點是每次探測有3種可能結果：

（1）搜尋命中（目前位置上的元素關鍵字與搜尋關鍵字比對，停止搜尋），

（2）搜尋失敗（搜尋位置為空，停止搜尋），

（3）不比對（搜尋位置非空，但是不比對，繼續搜尋下一位置）。

Item HashTabelSearch(KeyItem v)
{
    int hash_key = Hash(v, M);
    //遇到空位置，搜尋失敗
    while (hash_table[hash_key] != NULLItem) {
        if(eq(GetKey(hash_table[hash_key]), v)) //搜尋命中
            break;
        hash_key = (hash_key+) % M; //不比對
    }
    return hash_table[hash_key];
}
           

删除

線性探測表中的删除，僅僅移走删除關鍵字對應的元素時不夠的。因為當移走後形成的空位會導緻其後面元素的搜尋失敗（空位終止向後搜尋）。是以，應該将删除位置與其右邊的下一個空位之間所有元素重新散列插入到表中。

void HashTabelDelete(Item item)
{
    int hash_key = Hash(GetKey(item), M);
    //尋找删除位置
    while (hash_table[hash_key] != NULLItem) {
        if (eq(GetKey(item), GetKey(hash_table[hash_key])))
            break;
        else
            hash_key = (hash_key+) % M;
    }   
    if (hash_table[hash_key] == NULLItem)
        return;
    hash_table[hash_key] = NULLItem;
    N--;
    //将删除位置到其右邊下一個空位之間所有的元素重新散列
    for (int j = hash_key+; hash_table[j] != NULLItem; j = (j+)%M) {
        HashTableInsert(hash_table[j]);
        hash_table[j] = NULLItem;
    }
}
           

性能分析

開放位址法的性能依賴于 α=N/M ，表示表中被位置被占據的百分比，成為裝填因子。

對于稀疏表（ α 較小），預期幾次探測就能找到表的空位，但對于接近滿的表（ α 較大），一次搜尋要經曆相當多次的探測。是以我們為了避免過長時間搜尋，不允許表達到接近滿。

線上性探測中，多個元素聚合到連續一段空間成為聚焦，這将導緻搜尋時間的變慢。時間平均開銷依賴于插入時的聚焦情況。即：要經曆很多次的探測才能确定是否搜尋成功（比對）或失敗（空位）。

2. 雙重散清單

對于線性探測法，當聚焦問題嚴重或者表接近滿時，要搜尋一個關鍵字，往往要逐個檢查很多個無關項（先于和搜尋關鍵字比對的元素插入）。為了解決聚焦問題，提出了雙重雜湊演算法，其基本政策和線性探測法一項，唯一不同是：它不是檢查沖突位置後的每一個位置，而是采用另一個散列函數産生一個固定的增量。（跳躍式檢查和插入，減小聚焦大小）

假設第二個散列函數值為T

- 線性探測法：逐個檢查沖突位置的下一個位置

- 雙重散清單：每隔T個位置檢查一次

注：第二個散列函數要仔細選擇，需滿足條件

（1）排除散列值是0的情況

（2）産生的散列值必須與表長M互素

常用

`#define Hash2(v) ((v % 97) + 1)

2.1 搜尋和插入

void HashTableInsert(Item item)
{
    int hash_key = Hash(GetKey(item), M);
    int hash_key2 = Hash2(GetKey(item), M);

    while (hash_table[hash_key] != NULLItem) {
        // hash_key = (hash_key+1) % M; 線性探測時 +1
        hash_key = (hash_key+hash_key2) % M;
    }
    hash_table[hash_key] = item;
    N++;
}

Item HashTabelSearch(KeyItem v)
{
    int hash_key = Hash(v, M);
    int hash_key2 = Hash2(v, M);
    while (hash_table[hash_key] != NULLItem) {
        if(eq(GetKey(hash_table[hash_key]), v))
            break;
        hash_key = (hash_key+hash_key2) % M;
    }
    return hash_table[hash_key];
}
           

2.2 删除

如果雙重散清單的删除操作繼承線性探測算法：那麼删除算法會降低雙重散清單的性能，因為待删除關鍵字有可能影響整個表中的關鍵字，解決辦法是：用一個觀察哨代替已删除元素，表示該位置被占用，不與任何關鍵字比對。

2.3 性能分析

如果要保證所有搜尋的平均開銷小于t次探測，那麼線性探測法和雙重散列法的裝填因子分别要小于 1−1/t√ 和 1−1/t

3. 動态散清單

因為随着表中關鍵字的增多，表的性能會下降，一種解決辦法是：當表快要滿時，表的大小加倍，然後被所有元素重新插入。（非經常性操作，可以接受）

如果表支援删除的ADT操作，随着表元素減少，值得對表大小減半。但需要注意的是表長加倍和減半的門檻值時不同的。如在半滿時加倍，在1/8滿時減半。

表長動态變化能夠合理處理各種元素個數的變化，缺點是表的擴張和縮減時的重新散列和記憶體配置設定的開銷。

4. 散列的綜述

• 線性探測是三者中最快的（前提是記憶體足夠大保證表稀疏）
• 雙重散列法使用記憶體最高效（需要額外開銷計算第二個散列值）
• 鍊位址法易于實作（假設已經存在好的記憶體配置設定），特别對于删除操作；對于固定表長通常選擇鍊位址法。

如何選擇：

- 是選擇線性探測還是雙重散列主要取決于：計算散列函數的開銷和裝填因子。 α 較小，兩者均可；長關鍵字計算散列函數開銷大；裝填因子 α 接近于1，雙重散列性能大于線性探測。

- 鍊位址法需要額外的記憶體空間存儲連結，但是有一些符号表中已經事先配置設定好了連結字段的元素。雖然不如開放位址法快，但性能仍然比順序搜尋快的多。

- 當以搜尋為主且關鍵字數目不能精确預測時，動态散清單是可選的。

5. 所有源碼

http://download.csdn.net/detail/quzhongxin/8620465

參考資料 《算法：C語言實作》p388-401