C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

ダブルハッシュを使用してハッシュテーブルを実装するC++プログラム

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

ダブルハッシュは、オープンアドレスハッシュテーブルの衝突解決手法です。ダブルハッシュは、衝突が発生したときに2番目のハッシュ関数を使用してキーを設定するという考え方を使用しています。

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

アルゴリズム

キーを検索するには： 

Begin
   Declare Function SearchKey(int k, HashTable *ht)
      int hashVal= HashFunc1(k, ht->s)
      int stepSize= HashFunc2(k, ht->s)
      while (ht->t[hashVal].info != Emp and
         ht->t[hashVal].e != k)
            hashVal = hashVal + stepSize
            hashVal = hashVal % ht->s
      return hashVal
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 v= ht->t[i].e;
         if (!v)
            Print "Position: "
               Print the position of the pointer
            Print " Element: Null"
         else
            Print "Position: "
               Print the position of the pointer
            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.



サンプルコード

#include <iostream>
#include <cstdlib>
#define T_S 5
using namespace std;
enum EntryType {Legi, Emp};
struct HashTableEntry {
   int e;
   enum EntryType info;
};
struct HashTable {
   int s;
   HashTableEntry *t;
};
int HashFunc1(int k, int s) {
   return k % s;
}
int HashFunc2(int k, int s) {
   return (k * s - 1) % 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 = 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 hashVal= HashFunc1(k, ht->s);
   int stepSize= HashFunc2(k, ht->s);
   while (ht->t[hashVal].info != Emp &&
      ht->t[hashVal].e != k) {
         hashVal = hashVal + stepSize;
         hashVal = hashVal % ht->s;
      }
      return hashVal;
}
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;
   }
}
void display(HashTable *ht) {
   for (int i = 0; i < ht->s; i++) {
      int v= ht->t[i].e;
      if (!v)
         cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
      else
         cout<<"Position: "<<i + 1<<" Element: "<<v<<endl;
   }
}
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;
}
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 Hash 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);
         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 Hash Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 4
Table Size is Too Small
Enter your choice: 1
Enter size of the Hash Table: 10
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash 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 Hash 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 Hash 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 Hash 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 Hash 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 Hash 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 Hash 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 Hash Table
5.Exit
Enter your choice:
9
Enter correct option
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash 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 Hash 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 Hash 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 Hash 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 Hash Table
5.Exit
Enter your choice: 12
Enter correct option
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash 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 Hash 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 Hash Table
5.Exit
Enter your choice: 3
Position: 1 Element: 10
Position: 2 Element: 1
Position: 3 Element: 11
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
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash 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 Hash Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: 1
Position: 3 Element: Null
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
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash 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 Hash Table
5.Exit
Enter your choice: 3
Position: 1 Element: 20
Position: 2 Element: 1
Position: 3 Element: Null
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
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 5



  1. 基数ソートを実装するC++プログラム

    基数ソートは、非比較ソートアルゴリズムです。この並べ替えアルゴリズムは、同じ位置と値を共有する数字をグループ化することにより、整数キーで機能します。基数は、記数法のベースです。 10進法では、基数または基数は10であることがわかっているので、いくつかの10進数を並べ替えるには、数値を格納するために10個の位取りボックスが必要です。 基数ソート手法の複雑さ 時間計算量：O（nk） スペースの複雑さ：O（n + k） Input − The unsorted list: 802 630 20 745 52 300 612 932 78 187 Output &minus

  2. 与えられた複雑さの制約でクイックソートを実装するC++プログラム

    クイックソートは分割統治法に基づいています。このアルゴリズムの平均時間計算量はO（n * log（n））ですが、最悪の場合の複雑さはO（n ^ 2）です。ここで最悪のケースの可能性を減らすために、クイックソートはランダム化を使用して実装されています。 アルゴリズム partition（int a []、int l、int h） Begin    pivot = h    Index = l    start = l and end = h    while start < end do   &nb