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

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

本記事では、単方向リンクリスト(シングルリンクリスト)によるチェイン法を用いてハッシュテーブルを実装するC++プログラムを紹介します。チェイン法を採用することで、異なるキーが同じハッシュ値を持つ「衝突」が発生しても、各バケットをリンクリストとして連結することで適切に対応できます。

アルゴリズム

挿入(Insert)

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

削除(Remove)

開始
    関数 Remove(int k) を宣言
        int hash_v = HashFunc(k)
        HashTableEntry* en = ht[hash_v]
        HashTableEntry* p = NULL
        if (en == NULL または en->k != k)
            「キーに要素が見つかりません」を出力
            return
        while (en->n != NULL)
            p = en
            en = en->n
        if (p != NULL)
            p->n = en->n
        delete en
            「要素を削除しました」を出力
終了。

キーによる値の検索(SearchKey)

開始
    関数 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)
                    「キーに要素が見つかりました」を出力
                    en->v を出力
                en = en->n
        if (!flag)
            「キーに要素が見つかりません」を出力
終了。

サンプルコード

#include <iostream>
const int T_S = 200;
using namespace std;
struct HashTableEntry {
    int v, k;
    HashTableEntry *n;
    HashTableEntry *p;
    HashTableEntry(int k, int v) {
        this->k = k;
        this->v = v;
        this->n = NULL;
    }
};
class HashMapTable {
    public:
        HashTableEntry **ht, **top;
        HashMapTable() {
            ht = new HashTableEntry*[T_S];
            for (int i = 0; i < T_S; i++)
                ht[i] = NULL;
        }
        int HashFunc(int key) {
            return key % T_S;
        }
        void Insert(int k, int v) {
            int hash_v = HashFunc(k);
            HashTableEntry* p = NULL;
            HashTableEntry* en = ht[hash_v];
            while (en!= NULL) {
                p = en;
                en = en->n;
            }
            if (en == NULL) {
                en = new HashTableEntry(k, v);
                if (p == NULL) {
                    ht[hash_v] = en;
                } else {
                    p->n = en;
                }
            } else {
                en->v = v;
            }
        }
        void Remove(int k) {
            int hash_v = HashFunc(k);
            HashTableEntry* en = ht[hash_v];
            HashTableEntry* p = NULL;
            if (en == NULL || en->k != k) {
                cout<<"No Element found at key "<<k<<endl;
                return;
            }
            while (en->n != NULL) {
                p = en;
                en = en->n;
            }
            if (p != NULL) {
                p->n = en->n;
            }
            delete en;
            cout<<"Element Deleted"<<endl;
        }
        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->v<<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<<"\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: 2
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: 3
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: 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: 8
Enter key at which element to be inserted: 9
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: 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: 3
Enter key of the element to be deleted: 9
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

コードのポイント

• テーブルサイズとハッシュ関数: テーブルサイズは定数 T_S = 200 として定義されており、ハッシュ関数は「key % T_S」でバケットのインデックスを算出します。
• 衝突への対処(チェイン法): 各バケットは単方向リンクリストの先頭ポインタを保持しています。ハッシュ値が同じ要素が複数あっても、リストの末尾へ新しいノードを連結することで問題なく格納できます。
• 計算量: 挿入・検索・削除は平均的に O(1) で動作しますが、多くの要素が同一バケットに集中する最悪ケースでは O(n) となる点に注意が必要です。