1,105,578 Community Members

Hash Table - Insertion

Member Avatar
CodeNinjaMike
Newbie Poster
6 posts since Mar 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Ok, I've been trying to wrap my head around this code for the longest time today, and I've tried to look up multiple web pages on how to solve my issue in a different way, but it's no use. There's something that Im not seeing that separates a regular array, from the way that I have my array or HashTable. The table is set to 128 slots as it's defined to that number. If you need any more information, let me know. My code is as following:

#include <iostream>
#include <iomanip>
using namespace std;

class HashEntry
{
private:
	int key;
	int value;
public:
	HashEntry(int key, int value)
	{
		this->key=key;
		this->value=value;
	}
	

	int getKey()
	{
		return key;
	}
	void setKey(int a_key)
	{
		key=a_key;
	}
	int getValue()
	{
		return value;
	}
	void setValue(int a_value)
	{
		value=a_value;
	}
};
const int TABLE_SIZE =128;

class HashMap
{
private:
	HashEntry**table;
public:
	HashMap()
	{
		table=new HashEntry*[TABLE_SIZE];
		for (int i=0;i<TABLE_SIZE;i++)
			table[i]=NULL;
	}
	int get(int key)
	{
		int hash=(key % TABLE_SIZE);//check to see if the key is less or equal to 128
		//While the spot in table is not null and there is a duplicate of key
		while(table[hash]!=NULL && table[hash]->getKey()!=key)
			//Increment the table spot to insert to
			hash=(hash+1)&TABLE_SIZE;
		//If there is no data
		if(table[hash]==NULL)
			return -1;
		else
			//return the value given there is a valid spot
			return table[hash]->getValue();
	}
	void put(int key, int value) 
	{
		//check to see if the key is within the array
            int hash = (key % TABLE_SIZE);
			//While the table spot isnt null and there is not already a key in place
            while (table[hash] != NULL && table[hash]->getKey() != key)
				//Increment the spot to insert data into on the table
                  hash = (hash + 1) % TABLE_SIZE;
			//If it's null
            if (table[hash] != NULL)
				//delete that spot
                  delete table[hash];
			//Create a new spot
            table[hash] = new HashEntry(key, value);

      }     
      ~HashMap()
	  {
            for (int i = 0; i < TABLE_SIZE; i++)
                  if (table[i] != NULL)
                        delete table[i];
            delete[] table;
      }
	  int getSize()
	  {
		  int count=0;
		  for (int i=0;i<TABLE_SIZE;i++)
		  {
			  if(table[i]!=NULL)
				  count++;
			  else
				  break;
		  }
		  return count;
	  }
	  void insert(int key, int value)
	  {  
		  int count=0;
		  for (int i=0;i<TABLE_SIZE;i++)
		  {
			  if(table[i]!=NULL)
				  //count the entries that have data
				  count++;
			  else
				  //If null, end loop
				  break;
		  }
		  if(key==-1)
			  table[count++]->setValue(value);
		  else
		  {
			//  count++;
			  for (int i=count;i>key;i--)
			  {
				  //Shift the data over
				 table[i]=table[i-1];
			  }
			  //Put the data back in the empty slot.
			  table[key]->setValue(value);
			//put(key,value);
		  }
	  }
};
void main()
{
	HashMap Bob;
	Bob.put(0,0);
	Bob.put(1,10);
	Bob.put(2,20);
	Bob.put(3,40);
	Bob.put(4,100);
	
	for (int i=0;i<Bob.getSize();i++)
	{
		cout << Bob.get(i) << endl;
	}
	Bob.insert(1,30);
	cout << "\nNew Numbers" << endl;
	for (int i=0;i<10;i++)
	{
			cout << Bob.get(i) << endl;
	}

}
Member Avatar
firstPerson
Industrious Poster
4,052 posts since Dec 2008
Reputation Points: 761 [?]
Q&As Helped to Solve: 634 [?]
Skill Endorsements: 24 [?]
 
0
 

whats the problem?

Member Avatar
CodeNinjaMike
Newbie Poster
6 posts since Mar 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Well I dont know if you tried to run it, but for me, when i try to run it, it doesn't execute the second print at the very end. It's like it's telling me that it can't access a spot in the array, therefore something is corrupted.

Member Avatar
firstPerson
Industrious Poster
4,052 posts since Dec 2008
Reputation Points: 761 [?]
Q&As Helped to Solve: 634 [?]
Skill Endorsements: 24 [?]
 
0
 

why do you have both "put" and "insert" function? Most likely, you should only have one function to insert into the hashmap.

Member Avatar
CodeNinjaMike
Newbie Poster
6 posts since Mar 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

why do you have both "put" and "insert" function? Most likely, you should only have one function to insert into the hashmap.

Insert puts data between two entries without erasing anything. Put placed data in the array and doesn't care If data is already there

Member Avatar
firstPerson
Industrious Poster
4,052 posts since Dec 2008
Reputation Points: 761 [?]
Q&As Helped to Solve: 634 [?]
Skill Endorsements: 24 [?]
 
0
 

why do you have that? A key should be unique. In your insert function you are shifting values around. That would cause the get method to fail or act incorrectly because a key that was hashed into a slot is no longer in the same slot.

Member Avatar
CodeNinjaMike
Newbie Poster
6 posts since Mar 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

why do you have that? A key should be unique. In your insert function you are shifting values around. That would cause the get method to fail or act incorrectly because a key that was hashed into a slot is no longer in the same slot.

So there's no reason to have a insert then? I would simply do a "replace" function instead ?

Member Avatar
firstPerson
Industrious Poster
4,052 posts since Dec 2008
Reputation Points: 761 [?]
Q&As Helped to Solve: 634 [?]
Skill Endorsements: 24 [?]
 
0
 

No all you need is a insert function. Usually what happens is that if you try to insert into the map with a key that already exist you return the already existed key/value pair. It is up to the user to decide whether to remove that key or just replace the value associated with that key

Member Avatar
CodeNinjaMike
Newbie Poster
6 posts since Mar 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

No all you need is a insert function. Usually what happens is that if you try to insert into the map with a key that already exist you return the already existed key/value pair. It is up to the user to decide whether to remove that key or just replace the value associated with that key

Ok so what I need to do is take the key and find the value in the array that matches the key and replace it there. But wouldn't I still have to move the data over to the right and insert the new data into the empty spot?

Member Avatar
firstPerson
Industrious Poster
4,052 posts since Dec 2008
Reputation Points: 761 [?]
Q&As Helped to Solve: 634 [?]
Skill Endorsements: 24 [?]
 
0
 

Ok so what I need to do is take the key and find the value in the array that matches the key and replace it there. But wouldn't I still have to move the data over to the right and insert the new data into the empty spot?

Key should be unique to each hashtable. So every key of value 5 for example, should map to the same spot in the array.

Question Answered as of 2 Years Ago by firstPerson
You
This question has already been solved: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: