Member Avatar for blazted

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

// 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
  • 114 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by blazted
Member Avatar for Narue

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.

Member Avatar for blazted

Ahh thank you. I did that and it worked perfectly.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.