cos

一、ハッシュテーブル（ハッシュ表）#

1. 概念の導入#

コンパイル処理における変数の管理：動的検索問題

• 検索木を利用する？—— 二つの変数名（文字列）比較効率が低い
• 文字列を数字に変換して処理する？—— これがハッシュ検索の考え方
  既知のいくつかの検索方法：
• 順次検索 O (N)
• 二分検索（静的検索） O (log~2~N)
• 二分探索木 O (h) h は二分探索木の高さ
• 平衡二分木 O (log~2~N)

問題：必要なキーワードを迅速に検索するには？キーワードの比較が困難な場合はどうする？#

検索の本質： 知られたオブジェクトの位置を見つける

• オブジェクトを順序付ける：全順序（完全に順序付けられた、eg: 二分検索）、半順序（特定のキーワード間に順序が存在する、eg: 検索木）
• 直接 **「計算する」** オブジェクトの位置：ハッシュ

ハッシュの基本作業#

• 位置を計算する：ハッシュ関数を構築してキーワードの保存位置を決定
• 衝突を解決する：複数のキーワードが同じ位置にある問題を解決するために何らかの戦略を適用

時間計算量#

時間計算量はほぼ定数：O (1)、つまり検索時間は問題の規模に依存しない！

2. ハッシュ検索#

（1）基本思想#

• キーワードkeyを自変数として、確定した関数 h **（ハッシュ関数）** を通じて、対応する関数値 h (key) を計算し、データオブジェクトの保存アドレスとする
• 異なるキーワードが同じハッシュアドレスにマッピングされる可能性がある、すなわち h (key~i~) = h (key~j~) (key~i~ ≠ key~j~ のとき)、これを **「衝突 (Collision)」** と呼ぶ。—— 何らかの衝突解決戦略が必要

衝突がない場合、検索はハッシュ関数に基づいてアドレスを計算して行う

ロードファクター#

ロードファクター（Loading Factor）：ハッシュテーブルの空間サイズを m、テーブルに入れる要素の個数を n とすると、α = n /m をハッシュテーブルのロードファクターと呼ぶ

• 上の図のα = 11 / 17 ≈ 0.65
  オーバーフローがなければ T~ 検索～= T~ 挿入～= T~ 削除～= O (1)

再ハッシュ#

• ハッシュテーブルの要素が多すぎる（すなわちロードファクター α が大きすぎる）場合、検索効率が低下する
  • 実用的な最大ロードファクターは一般に0.5 ≤ α ≤ 0.85
• 解決策はハッシュテーブルを倍増させることで、このプロセスを「再ハッシュ(Rehashing)」と呼ぶ

（2）ハッシュ関数の構築#

二つの要素#

「良い」ハッシュ関数は一般に以下の二つの要素を考慮すべき：

• 計算が簡単で、変換速度を向上させるため
• キーワードに対応するアドレス空間が均等に分布し、衝突をできるだけ減らすため。

数字キーワードのハッシュ関数構築#

① 直接アドレス法#

キーワードのある線形関数値をハッシュアドレスとする、すなわちh(key) = a ×key + b（a、b は定数）

② 除留余数法（一般的）#

ハッシュ関数は：h(key) = key mod p
eg：h(key) = key %17

一般にキーワードに対応するアドレス空間が均等に分布するように、p は素数を取る

③ 数字分析法#

数字キーワードの各桁の変化状況を分析し、比較的ランダムな桁をハッシュアドレスとして取る

④ 折りたたみ法#

キーワードを桁数が同じいくつかの部分に分割し、重ね合わせる

⑤ 平方取中法#

文字キーワードのハッシュ関数構築#

簡単なハッシュ関数 ——ASCII コード加合法#

文字型キーワード key に対してハッシュ関数を以下のように定義する：h(key) = (Σkey[i]) mod TableSize
衝突が深刻！！

簡単な改善 —— 最初の 3 文字移位法#

h(key) = (key[0] × 27^2^ + key[1] ×27 + key[2]) mod TableSize
依然として衝突、空間の浪費

良いハッシュ関数 —— 移位法#

キーワードのすべての n 文字を設計し、かつ良く分布させる
h(key) = ($\begin{matrix} \sum_{i=0}^{n-1}key[n-i-1] \times32^i \end{matrix}$) mod TableSize
コードは以下の通り

typedef string DataType;//データの型
typedef int Index;//ハッシュ後のインデックス
//ハッシュ関数計算後のインデックスを返す
Index Hash(string Key, int TableSize) { 
    unsigned int h = 0; //ハッシュ関数値、初期値は0
    int len = Key.length();
    for(int i = 0; i < len; ++i) 
        h = (h << 5) + Key[i];
    
    return h % TableSize;
}

（3）ハッシュ検索の衝突処理#

一般的な衝突処理の考え方は以下の通り

• 別の位置に移動 ——オープンアドレッシング法
• 同じ位置の衝突オブジェクトを一緒に整理 ——チェインアドレス法

オープンアドレッシング法#

オープンアドレッシング法 (Open Addressing) では、一度衝突が発生した場合（その位置に他の要素が既にある）、何らかの規則に従って別の空きアドレスを探す。その利点はハッシュテーブルが配列であり、ストレージ効率が高く、ランダム検索が可能であること、欠点はハッシュテーブルに「集約」現象があること。オープンアドレスハッシュ法では削除操作に非常に注意が必要で、「怠惰な削除」しかできず、実際の削除ではなく削除マークを追加する必要があり、検索時に「断鎖」しないようにする。その空間は次回の挿入時に再利用できる。

• i 回目の衝突が発生した場合、次の試行アドレスはd~i~を加算する、基本公式は：h~i~(key) = (h(key) + d~i~) mode TableSize(1 ≤ i < TableSize)
• d~i~の値は異なる衝突解決方案を決定する：線形探索 (d~i~ = i)、平方探索 (d~i~ = ± i^2^)、二重ハッシュ (d~i~ = i*h~2~(key))。

① 線形探索法#

増分系列 1、2、……、（TableSize - 1）で次の保存アドレスを循環試行する。

② 平方探索法（二次探索）#

増分系列 1^2^、-1^2^、2^2^、-2^2^、……、q^2^、-q^2^ かつ q ≤ | TableSize/2 | で次の保存アドレスを循環試行する。


平方探索法で全ての空間を探し出せるか？以下の定理がある：

• ハッシュテーブルの長さ TableSize がある4k+3（k は正整数）形式の素数である場合、平方探索法はハッシュテーブル全体の空間を探査できる

//Key要素を検索する、ここでは平方探索法で衝突を処理
Index Find(ptrHash H, DataType Key) {
    Index nowp, newp;
    int Cnum = 0;//衝突回数を記録
    newp = nowp = Hash(Key, H->TableSize);
    //その位置の単位が空でなく、探している要素でない場合に衝突が発生
    while(H->Units[newp].flag != Empty && H->Units[newp].data != Key) {
        ++Cnum;//衝突が1回増加
        if(++Cnum % 2) {
            newp = nowp + (Cnum+1)*(Cnum+1)/4;//増分は+i^2、iは(Cnum+1)/2
            if(newp >= H->TableSize)
                newp = newp % H->TableSize;
        } else {
            newp = nowp - Cnum*Cnum/4;//増分は-i^2、iはCnum/2
            while(newp < 0)
                newp += H->TableSize;
        }
    }
    return newp;//位置を返す、その位置が空の単位の位置であれば見つからないことを示す
}

③ 二重ハッシュ探索法#

d~i~ は i*h~2~(key)、h~2~(key) は別のハッシュ関数であり、探索系列は h~2~(key)、2h~2~(key)、3h~2~(key)……

• 任意の key に対して、h~2~(key) ≠ 0！
• 探索系列はすべてのハッシュストレージユニットが探索できることを保証する必要があり、以下の形式を選択することで良好な効果が得られる：h~2~(key) = p - (key mod p)
  ここで p < TableSize、p、TableSize はともに素数

分離リンク法#

分離リンク法 (Separate Chaining) では、対応する位置で衝突したすべてのキーワードを単一のリンクリストに保存する。利点はキーワードの削除が「怠惰な削除法」を必要とせず、ストレージのゴミがないこと、欠点はリンクリスト部分のストレージ効率と検索効率が比較的低いこと。リンクリストの長さの不均一は時間効率の著しい低下を引き起こす

（4）ハッシュ検索の操作セット（コード）#

ここでは文字列のハッシュ検索を示し、Hash 関数は移位法を採用し、衝突処理にはオープンアドレッシング法の平方探索法を使用し、他はその基礎の上で変更すればよい

定義#

const int MaxSize = 100000;
typedef int Index;//ハッシュ後のインデックス
typedef string DataType;//ハッシュ単位に保存される要素の型
//ハッシュ単位の状態型、合法的な要素、空の単位、削除された要素にそれぞれ対応
typedef enum {Legitimate, Empty, Deleted} EntryType;
struct HashNode {   //ハッシュテーブル単位の型
    DataType data;      //要素を保存
    EntryType flag;     //単位の状態
};
struct HashTable {  //ハッシュテーブルの型
    int TableSize;      //テーブルの長さ
    HashNode *Units;	//ハッシュ単位を保存する配列
};
typedef HashTable *ptrHash;

素数の取得#

N より大きく MaxSize を超えない最小の素数を返し、ハッシュテーブルの最大長さを素数に保ち、できるだけキーワードに対応するアドレス空間が均等に分布するようにする

//Nより大きくMaxSizeを超えない最小の素数を返し、ハッシュテーブルの最大長さを素数に保つ
int NextPrime(int N) {
    int i, p = (N%2) ? N+2 : N+1;//Nより大きい次の奇数pから始める
    while(p <= MaxSize) {
        for(i = (int)sqrt(p); i >= 2; i--) 
            if(!(p % i)) break;//素数でない
        if(i == 2) break;//forが正常に終了、素数である
        else p += 2;//次の奇数を試す
    }
    return p;
}

空のテーブルを作成#

TableSize より長い空のテーブルを作成する。（長さを素数にすることを保証）

ptrHash CreateTable(int TableSize) {
    ptrHash H;
    int i;
    H = new HashTable;
    H->TableSize = NextPrime(TableSize);
    H->Units = new HashNode[H->TableSize];
    for(int i = 0; i < H->TableSize; ++i) 
        H->Units[i].flag = Empty;
    return H;
}

ハッシュ計算#

ハッシュ関数計算後のインデックスを返す、ここでキーワードデータ型は string、移位法を使用

Index Hash(DataType Key, int TableSize) { 
    unsigned int h = 0; //ハッシュ関数値、初期値は0
    string str = Key.str;
    int len = str.length();
    for(int i = 0; i < len; ++i) 
        h = (h << 5) + str[i];
    return h % TableSize;
}

検索操作#

Key 要素を検索する、ここでは平方探索法で衝突を処理し、位置インデックスを返す、その位置が空の単位の位置であれば見つからないことを示す

Index Find(ptrHash H, DataType Key) {
    Index nowp, newp;
    int Cnum = 0;//衝突回数を記録
    newp = nowp = Hash(Key, H->TableSize);
    //その位置の単位が空でなく、探している要素でない場合に衝突が発生
    while(H->Units[newp].flag != Empty && H->Units[newp].data != Key) {
        ++Cnum;//衝突が1回増加
        if(++Cnum % 2) {
            newp = nowp + (Cnum+1)*(Cnum+1)/4;//増分は+i^2、iは(Cnum+1)/2
            if(newp >= H->TableSize)
                newp = newp % H->TableSize;
        } else {
            newp = nowp - Cnum*Cnum/4;//増分は-i^2、iはCnum/2
            while(newp < 0)
                newp += H->TableSize;
        }
    }
    return newp;//位置を返す、その位置が空の単位の位置であれば見つからないことを示す
}

挿入操作#

Key をテーブルに挿入し、挿入成功または失敗を返す、失敗した場合はそのキー値が既に存在することを示す

bool Insert(ptrHash H, DataType Key) {
    Index p = Find(H, Key);
    if(H->Units[p].flag != Legitimate) {//その位置に要素を挿入できる
        H->Units[p].flag = Legitimate;
        H->Units[p].data = Key;
        //他の操作
        return true;
    } else {//そのキー値は既に存在する
        //他の操作
        return false;
    }
}

（5）性能分析#

ハッシュテーブルの検索効率は以下の要素によって分析される：

• 成功平均検索長（ASLs）
• 不成功平均検索長（ASLu）

線形探索法の例題を用いてこのハッシュテーブルの性能を分析する

• そのASLsは検索テーブル内のキーワードの平均検索比較回数（すなわちその衝突回数に 1 を加えたもの）
  ASLs = （1+7+1+1+2+1+4+2+4）/ 9 = 23 / 9 ≈ 2.56
• そのASLuはハッシュテーブルに存在しないキーワードの平均検索比較回数（不成功）
  一般的な方法：ハッシュテーブルに存在しないキーワードをいくつかのクラスに分け、H (key) 値で分類する場合、ここでの H (key) = key mod 11、11 クラスで分析し、ASLu は以下の通り
  ASLu = （3+2+1+2+1+1+1+9+8+7+6）/ 11 = 41 / 11 ≈ 3.73

キーワードの比較回数は、衝突の発生数に依存し、衝突の発生数に影響を与える要素は以下の三つである

1. ハッシュ関数が均等であるか
2. 衝突処理の方法
3. ハッシュテーブルのロードファクター α
   異なる衝突処理方法とロードファクターが効率に与える影響は以下の通り

① 線形探索法の検索性能#

② 平方探索法と二重ハッシュ探索法の検索性能#

ロードファクター α<0.5 のとき、さまざまな探索法の期待探索回数はあまり大きくなく、比較的近い。α が増加するにつれて、線形探索法の期待探索回数は急速に増加し、不成功の検索と挿入操作の期待探索回数は成功の検索の期待探索回数よりも大きくなる。したがって、合理的な最大装入因子は 0.85 を超えてはならない

③ 分離リンク法の検索性能#

まとめ#

• ** 適切な h (key) を選択すれば、ハッシュ法の検索効率の期待値は定数 O (1)** であり、ほぼキーワードの空間のサイズ n に依存しない！また、キーワードの直接比較計算量が大きい問題にも適している
• それは小さな αを前提としているため、ハッシュ法は時間を空間で交換する方法である
• ハッシュ法のストレージはキーワードに対してランダムであり、順序検索には不便であり、また範囲検索や最大値最小値の検索にも適していない。