C ++程序通过二次探测实现哈希表

哈希表是一种数据结构，用于存储键值对。哈希表使用哈希函数来计算要插入或搜索元素的数组的索引。二次探测是开放地址哈希表中的冲突解决技术。它通过获取原始哈希索引并添加任意二次多项式的连续值直到找到一个空位来进行操作。

这是一个使用二次探测实现哈希表的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<<"输入您的选择： ";
      cin>>c;
      switch(c) {
         case 1:
            cout<<"输入哈希表的大小： ";
            cin>>s;
            ht = initiateTable(s);
            cout<<"哈希表的大小： "<<nextPrime(s);
         break;
         case 2:
            if (i > ht->s) {
               cout<<"Table is Full, Rehash the table"<<endl;
               continue;
            }
            cout<<"输入要插入的元素： ";
            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
输入您的选择： 1
输入哈希表的大小： 4
Table Size is Too Small
哈希表的大小： 51.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 1
输入哈希表的大小： 10
哈希表的大小： 111.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 2
输入要插入的元素： 1
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 2
输入要插入的元素： 2
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 2
输入要插入的元素： 3
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 2
输入要插入的元素： 4
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 2
输入要插入的元素： 5
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 2
输入要插入的元素： 6
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 2
输入要插入的元素： 7
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 2
输入要插入的元素： 8
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 2
输入要插入的元素： 9
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 2
输入要插入的元素： 10
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 2
输入要插入的元素： 11
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 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
输入您的选择： 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
输入您的选择： 4
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 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
输入您的选择： 2
输入要插入的元素： 20
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
输入您的选择： 5