C++で実装するリストヘッド連鎖（チェイン法）ハッシュテーブル

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

本記事では、リストヘッド（List Head）によるチェイン法（連鎖法）を用いたハッシュテーブルをC++で実装する方法を解説します。チェイン法では、同一のハッシュ値を持つ複数の要素を連結リストでつなぎ、各バケットの先頭ノードを「リストヘッド」として管理します。これにより、ハッシュ値の衝突が発生しても、リストをたどることですべての要素へアクセスできます。

アルゴリズム

挿入（Insert）

開始
　　関数 Insert(int k, int v) を宣言
　　　　int hash_v = HashFunc(k)
　　　　if (ht[hash_v] == NULL)
　　　　　　ht[hash_v] = new ListHead(k, v)
　　　　else
　　　　　　ListHead *en = ht[hash_v]
　　　　　　while (en->n != NULL)
　　　　　　　　en = en->n
　　　　　　if (en->k == k)
　　　　　　　　en->v = v
　　　　　　else
　　　　　　　　en->n = new ListHead(k, v)
終了

ハッシュ関数でキーのハッシュ値を求めます。該当バケットが空であれば新規ノードを作成し、すでにリストが存在する場合は末尾まで走査します。同じキーが見つかれば値を更新し、なければ新しいノードを連結します。

検索（SearchKey）

開始
　　関数 SearchKey(int k) を宣言
　　　　int hash_v = HashFunc(k)
　　　　if (ht[hash_v] == NULL)
　　　　　　return -1
　　　　else
　　　　　　ListHead *en = ht[hash_v]
　　　　　　while (en != NULL かつ en->k != k)
　　　　　　　　en = en->n
　　　　　　if (en == NULL)
　　　　　　　　return -1
　　　　　　else
　　　　　　　　return en->v
終了

ハッシュ値に対応するバケットの連結リストを先頭から順に走査し、指定されたキーと一致するノードを探します。一致するノードがあればその値を返し、見つからなければ -1 を返します。

削除（Remove）

開始
　　関数 Remove(int k) を宣言
　　　　int hash_v = HashFunc(k)
　　　　if (ht[hash_v] != NULL)
　　　　　　ListHead *en = ht[hash_v]
　　　　　　ListHead *p = NULL
　　　　　　while (en->n != NULL かつ en->k != k)
　　　　　　　　p = en
　　　　　　　　en = en->n
　　　　　　if (en->k == k)
　　　　　　　　if (p == NULL)
　　　　　　　　　　ListHead *n = en->n
　　　　　　　　　　delete en
　　　　　　　　　　ht[hash_v] = n
　　　　　　　　else
　　　　　　　　　　ListHead *n = en->n
　　　　　　　　　　delete en
　　　　　　　　　　p->n = n
終了

削除対象ノードとその直前のノードを追跡しながらリストを走査します。対象ノードが見つかったらメモリを解放し、先頭ノードの場合はバケットの参照を次ノードへ付け替え、中間ノードの場合は前ノードのポインタを次ノードへ接続し直します。

サンプルコード

#include <iostream>
using namespace std;
const int T_S = 20;
class ListHead {
    public:
        int k, v;
        ListHead *n;
        ListHead(int k, int v) {
            this->k = k;
            this->v = v;
            this->n = NULL;
        }
};
class HashMapTable {
    private:
        ListHead **ht;
    public:
        HashMapTable() {
            ht = new ListHead*[T_S];
            for (int i = 0; i < T_S; i++) {
                ht[i] = NULL;
            }
        }
        int HashFunc(int k){
            return k % T_S;
        }
        void Insert(int k, int v) {
            int hash_v = HashFunc(k);
            if (ht[hash_v] == NULL)
                ht[hash_v] = new ListHead(k, v);
            else {
                ListHead *en = ht[hash_v];
                while (en->n != NULL)
                    en = en->n;
                if (en->k == k)
                    en->v = v;
                else
                    en->n = new ListHead(k, v);
            }
        }
        int SearchKey(int k) {
            int hash_v = HashFunc(k);
            if (ht[hash_v] == NULL)
                return -1;
            else {
                ListHead *en = ht[hash_v];
                while (en != NULL && en->k != k)
                    en = en->n;
                if (en == NULL)
                    return -1;
                else
                    return en->v;
            }
        }
        void Remove(int k) {
            int hash_v = HashFunc(k);
            if (ht[hash_v] != NULL) {
                ListHead *en = ht[hash_v];
                ListHead *p = NULL;
                while (en->n != NULL && en->k != k) {
                    p = en;
                    en = en->n;
                }
                if (en->k == k) {
                    if (p == NULL) {
                        ListHead *n = en->n;
                        delete en;
                        ht[hash_v] = n;
                    }
                    else {
                        ListHead *n = en->n;
                        delete en;
                        p->n = n;
                    }
                }
            }
        }
        ~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;
                if (hash.SearchKey(k) == -1)
                    cout<<"No element found at key "<<k<<endl;
                else {
                    cout<<"Elements at key "<<k<<" : ";
                    cout<<hash.SearchKey(k)<<endl;
                }
            break;
            case 3:
                cout<<"Enter key of the element to be deleted: ";
                cin>>k;
                if (hash.SearchKey(k) == -1)
                    cout<<"Key "<<k<<" is empty"<<endl;
                else {
                    hash.Remove(k);
                    cout<<"Entry Removed"<<endl;
                }
            break;
            case 4:
                exit(1);
            default:
                cout<<"\nEnter correct option\n";
        }
    }
    return 0;
}

このプログラムでは、テーブルサイズ T_S を 20 とし、ハッシュ関数は「キー % テーブルサイズ」でインデックスを算出しています。main 関数ではメニュー形式のループにより、挿入・検索・削除・終了の操作を選択できる対話的な動作を実現しています。

なお、上記のデストラクタでは配列本体のみを解放しているため、厳密には各ノードを順に delete してから配列を解放すると、より安全な実装になります。

実行結果

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: 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: 10
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: 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: 12
Enter key at which element to be inserted: 4
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 30
Enter correct option
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: 30
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
Elements 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
Entry Removed
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
Elements 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: 4

まとめ

リストヘッドによるチェイン法を用いれば、ハッシュ値の衝突が発生しても連結リストで柔軟に対応でき、平均 O(1) の時間計算量で挿入・検索・削除を行えます。一方で、多数のキーが同一のハッシュ値に集中した場合、最悪 O(n) となる点には注意が必要です。実務では、テーブルサイズやハッシュ関数の設計を工夫することで、衝突を抑え性能を安定させることが重要です。