C++でオープンアドレッシング（線形プロービング）によるハッシュテーブルを自作する方法

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

線形プロービング（Linear Probing）は、オープンアドレッシング方式のハッシュテーブルにおける衝突解決手法の一つです。この方式では、ハッシュテーブルの各セルには1つのキーと値のペアのみが格納されます。新しいキーが、すでに別のキーで占有されているセルにマッピングされると衝突が発生します。その場合、この手法はテーブル内で最も近い空きスロットを順次探索し、そこに新しいキーを挿入します。

本記事では、C++で線形プロービングによるハッシュテーブルを実装するプログラムを紹介します。

アルゴリズム

挿入処理：Insert(int k, int v)

Begin
    Declare function Insert(int k, int v)
        Declare hash_val, init, delindex to the integer pointer.
            initialize hash_val = HashFunc(k)
            initialize init = -1
            initialize delindex = -1
        while (hash_val != init and (ht[hash_val]
            == DelNode::getNode() or ht[hash_val]
            != NULL and ht[hash_val]->k != k))
                if (init == -1)
                    init = hash_val
                if (ht[hash_val] == DelNode::getNode())
                    delindex = hash_val
                hash_val = HashFunc(hash_val + 1)
        if (ht[hash_val] == NULL or hash_val == init)
            if(delindex != -1)
                ht[delindex] = new HashTable(k, v)
            else
                ht[hash_val] = new HashTable(k, v)
        if(init != hash_val)
            if (ht[hash_val] != DelNode::getNode())
                if (ht[hash_val] != NULL)
                    if (ht[hash_val]->k== k)
                        ht[hash_val]->v = v
            else
                ht[hash_val] = new HashTable(k, v)
End.

検索処理：SearchKey(int k)

Begin
    Declare Function SearchKey(int k)
        Declare hash_val, init of the integer datatype.
            initialize hash_val = HashFunc(k)
            initialize init = -1
        while (hash_val != init and (ht[hash_val]
            == DelNode::getNode() or ht[hash_val]
            != NULL and ht[hash_val]->k!= k))
                if (init == -1)
                    init = hash_val
                hash_val = HashFunc(hash_val + 1)
        if (ht[hash_val] == NULL or hash_val == init)
            return -1
        else
            return ht[hash_val]->v
End.

削除処理：Remove(int k)

Begin
    Declare Function Remove(int k)
        Declare hash_val, init of the integer datatype.
            initialize hash_val = HashFunc(k)
            initialize init = -1
        while (hash_val != init and (ht[hash_val]
            == DelNode::getNode() or ht[hash_val]
            != NULL and ht[hash_val]->k!= k))
                if (init == -1)
                    init = hash_val
                hash_val = HashFunc(hash_val + 1)
        if (hash_val != init and ht[hash_val] != NULL)
            delete ht[hash_val]
            ht[hash_val] = DelNode::getNode()
End.

サンプルコード

以下は、線形プロービングによるハッシュテーブルをC++で実装した完全なサンプルコードです。削除済みスロットを表す特殊なノード（DelNode）を用意することで、削除後も検索チェーンが途切れないようにしている点がポイントです。

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int T_S = 5;
class HashTable {
    public:
        int k;
        int v;
        HashTable(int k, int v) {
            this->k = k;
            this->v = v;
        }
};
class DelNode:public HashTable {
    private:
        static DelNode *en;
        DelNode():HashTable(-1, -1) {}
    public:
        static DelNode *getNode() {
            if (en == NULL)
                en = new DelNode();
            return en;
        }
};
DelNode *DelNode::en = NULL;
class HashMapTable {
    private:
        HashTable **ht;
    public:
        HashMapTable() {
            ht = new HashTable* [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_val = HashFunc(k);
            int init = -1;
            int delindex = -1;
            while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k != k)) {
                if (init == -1)
                    init = hash_val;
                if (ht[hash_val] == DelNode::getNode())
                    delindex = hash_val;
                    hash_val = HashFunc(hash_val + 1);
            }
            if (ht[hash_val] == NULL || hash_val == init) {
                if(delindex != -1)
                    ht[delindex] = new HashTable(k, v);
                else
                    ht[hash_val] = new HashTable(k, v);
            }
            if(init != hash_val) {
                if (ht[hash_val] != DelNode::getNode()) {
                    if (ht[hash_val] != NULL) {
                        if (ht[hash_val]->k== k)
                            ht[hash_val]->v = v;
                    }
                } else
                    ht[hash_val] = new HashTable(k, v);
            }
        }
        int SearchKey(int k) {
            int hash_val = HashFunc(k);
            int init = -1;
            while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k!= k)) {
                if (init == -1)
                    init = hash_val;
                    hash_val = HashFunc(hash_val + 1);
            }
            if (ht[hash_val] == NULL || hash_val == init)
                return -1;
            else
                return ht[hash_val]->v;
        }
        void Remove(int k) {
            int hash_val = HashFunc(k);
            int init = -1;
            while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k!= k)) {
                if (init == -1)
                    init = hash_val;
                    hash_val = HashFunc(hash_val + 1);
            }
            if (hash_val != init && ht[hash_val] != NULL) {
                delete ht[hash_val];
                ht[hash_val] = DelNode::getNode();
            }
        }
        ~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;
                    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;
}

実行結果

上記のプログラムをコンパイルして実行すると、以下のような対話的な操作が可能になります。テーブルサイズは5（T_S = 5）なので、キー6の要素はハッシュ値1の位置に、キー8の要素はハッシュ値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: 10
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: 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: 1
Enter element to be inserted: 12
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: 15
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: 15
Enter key at which element to be inserted: 8
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: 2
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: 2
No element found at key 2
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 4

まとめ

この記事では、C++を使ってオープンアドレッシング（線形プロービング）方式のハッシュテーブルをゼロから実装する方法を解説しました。挿入・検索・削除の各操作において、衝突が発生した場合はハッシュ値を1つずつ進めながら空きスロットを探すのが基本的な動作です。また、要素を単純にNULLにするのではなく、削除マーカー（DelNode）を残すことで、削除後も検索や挿入のチェーンが正しく機能するようになっています。ハッシュテーブルの内部動作を理解したい方にとって、良い学習材料となるでしょう。