I\'m kind of stucking with this question. Please help me, the time is runing out

Question

I'm kind of stucking with this question. Please help me, the time is runing out.

You need to implement the addElement and removeElement functions inside LinearHashTable.This is the code for LinearHashTable and the word " TODO " is the place we need to write the code :

template <typename Key, typename Value>
class LinearHashTable : public HashTableBase<Key, Value>
{
protected:

   //determines whether or not we need to resize
   //to turn off resize, just always return false
   virtual bool needsResize()
   {
       //linear probing seems to get worse after a load factor of about 70%
       if (_number_of_elements > (.7 * _primes[_local_prime_index]))
       {
           return true;
       }
       return false;
   }

   //called to check to see if we need to resize
   virtual void resizeCheck()
   {
       //Right now, resize when load factor > .75; it might be worth it to experiemnt with
       //this value for different kinds of hashtables
       if (needsResize())
       {
           _local_prime_index++;

           HasherBase<Key> *hasher = HasherFactory::copyHasher<Key>(*_hasher);
           LinearHashTable<Key, Value> new_hash{ hasher, _primes[_local_prime_index] };

           for (auto item : _items)
           {
               if (item.isEmpty() == false)
               {
                   //add to new hash table
                   new_hash.addElement(item.getKey(), item.getValue());
               }
           }

           //MOVE IS COOL!
           *this = move(new_hash);
       }
   }

public:

   LinearHashTable(HasherBase<Key> *hasher, int number_of_elements = 11)
       : HashTableBase(hasher, number_of_elements)
   {

   }

   LinearHashTable(LinearHashTable<Key, Value> &other)
       : HashTableBase(other)
   {

   }

   LinearHashTable(LinearHashTable<Key, Value> &&other)
       : HashTableBase(other)
   {

   }

   LinearHashTable & operator=(LinearHashTable<Key, Value> &other)
   {
       HashTableBase::operator=(other);
       return *this;
   }

   LinearHashTable & operator=(LinearHashTable<Key, Value> &&other)
   {
       HashTableBase::operator=(other);
       return *this;
   }

   //concrete implementation for parent's addElement method
   virtual void addElement(const Key &key, const Value &value)
   {
       //check for size restrictions
       resizeCheck();

       //calculate hash based on key
       int hash = HashTableBase::getHash(key);

       //TODO: find empty slot to insert (update hash variable as necessary)

       //remember how many things we're presently storing
       _number_of_elements++;
   }

   //removes supplied key from hash table
   virtual void removeElement(Key key)
   {
       //calculate hash
       int hash = HashTableBase::getHash(key);

       //TODO: find slot to remove. Remember to check for infinite loop!

       //decrement hashtable size
       _number_of_elements--;
   }

   //returns true if the key is contained in the hash table
   virtual bool containsElement(Key key)
   {
       int hash = HashTableBase::getHash(key);
       HashItem<Key, Value> *slot = &_items[hash];
      
       //Turned off, no hints! :)
       throw exception("function not implemented");
   }

   //returns the item pointed to by key
   virtual Value &getElement(string key)
   {
       int hash = HashTableBase::getHash(key);
       HashItem<Key, Value> *slot = &_items[hash];

       //Turned off, no hints! :)
       throw exception("Key not found.");
   }
};

Explanation / Answer

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int TABLE_SIZE = 5;
class HashNode
{
public:
int key;
int value;
HashNode(int key, int value)
{
this->key = key;
this->value = value;
}
};

class DeletedNode:public HashNode
{
private:
static DeletedNode *entry;
DeletedNode():HashNode(-1, -1)
{}
public:
static DeletedNode *getNode()
{
if (entry == NULL)
entry = new DeletedNode();
return entry;
}
};
DeletedNode *DeletedNode::entry = NULL;
class 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++)
{
if (htable[i] != NULL && htable[i] != DeletedNode::getNode())
delete htable[i];
}
delete[] htable;
}
int HashFunc(int key)
{
return key % TABLE_SIZE;
}
void Insert(int key, int value)
{
int hash_val = HashFunc(key);
int init = -1;
int deletedindex = -1;
while (hash_val != init && (htable[hash_val]== DeletedNode::getNode() || htable[hash_val]!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
if (htable[hash_val] == DeletedNode::getNode())
deletedindex = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (htable[hash_val] == NULL || hash_val == init)
{
if(deletedindex != -1)
htable[deletedindex] = new HashNode(key, value);
else
htable[hash_val] = new HashNode(key, value);
}
if(init != hash_val)
{
if (htable[hash_val] != DeletedNode::getNode())
{
if (htable[hash_val] != NULL)
{
if (htable[hash_val]->key == key)
htable[hash_val]->value = value;
}
}
else
htable[hash_val] = new HashNode(key, value);
}
}
int Search(int key)
{
int hash_val = HashFunc(key);
int init = -1;
while (hash_val != init && (htable[hash_val]== DeletedNode::getNode() || htable[hash_val]!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (htable[hash_val] == NULL || hash_val == init)
return -1;
else
return htable[hash_val]->value;
}
void Remove(int key)
int hash_val = HashFunc(key);
int init = -1;
while (hash_val != init && (htable[hash_val== DeletedNode::getNode() || htable[hash_val]!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (hash_val != init && htable[hash_val] != NULL)
{
delete htable[hash_val];
htable[hash_val] = DeletedNode::getNode();
}
}
};
int main()
{
HashMap hash;
int key, value;
int choice;
while(1)
{
cout<<" ----------------------"<<endl;
cout<<"Operations on Hash Table"<<endl;
cout<<" ----------------------"<<endl;
cout<<"1.Insert element into the table"<<endl;
cout<<"2.Search element from the key"<<endl;
cout<<"3.Delete element at a key"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter element to be inserted: ";
cin>>value;
cout<<"Enter key at which element to be inserted: ";
cin>>key;
hash.Insert(key, value);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>key;
if(hash.Search(key) == -1)
{
cout<<"No element found at key "<<key<<endl;
continue;
}
else
{
cout<<"Element at key "<<key<<" : ";
cout<<hash.Search(key)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>key;
hash.Remove(key);
break;
case 4:
exit(1);
default:
cout<<" Enter correct option ";
}
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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