C++で双方向リンクリストを使ったハッシュテーブル（チェイン法）を実装する方法

ハッシュテーブルは、キーと値のペアを格納するためのデータ構造です。ハッシュ関数を使用することで、要素を挿入または検索する配列のインデックスを効率的に計算できます。

本記事では、双方向リンクリストを用いたチェイン法によるハッシュテーブルをC++で実装する方法を解説します。

アルゴリズム

要素の挿入（insert）

Begin
    Declare Function insert(int k, int v)
      int hash_v = HashFunc(k)
      HashTableEntry *en = ht[hash_v]
      if (en == NULL)
          en = new HashTableEntry
          en->d = v
          en->k = k
          en->n = NULL
          en->p = NULL
          ht[hash_v] = en
          top[hash_v] = en
      else
          while (en != NULL)
              en = en->n
          en = new HashTableEntry
          en->d = v
          en->k = k
          en->n = NULL
          en->p = top[hash_v]
          top[hash_v]->n = en
          top[hash_v] = en
End

挿入処理では、まずハッシュ関数でキーからインデックスを算出します。該当バケットが空であれば新しいノードを作成して先頭に設定し、すでに要素が存在する場合はリスト末尾まで移動してから新しいノードを連結します。前ポインタ（p）と次ポインタ（n）の両方を適切に設定する点が、双方向リンクリストならではの特徴です。

要素の削除（remove）

Begin
    Declare function remove(int k)
      int hash_v = HashFunc(k)
      HashTableEntry *en = ht[hash_v]
      if (en->k != k || en == NULL)
          Print No Element found at key
          return
      while (en != NULL)
          if (en->n == NULL)
              if (en->p == NULL)
                  ht[hash_v] = NULL
                  top[hash_v] = NULL
                  delete en
                  break
              else
                  top[hash_v] = en->p
                  top[hash_v]->n = NULL
                  delete en
                  en = top[hash_v]
          en = en->n
End

削除処理では、指定されたキーに対応するバケットを探索し、該当するノードを見つけて解放します。ノードがリスト内で唯一の要素である場合はバケット全体をNULLに戻し、それ以外の場合は末尾ポインタを一つ前に戻してリンクを切り離します。

キーの検索（SearchKey）

Begin
    Declare function SearchKey(int k)
      int hash_v = HashFunc(k)
      bool flag = false
      HashTableEntry* en = ht[hash_v]
      if (en != NULL)
          while (en != NULL)
              if (en->k == k)
                  flag = true
              if (flag)
                  Print Element found at key
                  print en->d
              en = en->n
          if (!flag)
              Print “No Element found at key.”
End.

検索処理では、ハッシュ値に対応するバケットのリストを先頭から順に走査し、キーが一致したノードの値を出力します。最後まで見つからなければ「要素が見つかりません」のメッセージを表示します。

サンプルコード

以下は、上記のアルゴリズムを実際にC++で実装した完全なプログラムです。メニュー形式のコンソールアプリケーションとして、挿入・検索・削除の操作を対話的に行えます。

#include <iostream>
const int T_S = 200;
using namespace std;
struct HashTableEntry {
    int d, k;
    HashTableEntry *n;
    HashTableEntry *p;
};
class HashMapTable {
    public:
        HashTableEntry **ht, **top;
        HashMapTable() {
            ht = new HashTableEntry*[T_S];
            top = new HashTableEntry*[T_S];
            for (int i = 0; i < T_S; i++) {
                ht[i] = NULL;
                top[i] = NULL;
            }
        }
        int HashFunc(int key) {
            return key % T_S;
        }
        void insert(int k, int v) {
            int hash_v = HashFunc(k);
            HashTableEntry *en = ht[hash_v];
            if (en == NULL) {
                en = new HashTableEntry;
                en->d = v;
                en->k = k;
                en->n = NULL;
                en->p = NULL;
                ht[hash_v] = en;
                top[hash_v] = en;
            } else {
                while (en != NULL)
                    en = en->n;
                en = new HashTableEntry;
                en->d = v;
                en->k = k;
                en->n = NULL;
                en->p = top[hash_v];
                top[hash_v]->n = en;
                top[hash_v] = en;
            }
        }
        void remove(int k) {
            int hash_v = HashFunc(k);
            HashTableEntry *en = ht[hash_v];
            if (en == NULL) {
                cout<<"No Element found at key: "<<k<<endl;
                return;
            }
            while (en != NULL) {
                if (en->n == NULL) {
                    if (en->p == NULL) {
                        ht[hash_v] = NULL;
                        top[hash_v] = NULL;
                        delete en;
                        break;
                    } else {
                        top[hash_v] = en->p;
                        top[hash_v]->n = NULL;
                        delete en;
                        en = top[hash_v];
                    }
                }
                en = en->n;
            }
        }
        void SearchKey(int k) {
            int hash_v = HashFunc(k);
            bool flag = false;
            HashTableEntry* en = ht[hash_v];
            if (en != NULL) {
                while (en != NULL) {
                    if (en->k == k) {
                        flag = true;
                    }
                    if (flag) {
                        cout<<"Element found at key "<<k<<": ";
                        cout<<en->d<<endl;
                    }
                    en = en->n;
                }
            }
            if (!flag)
                cout<<"No Element found at key "<<k<<endl;
        }
        ~HashMapTable() {
            delete [] ht;
        }
};
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;
                hash.SearchKey(k);
                break;
            case 3:
                cout<<"Enter key of the element to be deleted: ";
                cin>>k;
                hash.remove(k);
                break;
            case 4:
                exit(1);
            default:
                cout<<"
Enter correct option
";
        }
    }
    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: 3
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: 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: 2
Enter key of the element to be searched: 6
Element found 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
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 4

まとめ

このプログラムでは、テーブルサイズ200のハッシュテーブルを構築し、衝突が発生した場合は同じバケット内に双方向リンクリストで要素を連結するチェイン法を採用しています。ハッシュ関数には単純な剰余演算（key % T_S）を使用しており、各操作の平均計算量はO(1)、最悪時はO(n)となります。

双方向リンクリストを使用することで、単方向リストと比べてノードの前後関係をたどりやすくなり、削除処理などの実装が柔軟になります。データ構造の学習や、ハッシュテーブルの内部動作の理解にぜひ役立ててください。