#include <iostream>
#include <cstring>
using namespace std;
struct elt {
int key; // to hold a unique key for each element
int data; // the data for each element
elt * next; // next element in the bucket list
};
typedef elt * Eltp; // elt pointer
class HashTableOne {
int size= 0;
Eltp * table; // array of buckets
int hash(int k){ // hash function, k= key value
int i;
for (i= 0; k; i += k++);
return i % size;
}
public:
HashTableOne(int n); // constructor, n= size of hash table array
void add(int k, int d); // function adds element to hash table, k= key value, d= data to be added (an int)
int find(int k); // function that returns data (an int) for "k" key value input (returns -1 if no key exists)
void print(); // function that prints the contents of the hash table
};
// HashTable3 class declaration:
class HashTable3 {
HashTableOne_p * table; // array of pointers to buckets
public:
HashTable3(int n1, int n2); // constructor, n1= size of main hash table, n2= size for bucket hash tables
void add(int k, int d); // adds element, k= key, d= data (an int)
int find(int key); // returns d (data) associated with key (returns -1 if key does not exist)
void print(); // prints contents of hash table, printing bucket hash tables
};
// HashTableOne constructor:
HashTableOne::HashTableOne(int n) {
size = n;
table = new Eltp [size];
for(int i=0; i < size; i++){
table[i] = NULL;
}
}
// HashTableOne add function:
void HashTableOne::add(int k, int d) {
int index = hash(k);
if(table[index] == NULL){
table[index] = new elt;
table[index]->data = d;
table[index]->key = k;
table[index]->next = NULL;
} else{
// search for the key, if found update the data
elt * p = table[index];
while(p != NULL) {
if(p->key == k){ // found one
p->data = d;
return;
}
p = p->next;
}// end while
// did not find it in the bucket
p = table[index];
table[index] = new elt;
table[index]->data = d;
table[index]->key = k;
table[index]->next = p;
}
}
// HashTableOne find function:
int HashTableOne::find(int k) {
int index = hash(k);
elt * p = table[index];
while(p != NULL) {
if(p->key == k){ // found one
return p;
}
p = p->next;
}// end while
// did not find it
return -1;
}
// HashTable3 constructor:
HashTable3::HashTable3(int n1, int n2) {
typedef HashTableOne * HashTableOne_p; // a pointer to HashTableOne class
table= new HashTableOne_p[n1];
for (int i= 0; i < n1; i++){
table[i]= new HashTableOne(n2);
}
}
// HashTable3 add function:
void HashTable3::add(int k, int d) {
int index = hash(k);
if(table[index] == NULL){
table[index] = new elt;
table[index]->data = d;
table[index]->key = k;
table[index]->next = NULL;
} else{
// search for the key, if found update the data
elt * p = table[index];
while(p != NULL) {
if(p->key == k){ // found one
p->data = d;
return;
}
p = p->next;
}// end while
// did not find it in the bucket
p = table[index];
table[index] = new elt;
table[index]->data = d;
table[index]->key = k;
table[index]->next = p;
}
}
// HashTable3 find function:
int HashTable3::find(int k) {
int index = hash(k);
elt * p = table[index];
while(p != NULL) {
if(p->key == k){ // found one
return p;
}
p = p->next;
}// end while
// did not find it
return -1;
}
int main() {
// test cases go here
HashTable3 H1(3, 2); // New hash table with 3 elements in main hash table and 2 bucket hash tables, populate with add() method randomly
// Print the contents of the table after each operation using print()
H1.find("key"); // finds an element with "key" value and returns data value (or -1 if key does not exist)
return 0;
}