PROWAREtech
![](/img/wait2.gif)
![](/img/wait2.gif)
![](/img/wait2.gif)
![](/img/wait2.gif)
![](/img/wait2.gif)
![](/img/wait2.gif)
![](/img/wait2.gif)
![](/img/wait2.gif)
C++: Hashtable Example for Integer Keys
Use modulus to find the integer key.
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.
Comment![](/img/comment-white.svg)