Bảng băm là một cấu trúc dữ liệu được sử dụng để lưu trữ các cặp khóa-giá trị. Hàm băm được sử dụng bởi bảng băm để tính toán một chỉ mục vào một mảng trong đó một phần tử sẽ được chèn hoặc tìm kiếm.
Băm kép là một kỹ thuật giải quyết xung đột trong bảng Hash bổ sung mở. Hàm băm kép sử dụng ý tưởng sử dụng hàm băm thứ hai để khóa khi xảy ra xung đột.
Đây là một chương trình C ++ để triển khai chuỗi Hash Tables với hàm băm kép.
Thuật toán
Để tìm kiếm một khóa:
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
Để chèn:
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
Đối với màn hình:
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.
Đối với hàm rehash:
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.
Mã mẫu
#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;
}
Đầu ra
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