Scribd
Upload
3 views2 pages

HashTable Implement

The document contains C++ code implementing two hash table techniques: close addressing (chaining) and open addressing. It defines structures for nodes, hash functions, and methods for inserting and searching key-value pairs. The code includes error handling for cases such as key collisions and table overflow.

Uploaded by

Zid
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
3 views2 pages

HashTable Implement

The document contains C++ code implementing two hash table techniques: close addressing (chaining) and open addressing. It defines structures for nodes, hash functions, and methods for inserting and searching key-value pairs. The code includes error handling for cases such as key collisions and table overflow.

Uploaded by

Zid
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

#include <iostream>

#include <string>
using namespace std;
#define MAX 10

//////////////////////////////////////////////////
//CLOSE_ADDRESSING/CHAINING
struct Node{
string key;
int value;
Node* next;
}

Node* HashTable[MAX] = {NULL};

int HashFunction(string key){


int sum = 0;

for(int i=0; i<[Link](); i++){


sum += key[i];
}

return sum % MAX;


}

void insert(string key, int value){


int index = HashFunction(key);

Node* temp = HashTable[index];


while(temp != NULL){
if(temp->key = key){
temp->value = value;
return;
}
temp = temp->next;
}

Node* newNode = new Node;


newNode->key = key;
newNode->value = value;

newNode->next = HashTable[index];
HashTable[index] = newNode;
}

int Search(string key){


int index = HashFunction(key);

Node* temp = HashTable[index];


while(temp != NULL){
if(temp->key = key){
return temp->value;
}
temp = temp->next;
}

return -1;
}
/////////////////////////////////
//OPEN_ADDRESSING

struct node{
string key;
int value;
}

node* hashTable[MAX] = {nullptr};

node* DELETED = new node{"", -1};

void insert(string key, int value) {


int index = hashFunction(key);
int originalIndex = index;

while (hashTable[index] != NULL && hashTable[index] != DUMMY_DELETED) {

if (hashTable[index]->key == key) {
hashTable[index]->value = value;
return;
}

index = (index + 1) % TABLE_SIZE;

if (index == originalIndex) {
cout << "Bảng băm đã đầy (Overflow)!" << endl;
return;
}
}

HashItem* newItem = new HashItem();


newItem->key = key;
newItem->value = value;
hashTable[index] = newItem;
}

int search(string key) {


int index = hashFunction(key);
int originalIndex = index;

while (hashTable[index] != NULL) {

if (hashTable[index] != DUMMY_DELETED && hashTable[index]->key == key) {


return hashTable[index]->value;
}

index = (index + 1) % TABLE_SIZE;

if (index == originalIndex) break;


}

return -1;
}

You might also like