二次プロービングでハッシュテーブルを実装するC++プログラム

ハッシュテーブルは、キーと値のペアを格納するために使用されるデータ構造です。ハッシュ関数は、要素が挿入または検索される配列へのインデックスを計算するためにハッシュテーブルによって使用されます。二次プロービングは、オープンアドレスハッシュテーブルの衝突解決手法です。元のハッシュインデックスを取得し、空きスロットが見つかるまで任意の2次多項式の連続する値を追加することで動作します。

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

アルゴリズム

キー値を検索する場合：

Begin
   Declare function SearchKey(int k, HashTable *ht)
      int pos = HashFunc(k, ht->s)
      intialize collisions = 0
      while (ht->t[pos].info != Emp and ht->t[pos].e != k)
         pos = pos + 2 * ++collisions -1
         if (pos >= ht->s)
            pos = pos - ht->s
      return pos
End.

挿入の場合：

Begin
   Declare function Insert(int k, HashTable *ht)
      int pos = SearchKey(k, ht)
      if (ht->t[pos].info != Legi)
         ht->t[pos].info = Legi
         ht->t[pos].e = k
End.

表示用：

Begin
   Declare function display(HashTable *ht)
      for (int i = 0; i < ht->s; i++)
         int value = ht->t[i].e
         if (!value)
            print"Position: "
               print the current position
            Print" Element: Null"
         else
            print"Position: "
               print the current position
            Print" Element: "
               Print the element.
End.

リハッシュ機能の場合：

Begin
   Declare function Rehash(HashTable *ht)
      int s = ht->s
      HashTableEntry *t= ht->t
      ht= initiateTable(2 * s)
      for (int i = 0; i < s; i++)
         if (t[i].info == Legi)
            Insert(t[i].e, ht)
      free(t)
      return ht
End.
Source Code:

サンプルコード

#include <iostream>
#include <cstdlib>
#define T_S 10
using namespace std;
enum EntryType {
   Legi, Emp, Del};
   struct HashTableEntry {
      int e;
      enum EntryType info;
   };
   struct HashTable {
      int s;
      HashTableEntry *t;
   };
   bool isPrime (int n) {
   if (n == 2 || n == 3)
      return true;
   if (n == 1 || n % 2 == 0)
      return false;
   for (int i = 3; i * i <= n; i += 2)
      if (n % i == 0)
         return false;
   return true;
}
int nextPrime(int n) {
   if (n <= 0)
      n == 3;
   if (n % 2 == 0)
      n++;
   for (; !isPrime( n ); n += 2);
      return n;
}
int HashFunc(int k, int s) {
   return k % s;
}
HashTable *initiateTable(int s) {
   HashTable *ht;
   if (s < T_S) {
      cout<<"Table Size is Too Small"<<endl;
      return NULL;
   }
   ht= new HashTable;
   if (ht == NULL) {
      cout<<"Out of Space"<<endl;
      return NULL;
   }
   ht->s = nextPrime(s);
   ht->t = new HashTableEntry [ht->s];
   if (ht->t == NULL) {
      cout<<"Table Size is Too Small"<<endl;
      return NULL;
   }
   for (int i = 0; i < ht->s; i++) {
      ht->t[i].info = Emp;
      ht->t[i].e = NULL;
   }
   return ht;
}
int SearchKey(int k, HashTable *ht) {
   int pos = HashFunc(k, ht->s);
   int collisions = 0;
   while (ht->t[pos].info != Emp && ht->t[pos].e != k) {
      pos = pos + 2 * ++collisions -1;
      if (pos >= ht->s)
         pos = pos - ht->s;
   }
   return pos;
}
void Insert(int k, HashTable *ht) {
   int pos = SearchKey(k, ht);
   if (ht->t[pos].info != Legi) {
      ht->t[pos].info = Legi;
      ht->t[pos].e = k;
   }
}
HashTable *Rehash(HashTable *ht) {
   int s = ht->s;
   HashTableEntry *t= ht->t;
   ht= initiateTable(2 * s);
   for (int i = 0; i < s; i++) {
      if (t[i].info == Legi)
         Insert(t[i].e, ht);
   }
   free(t);
   return ht;
}
void display(HashTable *ht) {
   for (int i = 0; i < ht->s; i++) {
      int value = ht->t[i].e;
      if (!value)
         cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
      else
         cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
   }
}
int main() {
   int v, s, pos, i = 1;
   int c;
   HashTable *ht;
   while(1) {
      cout<<"1.Initialize size of the table"<<endl;
      cout<<"2.Insert element into the table"<<endl;
      cout<<"3.Display Hash Table"<<endl;
      cout<<"4.Rehash The Table"<<endl;
      cout<<"5.Exit"<<endl;
      cout<<"Enter your choice: ";
      cin>>c;
      switch(c) {
         case 1:
            cout<<"Enter size of the Hash Table: ";
            cin>>s;
            ht = initiateTable(s);
            cout<<"Size of Hash Table: "<<nextPrime(s);
         break;
         case 2:
            if (i > ht->s) {
               cout<<"Table is Full, Rehash the table"<<endl;
               continue;
            }
            cout<<"Enter element to be inserted: ";
            cin>>v;
            Insert(v, ht);
            i++;
         break;
         case 3:
            display(ht);
         break;
         case 4:
            ht = Rehash(ht);
         break;
         case 5:
            exit(1);
         default:
            cout<<"\nEnter correct option\n";
      }
   }
   return 0;
}

出力

1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 4
Table Size is Too Small
Size of Hash Table: 51.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 10
Size of Hash Table: 111.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 1
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 2
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 3
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 4
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 5
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 6
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 7
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 8
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 9
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 10
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 11
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 11
Position: 2 Element: 1
Position: 3 Element: 2
Position: 4 Element: 3
Position: 5 Element: 4
Position: 6 Element: 5
Position: 7 Element: 6
Position: 8 Element: 7
Position: 9 Element: 8
Position: 10 Element: 9
Position: 11 Element: 10
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 4
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: 1
Position: 3 Element: 2
Position: 4 Element: 3
Position: 5 Element: 4
Position: 6 Element: 5
Position: 7 Element: 6
Position: 8 Element: 7
Position: 9 Element: 8
Position: 10 Element: 9
Position: 11 Element: 10
Position: 12 Element: 11
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: Null
Position: 18 Element: Null
Position: 19 Element: Null
Position: 20 Element: Null
Position: 21 Element: Null
Position: 22 Element: Null
Position: 23 Element: Null
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 20
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 5