C++で線形プロービングによるハッシュテーブルを実装する方法

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

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

本記事では、線形プロービングを用いたハッシュテーブルをC++で実装する方法を、アルゴリズムの解説とサンプルコード付きで紹介します。

アルゴリズム

挿入（Insert）の場合

Begin
    Declare Function Insert(int k, int v)
      int hash_val = HashFunc(k)
      intialize init = -1
      intialize 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 || 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.

キーの検索（Search）の場合

Begin
    Declare Function SearchKey(int k)
      int hash_val = HashFunc(k)
      int 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.

削除（Delete）の場合

Begin
    Declare Function Remove(int k)
      int hash_val = HashFunc(k)
      intialize 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 && 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;
}

実行結果

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

まとめ

このプログラムでは、ハッシュ関数として「k % T_S」（テーブルサイズでの剰余）を使用しています。衝突が発生した場合は、インデックスを1つずつ進めながら空きセルを探す線形プロービングで対応します。また、要素を削除する際には単純にNULLを代入せず、削除マーカー（DelNode）を配置することで、その後の検索や挿入が正しく動作するようになっています。メニュー形式の対話型インターフェースにより、挿入・検索・削除の各操作を実際に試しながら、線形プロービングの動作を確認できます。