【メモ】

オープン・アドレス・メソッド:すべての要素がハッシュ・テーブルに格納されます.要素を検索するときは、必要な要素が見つかるまですべてのテーブル・アイテムをチェックするか、最終的にその要素がテーブルにないことがわかります.
削除アクション:スロットに特定の値DELETEDを設定します.したがって,キーワードを削除しなければならないアプリケーションでは,衝突をリンク法で解決することが多い.
オープン・アドレス法のプローブ・シーケンスを計算します.
線形プローブ:h(k,i)=(h′(k)+i)mod m,i=0,1,...,m-1
二次探査:h(k,i)=(h′(k)+c 1*i+c 2*i^2)mod m
二重ハッシュ:h(k,i)=(h 1(k)+i*h 2(k))mod m
二重ハッシュは、生成された配列がランダムに選択された配列の多くの特性を有するため、オープンアドレス法に用いる最良の方法の1つである.

【練習】

11.4−1キーワード10,22,31,4,15,28,17,88,59をm=11の長さのハッシュリストにオープンアドレス法で挿入することを考慮し、補助ハッシュ関数はh(k)=k mod mである.これらのキーワードを線形プローブ、二次プローブ(c 1=1,c 2=3)および二重ハッシュh 2(k)=1+(k mod(m−1))でハッシュリストに挿入した結果を説明する.
22 88 0 0 4 15 28 17 59 31 10
22 0 88 17 4 0 28 59 15 31 10
22 0 59 17 4 15 28 88 0 31 10
11.4-2 HASH-DELETEの偽コードを書いてください.HASH-INSERTを修正し、特殊値DELETEDを処理できるようにします.

bool hashDelete(int k) {
    int i=0;
    do{
        int j=h(k,i);
        if (T[j]==0) {
            return false;
        }
        else if (T[j]==k) {
            T[j]=DELETED;
            return true;
        }
        else i++;
    }while (i<m);
    return false;
}

int hashInsert(int k) {
    int i=0;
    do{
        int j=h(k,i);
        if (a[j]==0||a[j]==DELETED) {
            a[j]=k;
            return j;
        }
        else i++;
    }while (i<m);
    return -1;
}

*11.4-3数論関連、31章を参照.
11.4〜4は、一貫したハッシュを用いたオープン・アドレス・ハッシュ・リストを考慮する.ロードファクタが3/4および7/8の場合、1回の不成功ルックアップにおける所望のルックアップ数の上界、および1回の成功ルックアップにおける所望のルックアップ数の上界が与えられる.
*11.4-5