C++で学ぶチェイン法（連鎖法）によるハッシュテーブルの実装

ハッシュ化とは、任意の長さのデータ要素を固定サイズのキーへマッピングする手法のことです。ハッシュは「キーと値のペア」として動作します。

ハッシュ関数は、ハッシュマップ内でマッピングを担う関数です。ハッシュ関数に入力された複数のデータ要素が、同じハッシュキーを持つことがあります。この場合、要素同士が衝突（オーバーラップ）してしまいます。同じハッシュキーを持つ要素の衝突を回避するために考案されたのが「チェイン法（連鎖法）」という概念です。

ハッシュマップの作成

ハッシュマップを作成するには、データ要素のインデックス値を決定するハッシュ関数が必要です。

ここでは、n個のバケットを持つハッシュテーブルを用意します。ハッシュテーブルにノードを挿入する際は、次のハッシュ関数を使用します。

hashIndex = key % バケット数

このハッシュ関数を用いて、ハッシュマップに挿入するすべての値のハッシュインデックスを計算します。

• 要素の挿入：キー値からハッシュインデックスを計算し、そのリストの末尾に新しいノードを追加します。

• ノードの削除：ハッシュインデックスを計算し、対応するバケット内を検索して該当要素を見つけ、削除します。

サンプルコード

#include<iostream>
#include <list>
using namespace std;
class Hash{
    int BUCKET;
    list < int >*table;
    public:
    Hash (int V);
    void insertItem (int x);
    void deleteItem (int key);
    int hashFunction (int x){
        return (x % BUCKET);
    }
    void displayHash ();
};
Hash::Hash (int b){
    this->BUCKET = b;
    table = new list < int >[BUCKET];
}
void Hash::insertItem (int key){
    int index = hashFunction (key);
    table[index].push_back (key);
}
void Hash::deleteItem (int key){
    int index = hashFunction (key);
    list < int >::iterator i;
    for (i = table[index].begin (); i != table[index].end (); i++){
    if (*i == key)
        break;
    }
    if (i != table[index].end ())
        table[index].erase (i);
}
void Hash::displayHash (){
    for (int i = 0; i < BUCKET; i++){
        cout << i;
        for (auto x:table[i])
        cout << " --> " << x;
        cout << endl;
    }
}
 int main (){
    int a[] = { 5, 12, 67, 9, 16 };
    int n = 5;
    Hash h (7);
    for (int i = 0; i < n; i++)
    h.insertItem (a[i]);
    h.deleteItem (12);
    h.displayHash ();
    return 0;
}

実行結果

0
1
2 --> 9 --> 16
3
4 --> 67
5 --> 5
6

このプログラムでは、7個のバケットを持つハッシュテーブルを作成し、値 {5, 12, 67, 9, 16} を挿入した後、キー「12」を削除しています。同じインデックスに割り当てられた要素（例：9 と 16）は、連結リストで連鎖的に管理されていることが出力から確認できます。