0

I wrote a hash table that takes a char as a key and for a test I am using a string for my value. It uses a linked list. But I am having a problem displaying the value. I have a function that displays the key correctly but the value is displayed as garbage. I am prety sure it is this one method that is causing it to display incorrectly but it complies and runs fine, i am just not sure why this does not work. Here is the method I think is not working and I am attaching the entire sample program as a txt file if someonecan take a look. I a little stuck on this.

bool Hashtable::get(char *key, string value)
{
    METADATA* temp = find(key);
    if(temp == NULL)
    {
        value = "";
        return false;
    }
    else
    {
        value = temp->value;
        return true;
    }
}

Here is my Display Function and it calls this function so I am assuming that for some reason the data is not bein copied correctly.

void displayAll(Hashtable *hashtable)
{
    char key[SIZE_KEY];
    char value[SIZE_VALUE];
    cout<< "\nCurrent nodes in hashtable: " << endl;
    hashtable->initIterator();
    while(hashtable->hasNext())
    {
        hashtable->getNextKey(key);
        hashtable->get(key, value);
        cout << "key: " << key << "\tvalue : " << value << endl;

    }
}

Thanks

Attachments
// HashTable_Test2.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <string>
#include <sstream>
#include <cctype>
#define SIZE_KEY 32
#define SIZE_VALUE 256
#define DEFAULT_TABLESIZE 101
using namespace std;

typedef struct METADATA
{
	struct METADATA(char *key, string value)
	{
		strcpy(this->key, key);
		this->value = value;
		next = NULL;
	}
	char key[SIZE_KEY];
	string value;
	struct METADATA *next;
}METADATA;

class Hashtable
{
private:
	int tablesize;
	METADATA** table;
	int size;
	long hashstring(char* key);
	METADATA* current_entry;
	METADATA* find(char* key);
	int current_index;
	
public:
	
	Hashtable(int tablesize = DEFAULT_TABLESIZE);
	virtual ~Hashtable();
	bool put(char* key, string value);
	bool get(char* key, string value);
	bool contains(char* key);
	bool remove(char* key);
	void removeAll();
	int getSize();
	void initIterator();
	bool hasNext();
	void getNextKey(char* key);
};

void displayAll(Hashtable *hashtable);

int main()
{
	Hashtable * hashtable = new Hashtable();
	char key[SIZE_KEY];
	string value;
	strcpy(key, "389");
	value = "Bob";
	if(!hashtable->contains(key))
	{
		cout << "Adding node - key: " << key << " value "
			<< value << endl;
		hashtable->put(key, value);
	}
	strcpy(key, "415");
	value = "Henry";
	if(!hashtable->contains(key))
	{
		cout << "Adding node - key: " << key << " value "
			<< value << endl;
		hashtable->put(key, value);
	}
	strcpy(key, "999");
	value = "Joe";
	if(!hashtable->contains(key))
	{
		cout << "Adding node - key: " << key << " value "
			<< value << endl;
		hashtable->put(key, value);
	}

	displayAll(hashtable);
	return 0;
}

Hashtable::Hashtable(int tablesize)
{
	size = 0;
	this->tablesize = tablesize;
	table = new METADATA*[tablesize];
	for(int i = 0; i<tablesize;i++)
	{
		table[i] = NULL;
	}
}

Hashtable::~Hashtable()
{
	removeAll();
	delete[] table;
}

bool Hashtable::put(char *key, string value)
{
	if(find(key) != NULL)
	{
		return false;
	}
	METADATA* entry = new METADATA(key, value);
	int bucket = hashstring(key);
	entry->next = table[bucket];
	table[bucket] = entry;
	size++;
	return true;
}

bool Hashtable::get(char *key, string value)
{
	METADATA* temp = find(key);
	if(temp == NULL)
	{
		value = "";
		return false;
	}
	else
	{
		value = temp->value;
		return true;
	}
}


bool Hashtable::contains(char* key)
{
	if(find(key) == NULL)
	{
		return false;
	}
	else
	{
		return true;
	}
}


bool Hashtable::remove(char *key)
{
	int bucket = hashstring(key);
	METADATA* temp = table[bucket];

	if(temp == NULL)
	{
		return false;
	}
	else if(strcmp(key, temp->key) == 0)
	{
		table[bucket] = temp->next;
		delete temp;
		size--;
		return true;
	}
	else
	{
		METADATA* temp_next = temp->next;
		while(temp_next != NULL)
		{
			if(strcmp(key, temp_next->key) == 0)
			{
				temp->next = temp_next->next;
				delete temp_next;
				size--;
				return true;
			}
			temp= temp->next;
			temp_next = temp_next->next;
		}
	}
	return false;
}
void Hashtable::removeAll()
{
	for(int i=0; i<tablesize; i++)
	{
		METADATA* temp = table[i];
		while(temp != NULL)
		{
			METADATA* next = temp->next;
			cout << "Removing node - key: " << temp->key << endl;
			delete temp;
			temp = next;
		}
	}
}

void Hashtable::getNextKey(char *key)
{
	if(current_entry == NULL)
	{
		key[0] = '\0';
		return;
	}
	strcpy(key, current_entry->key);
	if(current_entry->next != NULL)
	{
		current_entry = current_entry->next;
	}
	else
	{
		for(int i=current_index+1; i<tablesize; i++)
		{
			if(table[i] == NULL)
			{
				continue;
			}
			current_entry = table[i];
			current_index = i;
			return;
		}
		current_entry = NULL;
		current_index = tablesize;
	}
}

int Hashtable::getSize()
{
	return size;
}

void Hashtable::initIterator()
{
	current_entry = NULL;
	current_index = tablesize;
	for(int i=0;i<tablesize;i++)
	{
		if(table[i] == NULL)
		{
			continue;
		}
		else
		{
			current_entry = table[i];
			current_index = i;
			break;
		}
	}
}

METADATA* Hashtable::find(char *key)
{
	int bucket = hashstring(key);
	METADATA* temp = table[bucket];
	while(temp != NULL)
	{
		if(strcmp(key, temp->key) == 0)
		{
			return temp;
		}
		temp = temp->next;
	}
	return NULL;
}

long Hashtable::hashstring(char *key)
{
	int n = strlen(key);
	long h = 0;
	for(int i=0; i<n;i++)
	{
		h=(h<<2) + key[i];
	}
	return abs(h % tablesize);
}

bool Hashtable::hasNext()
{
	if(current_entry == NULL)
	{
		return false;
	}
	else
	{
		return true;
	}
}

void displayAll(Hashtable *hashtable)
{
	char key[SIZE_KEY];
	char value[SIZE_VALUE];
	cout<< "\nCurrent nodes in hashtable: " << endl;
	hashtable->initIterator();
	while(hashtable->hasNext())
	{
		hashtable->getNextKey(key);
		hashtable->get(key, value);
		cout << "key: " << key << "\tvalue : " << value << endl;

	}
}
2
Contributors
2
Replies
3
Views
10 Years
Discussion Span
Last Post by blazted
0

value is an array. When you pass it as the second argument to get, it acts as the initializer for the std::string parameter. You've lost your reference, and any changes to the parameter will not be reflected back in displayAll. Change value to a string and pass it by reference to get.

This question has already been answered. 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.