#include <bits/stdc++.h>
using namespace std;
template <typename T>
class Node {
public:
string key;
T value;
Node<T>* next;
Node(string key, T val) {
this->key = key;
value = val;
next = NULL;
}
~Node() {
while (next != NULL) {
delete next;
}
}
};
template <typename T>
class Hashtable {
Node<T>** table;
int tableSize;
int currentSize;
int hashFn(string key){
int idx = 0;
int power = 1;
for(int j = 0; j < key.length(); j++){
idx = idx + (key[j] * power) % tableSize;
idx = idx % tableSize;
power = (power * 27) % tableSize;
}
return idx;
}
void rehash(){
Node<T>** oldTable = table;
int oldTableSize = tableSize;
tableSize = 2*tableSize;
table = new Node<T>*[tableSize];
for (int i = 0; i < tableSize; i++){
table[i] = NULL;
}
currentSize = 0;
//shift elements from oldTable to Table;
for(int i = 0; i < oldTableSize; i++){
Node<T>* temp = oldTable[i];
while(temp != NULL){
insert(temp->key, temp->value);
temp = temp->next;
}
if (oldTable[i] != NULL){
delete oldTable[i];
//the delete keyword triggers the destructor, and the linked list
//present at oldTable[i] gets deleted recursively
}
}
delete [] oldTable;
//this deletes the oldTable
}
public:
Hashtable(int ts = 7) {
tableSize = ts;
table = new Node<T>*[tableSize];
currentSize = 0;
for (int i = 0; i < tableSize; i++) {
table[i] = NULL;
}
//we set each of the pointers in table to NULL instead of garbage value
}
void print(){
for(int i = 0; i < tableSize; i++){
cout << "Bucket: " << i << "->";
Node<T>* temp = table[i];
while(temp != NULL){
cout << temp->key << " ";
temp = temp->next;
}
cout << endl;
}
}
void insert(string key, T value) {
int idx = hashFn(key);
Node<T>* n = new Node<T>(key, value);
//inserting each new node at head. This would mean that the recently added node
//woudl be the head of LL
n->next = table[idx];
table[idx] = n;
currentSize++;
// cout << currentSize << endl;
// print();
// rehash
float loadFactor = (1.0 * currentSize) / (1.0 * tableSize);
// cout << loadFactor << endl;
if(loadFactor > 0.7){
rehash();
}
}
// T* search(string key) {
// //the return type is T* because we return a pointer
// int idx = hashFn(key);
// Node<T>* temp = table[idx];
// while(temp != NULL){
// if (temp->key == key){
// return &temp->value;
// }
// temp = temp->next;
// }
// return NULL;
// }
};
