I typically implement my hash tables as an array of linked lists.
I find this method of implementing a hashtable to be cleaner and sometimes more efficient. It keeps all elements within linked lists inside their own hash buckets.
const int HashtableSize = 31;
for(int i=0; i<HashtableSize; i++)
table[i] = NULL;
// very awful hash function
hash(const string& key)
return key.size() % HashtableSize;
insert(const string& name, const string& address)
int h = hash(name);
HashtableNode* node = table[h];
// walk the list to see if the key already exists
// if it does, set the value and return
if(node->key == name)
node->value = address;
node = node->next;
// otherwise, we need a new node
newNode = new HashtableNode;
newNode->key = name;
newNode->value = address;
// add it to the front of the linked list
newNode->next = table[h];
table[h] = newNode;
The array method forces you to move elements into further buckets when you have collisions.
If you still want to implement it that way, you'd basically need a while loop. You start at your hash bucket and if that spot is taken, you move forward 1 spot and try again. Keep doing this until you find an open spot (or you run out of space in the table).
Something like this for your code:
Hope that helps.
bool HashTable::Insert(const string &name, const string &address)
unsigned int key = Mask(Hash(name));
while(key < SIZE) // whatever size your array is
if (ptr[key].GetName()=="nil" || ptr[key].GetName() == name)
return false; // ran out of room