0

Hi, how can i avoid of key beeing inserted into wrong location.If i do lets say 3 numbers ,5 digits long like 12345,23445,56745 and choose location 45,they will be inserted to location 45,but if try to insert 67452 to the same location it will be inserted,but i need it to be inserted into its own free location like 52,not 45.And is where any way to detect the location automatically,after inserting number?

#include "stdafx.h"

using namespace std;
const int TABLE_SIZE = 128;

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

/*
* HashMap Class Declaration
*/
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)
        {
            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
    */
    void Insert(int key, int value)
    {
        int hash_val = HashFunc(key);
        HashNode* prev = NULL;
        HashNode* entry = htable[hash_val];
        while (entry != NULL)
        {
            prev = entry;
            entry = entry->next;
        }
        if (entry == NULL)
        {
            entry = new HashNode(key, value);
            if (prev == NULL)
            {
                htable[hash_val] = entry;
            }
            else
            {
                prev->next = entry;
            }
        }
        else
        {
            entry->value = value;
        }
    }
    /*
    * Remove Element at a key
    */
    void Remove(int key)
    {
        int hash_val = HashFunc(key);
        HashNode* entry = htable[hash_val];
        HashNode* prev = NULL;
        if (entry == NULL || entry->key != key)
        {
            cout<<"No Element found at key "<<key<<endl;
            return;
        }
        while (entry->next != NULL)
        {
            prev = entry;
            entry = entry->next;
        }
        if (prev != NULL)
        {
            prev->next = entry->next;
        }
        delete entry;
        cout<<"Element Deleted"<<endl;
    }
    /*
    * Search Element at a key
    */
    int Search(int key)
    {
        bool flag = false;
        int hash_val = HashFunc(key);
        HashNode* entry = htable[hash_val];
        while (entry != NULL)
        {
            if (entry->key == key)
            {
                cout<<entry->value<<" ";
                flag = true;
            }
            entry = entry->next;
        }
        if (!flag)
            return -1;
    }
};
/*
* Main Contains Menu
*/
int main()
{
    HashMap hash;
    int key, value;
    int choice;
    while (1)
    {
        cout<<"\n----------------------"<<endl;
        cout<<"Operations on Hash Table"<<endl;
        cout<<"\n----------------------"<<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;
            cout<<"Element at key "<<key<<" : ";
            if (hash.Search(key) == -1)
            {
                cout<<"No element found at key "<<key<<endl;
                continue;
            }
            break;
        case 3:
            cout<<"Enter key of the element to be deleted: ";
            cin>>key;
            hash.Remove(key);
            break;
        case 4:
            exit(1);
        default:
            cout<<"\nEnter correct option\n";
        }
    }
    return 0;
}
2
Contributors
1
Reply
22
Views
2 Years
Discussion Span
Last Post by StuXYZ
0

The principle of this type of hash map is that when two objects have the same key they are stored in the hashmap using a linked list. i.e
if you store say 12345 and 23456 at key number 7, then both will be stored at location 7.

Now if it was put to a different location if then (a) it would not be findable under the initial key (b) what would you do when you have more than 128 (your array limit) ?

The way this was coded effectively is like someone has an old address book with each page has a letter e.g. A , B , C etc. Then as a person is added it gets added directly under the correct letter but in no particular order, e.g. under S it might be Smith, Simon, Steve.
When you are looking for Steve's address, you have to look at all the
S entries until you find him, but don't have to look at A, B ,C etc.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.