C++でダブルハッシングを使ったハッシュテーブルを実装する方法

ハッシュテーブルとダブルハッシングとは

ハッシュテーブルは、キーと値のペアを効率的に格納・管理するためのデータ構造です。ハッシュテーブルでは、ハッシュ関数を使って、要素を挿入または検索する配列上のインデックス（位置）を計算します。

ダブルハッシング（Double Hashing）は、オープンアドレス法を採用したハッシュテーブルにおける衝突解決手法の一つです。キーを挿入する際に衝突が発生すると、2つ目のハッシュ関数を使って次の探索位置を決定します。この方式により、線形探索法などと比べてデータの偏り（クラスタリング）を抑えられるのが特徴です。

本記事では、ダブルハッシングを用いてハッシュテーブルを実装するC++プログラムを紹介します。

アルゴリズム

キーの検索

Begin
    Declare Function SearchKey(int k, HashTable *ht)
      int hashVal= HashFunc1(k, ht->s)
      int stepSize= HashFunc2(k, ht->s)
      while (ht->t[hashVal].info != Emp and
          ht->t[hashVal].e != k)
             hashVal = hashVal + stepSize
             hashVal = hashVal % ht->s
      return hashVal
End

まず1つ目のハッシュ関数（HashFunc1）で初期位置を求め、2つ目のハッシュ関数（HashFunc2）でステップ幅を計算します。空きスロットまたは目的のキーが見つかるまで、ステップ幅ずつ位置を進めながら探索を繰り返します。

要素の挿入

Begin.
    Declare Function Insert(int k, HashTable *ht)
       int pos = SearchKey(k, ht)
       if (ht->t[pos].info != Legi )
          ht->t[pos].info = Legi
          ht->t[pos].e = k
End

SearchKey関数で挿入すべき位置を特定し、その位置がまだ有効なエントリ（Legi）として使用されていなければ、そこへ新しいキーを登録します。

テーブルの表示

Begin
    Declare function display(HashTable *ht)
       for (int i = 0; i < ht->s; i++)
           int v= ht->t[i].e;
           if (!v)
              Print "Position: "
                 Print the position of the pointer
              Print " Element: Null"
           else
              Print "Position: "
                 Print the position of the pointer
              Print " Element: "
                 Print the element
End.

テーブル内のすべてのスロットを先頭から順に走査し、各位置に格納されている要素を出力します。空きスロットは「Null」として表示されます。

再ハッシュ処理

Begin
    Declare function Rehash(HashTable *ht)
       int s = ht->s
       HashTableEntry *t= ht->t
       ht = initiateTable(2*s)
       for (int i = 0; i < s; i++)
           if (t[i].info == Legi)
              Insert(t[i].e, ht)
       free(t)
       return ht
End.

テーブルが満杯に近づいた場合、現在の2倍のサイズを持つ新しいテーブルを作成し、既存の有効な要素をすべて挿し直します。最後に古いテーブルのメモリを解放します。

サンプルコード

#include <iostream>
#include <cstdlib>
#define T_S 5
using namespace std;
enum EntryType {Legi, Emp};
struct HashTableEntry {
    int e;
    enum EntryType info;
};
struct HashTable {
    int s;
    HashTableEntry *t;
};
int HashFunc1(int k, int s) {
    return k % s;
}
int HashFunc2(int k, int s) {
    return (k * s - 1) % s;
}
HashTable *initiateTable(int s) {
    HashTable *ht;
    if (s < T_S) {
        cout<<"Table Size is Too Small"<<endl;
        return NULL;
    }
    ht= new HashTable;
    if (ht == NULL) {
        cout<<"Out of Space"<<endl;
        return NULL;
    }
    ht->s = s;
    ht->t = new HashTableEntry[ht->s];
    if (ht->t== NULL) {
        cout<<"Table Size is Too Small"<<endl;
        return NULL;
    }
    for (int i = 0; i < ht->s; i++) {
        ht->t[i].info = Emp;
        ht->t[i].e=NULL;
    }
    return ht;
}
int SearchKey(int k, HashTable *ht) {
    int hashVal= HashFunc1(k, ht->s);
    int stepSize= HashFunc2(k, ht->s);
    while (ht->t[hashVal].info != Emp &&
        ht->t[hashVal].e != k) {
            hashVal = hashVal + stepSize;
            hashVal = hashVal % ht->s;
        }
        return hashVal;
}
void Insert(int k, HashTable *ht) {
    int pos = SearchKey(k, ht);
    if (ht->t[pos].info != Legi ) {
        ht->t[pos].info = Legi;
        ht->t[pos].e = k;
    }
}
void display(HashTable *ht) {
    for (int i = 0; i < ht->s; i++) {
        int v= ht->t[i].e;
        if (!v)
            cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
        else
            cout<<"Position: "<<i + 1<<" Element: "<<v<<endl;
    }
}
HashTable *Rehash(HashTable *ht) {
    int s = ht->s;
    HashTableEntry *t= ht->t;
    ht = initiateTable(2*s);
    for (int i = 0; i < s; i++) {
        if (t[i].info == Legi)
            Insert(t[i].e, ht);
    }
    free(t);
    return ht;
}
int main() {
    int v, s, pos, i = 1;
    int c;
    HashTable *ht;
    while(1) {
        cout<<"1.Initialize size of the table"<<endl;
        cout<<"2.Insert element into the table"<<endl;
        cout<<"3.Display Hash Table"<<endl;
        cout<<"4.Rehash Hash Table"<<endl;
        cout<<"5.Exit"<<endl;
        cout<<"Enter your choice: ";
        cin>>c;
        switch(c) {
            case 1:
                cout<<"Enter size of the Hash Table: ";
                cin>>s;
                ht = initiateTable(s);
            break;
            case 2:
                if (i > ht->s) {
                    cout<<"Table is Full, Rehash the table"<<endl;
                    continue;
                }
                cout<<"Enter element to be inserted: ";
                cin>>v;
                Insert(v, ht);
                i++;
            break;
            case 3:
                display(ht);
            break;
            case 4:
                ht= Rehash(ht);
            break;
            case 5:
                exit(1);
            default:
            cout<<"\nEnter correct option\n";
        }
    }
    return 0;
}

コードのポイント

HashFunc1： キーをテーブルサイズで割った余りを返す基本的なハッシュ関数です。
HashFunc2： 衝突時のステップ幅を計算する2つ目のハッシュ関数です。テーブルサイズとの組み合わせで周期性を避けます。
initiateTable： テーブルサイズが最小値（T_S = 5）未満の場合はエラーを返し、メモリ確保後に全スロットを空き状態（Emp）で初期化します。
Rehash： 要素数が上限に達したときにテーブルを2倍に拡張し、全要素を再配置することで、挿入を継続できるようにします。

実行結果

1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 4
Table Size is Too Small
Enter your choice: 1
Enter size of the Hash Table: 10
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 1
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 3
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 4
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 5
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 6
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 7
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 8
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice:
9
Enter correct option
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 9
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 10
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 11
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 12
Enter correct option
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 3
Position: 1 Element: 10
Position: 2 Element: 1
Position: 3 Element: 11
Position: 4 Element: 3
Position: 5 Element: 4
Position: 6 Element: 5
Position: 7 Element: 6
Position: 8 Element: 7
Position: 9 Element: 8
Position: 10 Element: 9
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 4
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: 1
Position: 3 Element: Null
Position: 4 Element: 3
Position: 5 Element: 4
Position: 6 Element: 5
Position: 7 Element: 6
Position: 8 Element: 7
Position: 9 Element: 8
Position: 10 Element: 9
Position: 11 Element: 10
Position: 12 Element: 11
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: Null
Position: 18 Element: Null
Position: 19 Element: Null
Position: 20 Element: Null
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 20
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 3
Position: 1 Element: 20
Position: 2 Element: 1
Position: 3 Element: Null
Position: 4 Element: 3
Position: 5 Element: 4
Position: 6 Element: 5
Position: 7 Element: 6
Position: 8 Element: 7
Position: 9 Element: 8
Position: 10 Element: 9
Position: 11 Element: 10
Position: 12 Element: 11
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: Null
Position: 18 Element: Null
Position: 19 Element: Null
Position: 20 Element: Null
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 5

実行例では、まずサイズ4のテーブル作成が最小サイズ未満のため拒否され、サイズ10で再作成されています。その後、要素を順次挿入していき、テーブルが満杯になると「Rehash」を選択することでテーブルが20に拡張され、全要素が再配置されていることが確認できます。

C++でローリングハッシュを実装する方法｜Rabin-Karp法による文字列検索を解説

C++で単方向リンクリストによるチェイン法ハッシュテーブルを実装する方法

C++で基数ソート（ラディックスソート）を実装するプログラム
基数ソート（ラディックスソート）は、非比較型のソートアルゴリズムの一つです。要素同士を直接比較するのではなく、整数キーを構成する各桁に注目し、同じ桁位置・同じ値を持つ数字どうしをグループ化しながら並べ替えを行います。「基数」とは記数法における底のことです。私たちが普段使う10進法では基数は10であるため、10進数を基数ソートで並べ替える際には、数値を一時的に格納するための10個のバケット（ポケット）が必要になります。基数ソートの計算量時間計算量： O(nk)　※nは要素数、kは最大桁数空間計算量： O(n+k) 入力 − ソート前のデータ： 802 630 20 745 52 3
C++でクイックソートを実装するプログラム|ランダム化で最悪ケースO(n²)を回避
クイックソート(Quick Sort)は「分割統治法(divide-and-conquer)」に基づく高速な整列アルゴリズムです。平均時間計算量は O(n log n) と非常に効率的ですが、ピボットの選び方次第では最悪ケースで O(n²) まで計算量が悪化する可能性があります。そこで本記事では、乱数を用いてピボットをランダムに選択する「ランダム化クイックソート」をC++で実装し、最悪ケースが発生する確率を大幅に下げる方法を解説します。アルゴリズム Partition(int a[], int l, int h) 配列 a の範囲 [l, h] を、ピボットより小さいグループと大きい