1. ハッシュテーブルの基本概念

順序リストや木構造では、データ要素を検索する際にキーの比較を繰り返す必要があります。比較回数を減らすためには、データ要素の格納位置とキーの値の間に関連性を確立する必要があります。この目的のために、ハッシュ技術を用いた動的検索表が使用されます。まず、いくつかの基本概念を理解しましょう。

1. ハッシュ関数：データ要素のキーの値と格納位置の間に確立される対応関係。
2. ハッシュテーブル：キーの値をハッシュ関数で変換して格納位置を取得するこのような格納方式で構築されたデータ構造。
3. ハッシュアドレス：ハッシュ関数によってデータ要素の格納位置が決定され、その位置をハッシュアドレスと呼びます。
4. ハッシュ検索：指定されたキーを受け取り、ハッシュ関数でテーブル内のアドレスに変換し、その位置に目的の要素があるかどうかを確認します。存在すればその要素を返し、存在しなければそこに挿入します。

理想的な状況では、使用するハッシュ関数によって各キー値が一意のハッシュアドレスに対応しますが、実際のアプリケーションでは、このような状況はほとんどありません。2つの要素のキー値が等しくないのに、ハッシュ関数で変換した結果のハッシュアドレスが同じになる場合、これが衝突を引き起こします。ハッシュ関数はキーの集合からアドレスの集合への写像であるため、一般的に衝突は完全に避けることはできず、可能な限り減らすしかありません。したがって、ハッシュ技術を採用する際には、2つの問題を考慮する必要があります。

1. 「均一な」ハッシュ関数をどのように選択するか？
   良いハッシュ関数は、計算が簡単で、演算速度が速く、ランダム性が高く、アドレスができるだけ均一に分布し、衝突が少ないことが求められます。
2. 衝突を効果的に解決するにはどの方法を使用するか？
   衝突を解決する方法については、以下のハッシュテーブルの実装で説明します。

2. 主なハッシュ法

2.1. 数字分析法

数字分析法、または数字選択法は、考えられるすべてのキーの値を収集し、並べ替えてキーの各桁を分析し、分布が比較的均一な桁を選んでハッシュアドレスを構成する方法です。選択する桁数はハッシュテーブルのサイズに依存します。テーブルサイズが100の場合、2桁で十分です。

考えられるキーの値が以下のようであるとします。

すべてのキーの値を分析すると、左から3桁目までは「7 1 2」となっており、第5桁は1または4、第7桁は6、7、8のいずれかしか取れないため、これらの5桁は使用できません。残りの4、6、8、9桁は分布が比較的均一であるため、これらまたはその中のいくつかを組み合わせてハッシュアドレスとして使用できます。

2.2. 除算剰余法

除算剰余法は、シンプルかつ効果的で最も一般的に使用される構成方法です。ハッシュテーブルのサイズn以下の正の整数pを選択し、キーの値をpで割った余りをハッシュアドレスとします。この方法の鍵はpの選択にあります。pの選択が適切でないと、衝突が発生しやすくなります。通常、以下のルールに従うべきです。

1. pは偶数を取らない。
2. pはキーの文字セットのn倍を取らない。
3. 一般的にpはテーブルサイズに最も近い素数を選択します。

2.3. 平方中位法

平方中位法は、キーの値の2乗の中央の数桁をハッシュアドレスとして使用します。この方法は計算が簡単で、ハッシュ関数を決定する際によく使用される方法です。ハッシュ関数を決定する際にキーの分布が不明な場合、どの桁を使用するかが適切でない可能性がありますが、数値の2乗の中央の数桁はその数値のすべての桁に関連しているため、得られるハッシュアドレスは比較的均一になります。

2.4. 基数変換法

キーの値を別の基数系の数値と見なし、元の基数系の数値に変換してから、その中の数桁を選んでハッシュアドレスとします。

例えば、十進数のキー値443730を十三進数と見なし、十進数に変換し、ハッシュテーブルのサイズに基づいて数桁を選んでハッシュアドレスとします。

3. ハッシュテーブルの実装

衝突は避けられないため、ハッシュ技術を採用する際の2番目の問題は、衝突をどのように解決するかです。

衝突が発生した場合、一定の規則に従ってそのアドレスの次のアドレスを選択します。まだ衝突する場合は、規則に従ってさらに次のアドレスを選択し、このプロセスを衝突が発生しなくなるまで続けます。

衝突を解決するために一般的に使用される方法は以下の通りです。

3.1. 線形探査法

任意のキー key に対して、H(key) = d とし、ハッシュテーブルの容量をmとすると、線形探査法で生成される後続のハッシュアドレスは以下のようになります。

d+1, d+2, ..., m-1, 0, 1, ..., d-1

例えば、長さ13のハッシュテーブルがあり、ハッシュ関数が H(key) = key mod 13 であるとします。テーブルにはすでにキー値16、30、54の要素が格納されています。ここでキー値29の要素を挿入しようとします。ハッシュ関数はハッシュアドレス3を求めますが、アドレス3にはすでに要素16が存在し、衝突が発生します。線形探査法を適用すると、次のアドレスは d+1=4 となり、まだ衝突します。そのため、さらに次のアドレス d+2 = 5 を求めます。この位置には要素がありませんので、要素をハッシュテーブルのインデックス5のセルに格納します。

上記の例からわかるように、線形探査法で生成される後続のハッシュアドレスの計算は簡単ですが、連続したアドレスを探査するため、同義語ではない要素間で同じハッシュアドレスをめぐって競合する現象が発生しやすくなります。これをクラスタリング（集積現象）と呼びます。クラスタリングの機会を減らすためには、後続のハッシュアドレスがハッシュテーブル全体にできるだけ均一に分布するようにする必要があります。

3.2. 二次探査法

二次探査法の基本的な考え方は、後続のハッシュアドレスが連続的ではなく、飛び跳ねるようにすることで、後続のデータ要素のためにスペースを残し、クラスタリングを減らすことです。二次探査法に従えば、キー key のハッシュアドレスのシーケンスは以下のようになります。

(d + i^2) mod m ただし、mはハッシュテーブルのサイズ、i = 1^2, -1^2, 2^2, -2^2, ..., k^2, -k^2 で、k <= m/2 となります。

例えば、線形探査法の例と同じハッシュテーブルとハッシュ関数を使用し、キー値29の要素を挿入します。衝突が発生した場合、二次探査法を使用すると、次のアドレスは d1 = (3 + 1^2) mod 13 = 4 となり、まだ衝突します。そのため、さらに次のアドレス d2 = (3 - 1^2) mod 13 = 2 を求め、まだ衝突します。ハッシュアドレスが d3 = (3 + 2^2) mod 13 = 7 になるまで続け、この位置に要素がないため、要素をハッシュテーブルのインデックス7の位置に格納します。

二次探査法の欠点は、ハッシュテーブルの全ての領域を探査できない可能性があることです。つまり、上記の後続のハッシュアドレスがハッシュテーブルのすべての格納位置をカバーできない可能性があります。

3.3. チェイン法

チェイン法は、各同義語（衝突したキー）に対して単方向リストを構築して衝突を解決する方法です。

選択されたハッシュ関数Hがあり、Hの値域（ハッシュアドレスの範囲）が0~(n-1)であるとします。ポインタの配列Pointer HP[n]を設定します。各ポインタHP[i]は単方向リストを指し、そのリストはハッシュアドレスがiのデータ要素を格納するために使用されます。このような各単方向リストを同義語サブリストと呼びます。

例えば、選択されたハッシュ関数が H(key) = key mod 13 であり、キー値26、41、25、05、07、15、12、49、51、31、62が格納されているハッシュテーブルを考えます。

3.4. 複数ハッシュ法

この方法では、複数のハッシュ関数H_i（i=1, ..., k）を設定する必要があります。指定された値keyがハッシュテーブル内の値と、あるハッシュ関数H_iに関して同義語である場合に衝突が発生したら、次のハッシュ関数H_i+1でのkeyのハッシュアドレスを計算し続け、衝突が発生しなくなるまで続けます。この方法の利点は、クラスタリングが発生しにくい点ですが、欠点は計算量が大きい点です。

3.5. 溢出領域法

この方法のハッシュテーブルは2つの一次元配列で構成されます。一つは基本テーブルで、上記で説明したハッシュテーブルそのものであり、もう一つは溢出テーブルと呼ばれます。挿入はまず基本テーブルで行われます。もし衝突が発生したら、同義語を溢出テーブルに格納します。こうすることで、基本テーブルで衝突が発生することはありません。

4. ハッシュテーブルの基本操作アルゴリズム

4.1. チェイン法ハッシュテーブル

型定義

// テーブルサイズの定義
const int TABLE_SIZE = 20;
typedef struct HashNode {
    KeyType key;
    struct HashNode *next;
} *HashNodePtr;

typedef HashNodePtr ChainedHashTable[TABLE_SIZE];

検索アルゴリズム

HashNodePtr SearchChainedHash(KeyType key, ChainedHashTable hash_table) {
    // キーのハッシュアドレスを計算
    int index = HashFunction(key);
    // 同義語サブリストの先頭ポインタをpに代入
    HashNodePtr current = hash_table[index];
    if (current == NULL) {
        return NULL;
    }
    // リストを走査
    while (current != NULL && current->key != key) {
        current = current->next;
    }
    return current;
}

挿入アルゴリズム

void InsertChainedHash(KeyType key, ChainedHashTable hash_table) {
    if (SearchChainedHash(key, hash_table) == NULL) {
        int index = HashFunction(key);
        // 新しいノードを生成
        HashNodePtr new_node = (HashNodePtr)malloc(sizeof(struct HashNode));
        new_node->key = key;
        new_node->next = NULL;
        // 新しいノードをサブリストの先頭に挿入
        new_node->next = hash_table[index];
        hash_table[index] = new_node;
    }
}

削除アルゴリズム

void DeleteChainedHash(KeyType key, ChainedHashTable hash_table) {
    int index = HashFunction(key);

    if (hash_table[index] == NULL) {
        // 同義語サブリストが空の場合、処理を終了
        return;
    } else {
        HashNodePtr current = hash_table[index];
        // 削除対象のノードがサブリストの先頭にある場合
        if (current->key == key) {
            hash_table[index] = current->next;
            free(current);
            return;
        } else {
            // サブリストを走査
            while (current->next != NULL) {
                HashNodePtr prev = current;
                current = current->next;
                if (current->key == key) {
                    prev->next = current->next;
                    free(current);
                    return;
                }
            }
        }
    }
}

4.2. 線形探査法ハッシュテーブル

型定義

const int TABLE_CAPACITY = 20;
typedef struct {
    KeyType key;
    // 他のデータフィールドをここに追加可能
} HashSlot;
typedef HashSlot LinearHashTable[TABLE_CAPACITY];

検索アルゴリズム

int SearchLinearHash(KeyType key, LinearHashTable hash_table) {
    // ハッシュアドレスを計算
    int initial_index = HashFunction(key);
    int current_index = initial_index;
    while ((hash_table[current_index].key != EMPTY_SLOT) && (hash_table[current_index].key != key)) {
        current_index = (current_index + 1) % TABLE_CAPACITY;
    }
    if (hash_table[current_index].key == key) {
        // 検索成功
        return current_index;
    } else {
        // 検索失敗
        return -1; // 失敗を示すインデックス
    }
}