C++でのオープンアドレッシング線形プロービングによる独自のハッシュテーブルの実装

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

線形プロービングは、オープンアドレスハッシュテーブルの衝突解決手法です。この方法では、ハッシュテーブルの各セルに単一のキーと値のペアが格納されます。別のキーによってすでに占有されているハッシュテーブルのセルに新しいキーをマッピングすることによって衝突が発生した場合。このメソッドは、テーブルで次の最も近い空き場所を検索し、そこに新しいキーを挿入します。

これは、線形プロービングを使用してハッシュテーブルを実装するためのC++プログラムです。

アルゴリズム

Begin
   Declare function Insert(int k, int v)
      Declare hash_val, init, delindex to the integer pointer.
         initialize 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 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.

キー値を検索する場合：

Begin
   Declare Function SearchKey(int k)
      Declare hash_val, init of the integer datatype.
         initialize 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 (ht[hash_val] == NULL or hash_val == init)
            return -1
         else
            return ht[hash_val]->v
End.

削除の場合：

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.

サンプルコード

#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