C ++程序使用双重哈希实现哈希表
哈希表是一种数据结构，用于存储键值对。哈希表使用哈希函数来计算要插入或搜索元素的数组的索引。
双重哈希是开放地址哈希表中的冲突解决技术。双散列使用在发生冲突时使用第二个散列函数进行键输入的思想。
这是一个使用双重哈希实现哈希表链接的C ++程序。
算法
对于搜索键：
BeginDeclare 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
用于显示：
BeginDeclare 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.
对于重新哈希功能：
BeginDeclare 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 table2.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
以上是 C ++程序使用双重哈希实现哈希表 的全部内容， 来源链接： utcz.com/z/350190.html
