write functions to do the following. Find the size of the hash table write a pri
ID: 3915178 • Letter: W
Question
write functions to do the following.
Find the size of the hash table
write a print function that will print all of the elements and their locations in the table
Remove the second element from the table and print it. The table is otherwise left unchanged
write a subprogram that will find the true load factor
write a function that will insert a new value into a hash table
write a function that will print the empty locations in the table
write a function that will create a new hash table by entering the data in reverse order
write a function to retrieve a value from a hash table
write a function to determine whether the two tables are equal
write a function that determines whether a sport is empty or full
write a function to implement random probing
Explanation / Answer
#include<bits/stdc++.h>
using namespace std;
//template for generic type
template<typename K, typename V>
//Hashnode class
class HashNode
{
public:
V value;
K key;
//Constructor of hashnode
HashNode(K key, V value)
{
this->value = value;
this->key = key;
}
};
//template for generic type
template<typename K, typename V>
//Our own Hashmap class
class HashMap
{
//hash element array
HashNode<K,V> **arr;
int capacity;
//current size
int size;
//dummy node
HashNode<K,V> *dummy;
public:
HashMap()
{
//Initial capacity of hash array
capacity = 20;
size=0;
arr = new HashNode<K,V>*[capacity];
//Initialise all elements of array as NULL
for(int i=0 ; i < capacity ; i++)
arr[i] = NULL;
//dummy node with value and key -1
dummy = new HashNode<K,V>(-1, -1);
}
// This implements hash function to find index
// for a key
int hashCode(K key)
{
return key % capacity;
}
//Function to add key value pair
void insertNode(K key, V value)
{
HashNode<K,V> *temp = new HashNode<K,V>(key, value);
// Apply hash function to find index for given key
int hashIndex = hashCode(key);
//find next free space
while(arr[hashIndex] != NULL && arr[hashIndex]->key != key
&& arr[hashIndex]->key != -1)
{
hashIndex++;
hashIndex %= capacity;
}
//if new node to be inserted increase the current size
if(arr[hashIndex] == NULL || arr[hashIndex]->key == -1)
size++;
arr[hashIndex] = temp;
}
//Function to delete a key value pair
V deleteNode(int key)
{
// Apply hash function to find index for given key
int hashIndex = hashCode(key);
//finding the node with given key
while(arr[hashIndex] != NULL)
{
//if node found
if(arr[hashIndex]->key == key)
{
HashNode<K,V> *temp = arr[hashIndex];
//Insert dummy node here for further use
arr[hashIndex] = dummy;
// Reduce size
size--;
return temp->value;
}
hashIndex++;
hashIndex %= capacity;
}
//If not found return null
return NULL;
}
//Function to search the value for a given key
V get(int key)
{
// Apply hash function to find index for given key
int hashIndex = hashCode(key);
//finding the node with given key
while(arr[hashIndex] != NULL)
{
//if node found return its value
if(arr[hashIndex]->key == key)
return arr[hashIndex]->value;
hashIndex++;
hashIndex %= capacity;
}
//If not found return null
return NULL;
}
//Return current size
int sizeofMap()
{
return size;
}
//Return true if size is 0
bool isEmpty()
{
return size == 0;
}
//Function to display the stored key value pairs
void display()
{
for(int i=0 ; i<capacity ; i++)
{
if(arr[i] != NULL && arr[i]->key != -1)
cout << "key = " << arr[i]->key
<<" value = "<< arr[i]->value << endl;
}
}
//Function to display the stored key value pairs in reverse order
void displayInReverse()
{
for(int i=capacity ; i>0 ; i--)
{
if(arr[i] != NULL && arr[i]->key != -1)
cout << "key = " << arr[i]->key
<<" value = "<< arr[i]->value << endl;
}
}
//Function to determine whether the two tables are equal
void checkTableEquality(HashMap<int, int> x)
{
for(int i=capacity ; i>0 ; i--)
{
if(x->arr[i] != NULL && x->arr[i]->key != -1)
cout << "key = " << arr[i]->key
<<" value = "<< arr[i]->value << endl;
}
}
//Function to get load factor of hastable
void findLoadFactor()
{
int load_factor = capacity / sizeofMap();
cout << "load factor is : " <<load_factor << endl;
}
};
//Driver method to test map class
int main()
{
HashMap<int, int> *h = new HashMap<int, int>;
h->insertNode(1,1);
h->insertNode(2,2);
h->insertNode(2,3);
h->display();
h->displayInReverse();
h->findLoadFactor();
h->checkTableEquality(h);
cout << h->sizeofMap() <<endl;
cout << h->deleteNode(2) << endl;
cout << h->sizeofMap() <<endl;
cout << h->isEmpty() << endl;
cout << h->get(2);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.