This is the 12th section of C++ basic syntax sharing, today to share a hash table!
Hash table
HashTable. CPP:
#include<stdio.h>
#include<stdlib.h>
#define SUCCESS 1
#define UNSUCCESS 0
#define OVERFLOW -1
#define OK 1
#define ERROR -1
#define MAXNUM 9999 #define MAXNUM 9999
typedef int Status;
typedef int KeyType;
// Hash the record type in the table
typedef struct {
KeyType key;
}RcdType;
// Hash table type
typedef struct {
RcdType *rcd;
int size;
int count;
int *tag;
}HashTable;
// The size of the hash table grows after each reconstruction
int hashsize[] = { 11, 31, 61, 127, 251, 503 };
int index = 0;
// Initial hash table
Status InitHashTable(HashTable &H, int size) {
int i;
H.rcd = (RcdType *)malloc(sizeof(RcdType)*size);
H.tag = (int *)malloc(sizeof(int)*size);
if (NULL == H.rcd || NULL == H.tag) return OVERFLOW;
KeyType maxNum = MAXNUM;
for (i = 0; i < size; i++) {
H.tag[i] = 0;
H.rcd[i].key = maxNum;
}
H.size = size;
H.count = 0;
return OK;
}
// hash function: division remainder method
int Hash(KeyType key, int m) {
return (3 * key) % m;
}
// Handle hash collisions: linear detection
void collision(int &p, int m) {
p = (p + 1) % m;
}
// Query in the hash table
Status SearchHash(HashTable H, KeyType key, int &p, int &c) {
p = Hash(key, H.size);
int h = p;
c = 0;
while ((1 == H.tag[p] && H.rcd[p].key ! = key) || -1 == H.tag[p]) {
collision(p, H.size); c++;
}
if (1 == H.tag[p] && key == H.rcd[p].key) return SUCCESS;
else return UNSUCCESS;
}
// Print the hash table
void printHash(HashTable H)
{
int i;
printf(“key : “);
for (i = 0; i < H.size; i++)
printf(“%3d “, H.rcd[i].key);
printf(“\n”);
printf(“tag : “);
for (i = 0; i < H.size; i++)
printf(“%3d “, H.tag[i]);
printf(“\n\n”);
}
// Insert hash table
Status InsertHash(HashTable &H, KeyType key);
// Rebuild the hash table
Status recreateHash(HashTable &H) {
RcdType *orcd;
int *otag, osize, i;
orcd = H.rcd;
otag = H.tag;
osize = H.size;
InitHashTable(H, hashsize[index++]);
// Put all elements in the new table according to the new hash function
for (i = 0; i < osize; i++) {
if (1 == otag[i]) {
InsertHash(H, orcd[i].key);
}
}
return OK;
}
// Insert hash table
Status InsertHash(HashTable &H, KeyType key) {
int p, c;
If (UNSUCCESS == SearchHash(H, key, p, c)) {// No same key
If (c*1.0 / h.size < 0.5) {// The number of conflicts does not reach the upper limit
// Insert code
H.rcd[p].key = key;
H.tag[p] = 1;
H.count++;
return SUCCESS;
}
else recreateHash(H); // Refactor the hash table
}
return UNSUCCESS;
}
// Delete the hash table
Status DeleteHash(HashTable &H, KeyType key) {
int p, c;
if (SUCCESS == SearchHash(H, key, p, c)) {
// Delete the code
H.tag[p] = -1;
H.count–;
return SUCCESS;
}
else return UNSUCCESS;
}
int main()
{
Printf (“—– hash table —–\n”);
HashTable H;
int i;
int size = 11;
KeyType array[8] = { 22, 41, 53, 46, 30, 13, 12, 67 };
KeyType key;
// Initialize the hash table
Printf (” initialize hash \n”);
If (SUCCESS == InitHashTable(H, hashsize[index++])) printf(” initialize SUCCESS \n”);
// Insert hash table
Printf (” insert hash table \n”);
for (i = 0; i <= 7; i++) {
key = array[i];
InsertHash(H, key);
printHash(H);
}
// Delete the hash table
Printf (” delete element \n from hash table with key 12 “);
int p, c;
if (SUCCESS == DeleteHash(H, 12)) {
Printf (” delete successfully, at this time the hash table is: \n”);
printHash(H);
}
// query the hash table
Printf (” select element with key 67 \n”);
If (SUCCESS == SearchHash(H, 67, p, c)) printf(” query successful \n”);
// Insert again to test the reconstruction of the hash table
Printf (” Insert again to test the reconstruction of the hash table: \n”);
KeyType array1[8] = { 27, 47, 57, 47, 37, 17, 93, 67 };
for (i = 0; i <= 7; i++) {
key = array1[i];
InsertHash(H, key);
printHash(H);
}
getchar();
return 0;
}
concept
Hash function H(key): K -> D, key ∈ K
A constructor
Direct addressing
Divisor remainder method
Numerical analysis method
Folding method
Square the middle
Conflict handling methods
Linked address method: use a single linked list for the same key
Open addressing method:
(1) Linear detection method: the key is the same -> put in the next position of the key, Hi = (H(key) + I) % m
(2) double detection method: same key -> put Di = 1^2, -1^2… , ± (k)^2,(k<=m/2)
(3) Random detection method: H = (H(key) + pseudo-random number) % m
Linear probe hash table data structure
Hash table data structures and images for linear probes
typedef char KeyType;
typedef struct {
KeyType key;
}RcdType;
typedef struct {
RcdType *rcd;
int size;
int count;
bool *tag;
}HashTable;
Copy the code
This is the end of today’s sharing, you must learn C++ yo ~
For those of you who are ready to learn C/C++ programming, if you want to improve your core programming skills, you might as well start now!
C language C++ programming learning exchange circle, QQ group [904329806] wechat official number: C language programming learning base
Organize and share (years of learning source code, project actual combat video, project notes, basic introduction tutorial)
Welcome to change careers and learn programming partners, use more information to learn and grow faster than their own thinking oh!