PROWAREtech

C++: Hashtable Example for Integer Keys

This first example is primarily in C but there is a little C++ sprinkled in here and there to make the code more readable. The second example is pure C++.

For a more complete example, see the C++ template class example.

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

#define TABLE_SIZE 1000003 // use a large prime number

#define HASH(key, table_size) (key % table_size)

class HashtableItem
{
private:
	HashtableItem *pnext; // for a linked list
	unsigned int key;
	string value;

public:
	HashtableItem(const unsigned int key, const string &value) : pnext(nullptr)
	{
		this->key = key;
		this->value = value;
	}
	~HashtableItem()
	{
		if(this->pnext)
			delete this->pnext;
	}
	unsigned int Key() const
	{
		return this->key;
	}
	string Value() const
	{
		return this->value;
	}
	void SetNext(HashtableItem *item)
	{
		if(this->pnext)
			this->pnext->SetNext(item);
		else
			this->pnext = item;
	}
	HashtableItem *GetNext() const
	{
		return this->pnext;
	}
};

int main (int argc, char *argv[])
{
	unsigned int i, key;
	string value;
	HashtableItem **table = (HashtableItem **)new void*[TABLE_SIZE];

	for(i = 0; i < TABLE_SIZE; table[i++] = 0);

	while(true)
	{
		cout << "enter a key (integer) for the hash (0 to quit): ";
		cin >> key;
		if(0 == key)
			break;
		i = HASH(key, TABLE_SIZE);
		if(table[i])
		{
			if(table[i]->Key() == key) // then we found the item
				cout << "the value at " << table[i]->Key() << " is \"" << table[i]->Value() << "\"\r\n";
			else
			{
				HashtableItem *item;
				for(item = table[i]; item->GetNext() && (item->GetNext()->Key() != key); item = item->GetNext());
				if(item->GetNext()) // then we found the item in the linked list
					cout << "the value at " << item->GetNext()->Key() << " is \"" << item->GetNext()->Value() << "\"\r\n";
				else // then the key was not found in the linked list
				{
					cout << "enter a value (string) for the key " << key << " (q to quit): ";
					cin >> value;
					if(value == "q")
						break;
					item->SetNext(new HashtableItem(key, value));
				}
			}
		}
		else // then the hashtable is functioning as it should WITHOUT the linked list
		{
			cout << "enter a value (string) for the key " << key << " (q to quit): ";
			cin >> value;
			if(value == "q")
				break;
			table[i] = new HashtableItem(key, value);
		}
	}
	// now print the entire table while deleting it
	for(i = 0; i < TABLE_SIZE; i++)
	{
		if(table[i])
		{
			HashtableItem *item;
			for(item = table[i]; item; item = item->GetNext())
				cout << item->Key() << " = " << item->Value() << "\r\n";
			delete table[i];
		}
	}
	delete []table;
	return 0;
}

And now an example in C++:

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

#define TABLE_SIZE 1000004 // use a large number multiple of two

#define HASH_MACRO(key, table_size) (key & (table_size - 1))

class HashtableItem;

class Hashtable
{
private:
	HashtableItem **table;
	HashtableItem *cur_table_item;
	int cur_index;

public:
	Hashtable();
	~Hashtable();

	// Add a new entry, returns false when the key already exists
	bool Add(const unsigned int key, const string &value);

	HashtableItem *operator[](const unsigned int key) const;

	// removes one item
	void Remove(const unsigned int key);

	// removes all items
	void Clear();

	// for looping through the keys
	HashtableItem *GetFirst();
	HashtableItem *GetNext();
};

class HashtableItem
{
private:
	HashtableItem *pnext;
	unsigned int key;
	string value;

	// keep these private because it prevents the client from creating them directly
	HashtableItem() {}
	HashtableItem(const unsigned int key, const string &value);
	~HashtableItem();

public:
	const unsigned int Key() const;
	const string &Value() const;
	const string &operator=(const string &value);
	const char *operator=(const char *value);

	// some friend functions that can access the private data
	friend bool Hashtable::Add(const unsigned int key, const string &value);
	friend Hashtable::~Hashtable();
	friend void Hashtable::Remove(const unsigned int key);
	friend void Hashtable::Clear();
	friend HashtableItem *Hashtable::operator[](const unsigned int key) const;
	friend HashtableItem *Hashtable::GetNext();
};

// ##################### Hashtable ###########################
Hashtable::Hashtable() : cur_table_item(nullptr), cur_index(0)
{
	table = new HashtableItem*[TABLE_SIZE];
	for (int i = 0; i < TABLE_SIZE; table[i++] = nullptr);
}
Hashtable::~Hashtable()
{
	for (int i = 0; i < TABLE_SIZE; i++)
	{
		if (table[i])
			delete table[i];
	}
	delete[]table;
}
bool Hashtable::Add(const unsigned int key, const string &value)
{
	unsigned int i = HASH_MACRO(key, TABLE_SIZE);
	if (table[i])
	{
		HashtableItem *node;
		for (node = table[i]; node->pnext && (node->pnext->Key() != key); node = node->pnext);
		if (node->pnext)
			return false;
		node->pnext = new HashtableItem(key, value);
		return true;
	}
	table[i] = new HashtableItem(key, value);
	return true;
}
HashtableItem *Hashtable::operator[](const unsigned int key) const
{
	unsigned int i = HASH_MACRO(key, TABLE_SIZE);
	if (table[i])
	{
		if (table[i]->Key() == key)
			return table[i];
		HashtableItem *node;
		for (node = table[i]; node->pnext && (node->pnext->Key() != key); node = node->pnext);
		if (node->pnext)
			return node->pnext;
	}
	return nullptr;
}
void Hashtable::Remove(const unsigned int key)
{
	unsigned int i = HASH_MACRO(key, TABLE_SIZE);
	if (table[i])
	{
		HashtableItem *node, *tmp;
		if (table[i]->Key() == key)
		{
			tmp = table[i]->pnext;
			table[i]->pnext = nullptr;
			delete table[i];
			table[i] = tmp;
		}
		else
		{
			for (node = table[i]; node->pnext && (node->pnext->Key() != key); node = node->pnext);
			if (node->pnext) // then key found in linked list
			{
				tmp = node->pnext->pnext;
				node->pnext = nullptr;
				delete node->pnext;
				node->pnext = tmp;
			}
		}
	}
}
void Hashtable::Clear()
{
	for (int i = 0; i < TABLE_SIZE; i++)
	{
		delete table[i];
		table[i] = nullptr;
	}
}
HashtableItem *Hashtable::GetFirst()
{
	int i;
	this->cur_table_item = nullptr;
	this->cur_index = 0;

	for (i = this->cur_index; i < TABLE_SIZE && table[i] == nullptr; i++);
	if (i < TABLE_SIZE)
	{
		this->cur_table_item = table[i];
		this->cur_index = i;
	}
	return this->cur_table_item;
}
HashtableItem *Hashtable::GetNext()
{
	if (this->cur_table_item && this->cur_table_item->pnext)
	{
		this->cur_table_item = this->cur_table_item->pnext;
	}
	else
	{
		int i;
		for (i = this->cur_index + 1; i < TABLE_SIZE && table[i] == nullptr; i++);
		if (i < TABLE_SIZE)
		{
			this->cur_table_item = table[i];
			this->cur_index = i;
		}
		else
		{
			this->cur_table_item = nullptr;
			this->cur_index = 0;
		}
	}
	return this->cur_table_item;
}

// ##################### HashtableItem ###########################
HashtableItem::HashtableItem(const unsigned int xKey, const string &xValue) : key(xKey), value(xValue), pnext(nullptr) {}
HashtableItem::~HashtableItem()
{
	if (this->pnext)
		delete this->pnext;
}
const unsigned int HashtableItem::Key() const
{
	return this->key;
}
const string &HashtableItem::Value() const
{
	return this->value;
}
const string &HashtableItem::operator=(const string &value)
{
	this->value = value;
	return value;
}
const char *HashtableItem::operator=(const char *value)
{
	this->value = value;
	return value;
}

// #################### entry point ####################
// notice how much cleaner the code is here than when compared to the C example
int main(int argc, char *argv[])
{
	unsigned int key;
	string value;
	Hashtable ht;
	HashtableItem *item;

	while (true)
	{
		cout << "enter a key (whole number) for the hash (-1 to quit): ";
		cin >> key;
		if ((int)key == -1)
			break;
		item = ht[key];
		if (item == nullptr)
		{
			cout << "enter a value for the key " << key << " (q to quit): ";
			cin >> value;
			if (value == "q")
				break;
			ht.Add(key, value);
		}
		else
		{
			cout << "the value at " << item->Key() << " is \"" << item->Value() << "\"\r\nenter a new value: ";
			cin >> value;
			(*item) = value;
		}
	}
	while (true)
	{
		item = ht.GetFirst();
		while (item)
		{
			cout << "the value at " << item->Key() << " is \"" << item->Value() << "\"\r\n";
			item = ht.GetNext();
		}
		cout << "enter the key (whole number) to delete (-1 to quit): ";
		cin >> key;
		if ((int)key == -1)
			break;
		ht.Remove(key);
	}
	return 0;
}

To convert this class to use C++ templates click here. To see the string implementation of this class click here.

---