C++でハッシュテーブルを実装する方法｜アルゴリズムとサンプルコードを徹底解説

ハッシュテーブル（Hash Table）は、キーと値のペアを効率的に格納・管理するためのデータ構造です。ハッシュ関数を使ってキーから配列のインデックスを計算することで、要素の高速な挿入や検索を実現できます。

この記事では、C++によるハッシュテーブルの実装例を、アルゴリズム、サンプルコード、実行結果とあわせてわかりやすく解説します。

ハッシュテーブルの仕組み

ハッシュテーブルでは、ハッシュ関数がキーを受け取り、それを配列の添字（インデックス）へ変換します。本記事の実装では、「k mod T_S」（キーをテーブルサイズで割った余り）というシンプルなハッシュ関数を採用しています。

異なるキーが同じインデックスに対応してしまう現象は「衝突（コリジョン）」と呼ばれます。この実装では、衝突が発生した際に隣の空きスロットを順番に探す線形探査法（Linear Probing）によって衝突を解決しています。

アルゴリズム

開始
    テーブルサイズ T_S を任意の整数値で初期化する。
    構造体 hashTableEntry を定義し、キー k と値 v を宣言する。
    クラス hashMapTable を作成する：
        コンストラクタ hashMapTable() でテーブルを生成する。
        「key mod T_S」を返す関数 hashFunc() を作成する。
        指定したキーに要素を挿入する関数 Insert() を作成する。
        指定したキーの要素を検索する関数 SearchKey() を作成する。
        指定したキーの要素を削除する関数 Remove() を作成する。
        デストラクタ ~hashMapTable() で、コンストラクタが確保したオブジェクトを解放する。
    main 関数内で switch 文によりメニュー処理を行い、選択肢に応じた操作を実行する。
        キーと値の挿入には Insert() を呼び出す。
        要素の検索には SearchKey() を呼び出す。
        要素の削除には Remove() を呼び出す。
終了。

C++ サンプルコード

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
const int T_S = 200;
class HashTableEntry {
   public:
      int k;
      int v;
      HashTableEntry(int k, int v) {
         this->k = k;
         this->v = v;
      }
};
class HashMapTable {
   private:
      HashTableEntry **t;
   public:
      HashMapTable() {
         t = new HashTableEntry * [T_S];
         for (int i = 0; i< T_S; i++) {
            t[i] = NULL;
         }
      }
      int HashFunc(int k) {
         return k % T_S;
      }
      void Insert(int k, int v) {
         int h = HashFunc(k);
         while (t[h] != NULL && t[h]->k != k) {
            h = HashFunc(h + 1);
         }
         if (t[h] != NULL)
            delete t[h];
         t[h] = new HashTableEntry(k, v);
      }
      int SearchKey(int k) {
         int h = HashFunc(k);
         while (t[h] != NULL && t[h]->k != k) {
            h = HashFunc(h + 1);
         }
         if (t[h] == NULL)
            return -1;
         else
            return t[h]->v;
      }
      void Remove(int k) {
         int h = HashFunc(k);
         while (t[h] != NULL) {
            if (t[h]->k == k)
               break;
            h = HashFunc(h + 1);
         }
         if (t[h] == NULL) {
            cout<<"No Element found at key "<<k<<endl;
            return;
         } else {
            delete t[h];
         }
         cout<<"Element Deleted"<<endl;
      }
      ~HashMapTable() {
         for (int i = 0; i < T_S; i++) {
            if (t[i] != NULL)
               delete t[i];
         }
         delete[] t;
      }
};
int main() {
   HashMapTable hash;
   int k, v;
   int c;
   while (1) {
      cout<<"1.Insert element into the table"<<endl;
      cout<<"2.Search element from the key"<<endl;
      cout<<"3.Delete element at a key"<<endl;
      cout<<"4.Exit"<<endl;
      cout<<"Enter your choice: ";
      cin>>c;
      switch(c) {
         case 1:
            cout<<"Enter element to be inserted: ";
            cin>>v;
            cout<<"Enter key at which element to be inserted: ";
            cin>>k;
            hash.Insert(k, v);
         break;
         case 2:
            cout<<"Enter key of the element to be searched: ";
            cin>>k;
            if (hash.SearchKey(k) == -1) {
               cout<<"No element found at key "<<k<<endl;
               continue;
            } else {
               cout<<"Element at key "<<k<<" : ";
               cout<<hash.SearchKey(k)<<endl;
            }
         break;
         case 3:
            cout<<"Enter key of the element to be deleted: ";
            cin>>k;
            hash.Remove(k);
         break;
         case 4:
            exit(1);
         default:
            cout<<"\nEnter correct option\n";
      }
   }
   return 0;
}

実行結果

1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 1
Enter key at which element to be inserted: 1
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 2
Enter key at which element to be inserted: 2
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 4
Enter key at which element to be inserted: 5
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 7
Enter key at which element to be inserted: 6
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 7
No element found at key 7
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 6
Element at key 6 : 7
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 3
Enter key of the element to be deleted: 1
Element Deleted
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 4

コードのポイント

• HashTableEntry クラス： キー k と値 v のペアを保持するエントリです。
• HashFunc()： キーをテーブルサイズ T_S（200）で割った余りをインデックスとして返します。
• Insert()： 対象スロットが既に埋まっている場合は h+1 を再ハッシュしながら空きスロットを探します（線形探査）。同一キーが存在する場合は値を上書きします。
• SearchKey()： 目的のキーが見つかるまで線形に探査し、見つかればその値を、見つからなければ -1 を返します。
• Remove()： 該当キーのエントリを削除します。キーが存在しない場合はその旨をコンソールに表示します。
• デストラクタ： new で確保したすべてのエントリとテーブル本体のメモリを解放し、メモリリークを防止します。

ハッシュテーブルを利用することで、平均 O(1) の時間計算量でのデータ挿入・検索・削除が可能になります。ただし、テーブルの占有率が高くなると線形探査の性能が劣化するため、実用的なシステムでは負荷率（ロードファクタ）の監視やテーブルの再ハッシュ（リハッシュ）もあわせて検討するとよいでしょう。