Suppose you are implementing a dynamic set of student records as a hash table. E
ID: 3851750 • Letter: S
Question
Suppose you are implementing a dynamic set of student records as a hash table. Each record has an integer key. Key can have values from 0 through 65, 536 and no two records can have the same key values. In addition to the key, each record has following information. Name: GPA: Academic level: Even though the key can take a value between 0 and 65536, this university can have max 10000 students at a given time. Hash Table Implementation Details: Assume that the hash key is k mod m and using chaining in case of a collision. Also, the size (m) of the hash table is 1000. Also, you can assume that keys for student are generated using a random uniform distribution function. Write a C or C++ program that Implements the hash table construction for the above scenario and then implement the following three functions a) 1NSERT (T, x)//insert the student record x to the table b) DELETE (T, x)//delete the student record x from the table c) SEARCH (T, k)//search key k in the hash tableExplanation / Answer
Hi, chaining in hashtables is used to fill data when 2 values map to same key, all such values are inserted in a linked list fashion in the resepctive key node. here is an implementation of the same, added comments too.
#include<iostream>
#include<cstdlib>
#include<string>
#include <bits/stdc++.h>
#include<cstdio>
using namespace std;
class HashNode
{
public:
int key;
float GPA;
string academiclevel;
string name;
HashNode* next;
HashNode(int key, string name,float GPA,string academiclevel)
{
this->key = key;
this->name = name;
this->GPA = GPA;
this->academiclevel = academiclevel;
this->next = NULL;
}
};
class HashMap
{
HashNode** hashtable;
public:
HashMap()
{
hashtable = new HashNode*[1000];
for (int i = 0; i < 1000; i++)
hashtable[i] = NULL;
}
int Hash(int key)
{
return key % 1000;
}
};
void Insert(HashMap hashtable,HashNode* x)
{
int hash_value = Hash(x->key); // calculate hash value of given key
HashNode* prev = NULL;
HashNode* entry = hashtable[hash_value];
while (entry != NULL) // loop till reach end of chain
{
prev = entry;
entry = entry->next;
}
if (entry == NULL)
{
entry = new HashNode(x->key,x->name,x->GPA,x->academiclevel);
if (prev == NULL)
{
hashtable[hash_value] = entry;
}
else
{
prev->next = entry;
}
}else
{
entry->name =x->name ;
entry->GPA=x->GPA;
entry->academiclevel=x->academiclevel;
}
}
void Delete(HashMap hashtable,HashNode* x)
{
int hash_value = Hash(x->key);// // calculate hash value of given key
HashNode* entry = hashtable[hash_value];
HashNode* prev = NULL;
if (entry == NULL || entry->key != x->key) // check if the key is present
{
cout<<"No Element found at key "<<x->key<<endl;
return;
}
while (entry->next != NULL)
{
prev = entry;
entry = entry->next;
}
if (prev != NULL) // if only one value present
{
prev->next = entry->next;
}
delete entry;
cout<<"Element Deleted"<<endl;
}
void Search(HashMap hashtable,int key)// search
{
int hash_value = Hash(key); // calculate hash value of given key
HashNode* entry = hashtable[hash_value]; // pointer to the entry with the obtained hash value
while (entry != NULL)
{
if (entry->key == key) // if key found
{
cout<<entry->name<<" "<<entry->GPA<<" "<<entry->academiclevel;
return;
}
entry = entry->next;
}
cout<<"key not found";
}
Thumbs up if this was helpful, otherwise let me know in comments. Good Day
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.