Complete the pseudo code for the following hash table operations: 1. Insert 2. R
ID: 3595743 • Letter: C
Question
Complete the pseudo code for the following hash table operations:
1. Insert
2. Remove
Assume Hashtable is a simple array of size 8, with indices 0..7. Numeric keys are mapped by a Hashfunction that gives the mod(8,n) value for any key “n” yielding the Hashtable index for that key (0..7). A Hashtable entry is null unless a key exists with that index as its hashed index; if so, the Hashtable entry points to the first node of a linked list of keys with that hash index. The last node on this linked list has a null reference for the next referenced node. Assume the occurrence of a linked list node is represented by the object “Node” and its “Data” and “NextRef” attributes.
Explanation / Answer
Answer for given hash table implemetation for Insert and remove with table size is .
I added additional initailzation functions.
Answer for Hash function implementation for Insert and Remove functions:
const int TABLE_SIZE = 8;
// HashNode structure Declaration
struct HashNode
{
public:
. int key;
int value;
HashNode* next;
HashNode(int key, int value)
{
this->key = key;
this->value = value;
this->next = NULL;
}
};
// HashMap structure Declaration
struct HashMap
{
private:
HashNode** htable;
public:
HashMap()
{
htable = new HashNode*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
htable[i] = NULL;
}
~HashMap()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
HashNode* entry = htable[i];
while (entry != NULL)
{
HashNode* prev = entry;
entry = entry->next;
delete prev;
}
}
delete[] htable;
}
/*
* Hash Function
*/
int HashFunc(int key)
{
return key % TABLE_SIZE;
}
/*
* Insert Element at a key
*/
function Insert(arg key, value)
then
Integer hash_val = HashFunc(key);
HashNode* prev = NULL;
HashNode* entry = htable[hash_val];
while (entry != NULL)
then
prev = entry;
entry = entry->next;
end while
if (entry == NULL)
then
entry = new HashNode(key, value);
if (prev == NULL)
then
htable[hash_val] = entry;
end if
else
then
prev->next = entry;
end inser else
else
then
entry->value = value;
end outer else
end function
Psedu code for Remove function:
function Remove(arg key)
{
integer hash_val = HashFunc(key);
HashNode* entry = htable[hash_val];
HashNode* prev = NULL;
if (entry == NULL || entry->key != key)
then
print "No Element found at key " key;
return;
end if
while (entry->next != NULL)
then
prev = entry;
entry = entry->next;
end while
if (prev != NULL)
then
prev->next = entry->next;
end if
delete entry;
print "Element Deleted";
end function.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.