A hash table is a collection of buckets . Each bucket is a collection of binding

Question

A hash table is a collection of buckets. Each bucket is a collection of bindings. Each binding consists of a key and a value. A key uniquely identifies its binding; a value is data that is somehow pertinent to its key. The mapping of bindings to buckets is determined by the hash table's hash function. A hash function accepts a binding's key and bucket count, and returns the number of the bucket in which that binding should reside.

A collision occurs when more than one binding is mapped to the same bucket. A good hash function distributes bindings fairly uniformly across the hash table's buckets, and thus minimizes collisions. A bad hash function is one that generates many collisions. With a good hash function, the retrieve/insert/delete performance of a hash table is very fast.

Implement a 100-bucket Hash Table ADT which can hold a set of integers. In the case of collision, the chaining resolution method will be used.

Output the content of each bucket.

Should be coded in C++.

Explanation / Answer

#include<bits/stdc++.h>
using namespace std;
const int TABLE_SIZE = 100;

/*
* Node Class Declaration
*/
class Node
{
public:
int key;
int data;
Node* next;
Node(int key, int data)
{
this->key = key;
this->data = data;
this->next = NULL;
}
};

/*
* HashTable Class Declaration
*/
class HashTable
{
private:
Node** htable;
public:
HashTable()
{
htable = new Node*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
htable[i] = NULL;
}
~HashTable()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
Node* insdata = htable[i];
while (insdata != NULL)
{
Node* prev = insdata;
insdata = insdata->next;
delete prev;
}
}
delete[] htable;
}
/*
* Hash Function
*/

void Retrive()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
Node* insdata = htable[i];
while (insdata != NULL)
{
cout<<"Key "<<insdata->key<<" data "<<insdata->data<<endl;
insdata = insdata->next;
//delete prev;
}
}
}
int HashFunction(int key,int s)
{
return key % s;
}

/*
* Insert Element at a key
*/
void Insert(int key, int data)
{
int hash_val = HashFunction(key,TABLE_SIZE);
Node* prev = NULL;
Node* insdata = htable[hash_val];
while (insdata != NULL)
{
prev = insdata;
insdata = insdata->next;
}
if (insdata == NULL)
{
insdata = new Node(key, data);
if (prev == NULL)
{
htable[hash_val] = insdata;
}
else
{
prev->next = insdata;
}
}
else
{
insdata->data = data;
}
}
/*
* Delete Element at a key
*/
void Delete(int key)
{
int hash_val = HashFunction(key,TABLE_SIZE);
Node* insdata = htable[hash_val];
Node* prev = NULL;
if (insdata == NULL || insdata->key != key)
{
cout<<"No Element found at key "<<key<<endl;
return;
}
while (insdata->next != NULL)
{
prev = insdata;
insdata = insdata->next;
}
if (prev != NULL)
{
prev->next = insdata->next;
}
delete insdata;
cout<<"Element Deleted"<<endl;
}
/*
* Search Element at a key
*/
  
};

int main()
{
HashTable hash;
int key, data;
int choice;
while (1)
{

cout<<"1.Insert element into the table"<<endl;

cout<<"2.Delete element at a key"<<endl;
cout<<"3.Retrive"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter element to be inserted: ";
cin>>data;
cout<<"Enter key at which element to be inserted: ";
cin>>key;
hash.Insert(key, data);
break;

case 2:
cout<<"Enter key of the element to be deleted: ";
cin>>key;
hash.Delete(key);
break;
case 3:
hash.Retrive();break;
case 4:
return 0;
default:
cout<<" Enter correct option ";
}
}
return 0;
}

=====================================================================

Output:

akshay@akshay-Inspiron-3537:~/Chegg$ g++ hash.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
1.Insert element into the table
2.Delete element at a key
3.Retrive
4.Exit
Enter your choice: 1
Enter element to be inserted: 10
Enter key at which element to be inserted: 0
1.Insert element into the table
2.Delete element at a key
3.Retrive
4.Exit
Enter your choice: 1
Enter element to be inserted: 100
Enter key at which element to be inserted: 0
1.Insert element into the table
2.Delete element at a key
3.Retrive
4.Exit
Enter your choice: 1
Enter element to be inserted: 2
Enter key at which element to be inserted: 2
1.Insert element into the table
2.Delete element at a key
3.Retrive
4.Exit
Enter your choice: 3
Key 0 data 10
Key 0 data 100
Key 2 data 2
1.Insert element into the table
2.Delete element at a key
3.Retrive
4.Exit
Enter your choice: 2
Enter key of the element to be deleted: 0
Element Deleted
1.Insert element into the table
2.Delete element at a key
3.Retrive
4.Exit
Enter your choice: 3
Key 0 data 10
Key 2 data 2
1.Insert element into the table
2.Delete element at a key
3.Retrive
4.Exit
Enter your choice: 4

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.