Thread: Hash Table implementation

Hello there all,
I wanted to have a question answered. I need to know how we would be able to Insert into a hash table with linear probing. I have half of the code done(where Insert does not require collisions.)
The second half I cannot get the algorithm for. Please look through this. A rough pseudocode will do. Thank you in advance.

Code:

bool HashTable::Insert(const string &name, const string &address)
  // insert an address with associated name
{

  // unsigned int key = Mask(Hash(name));

  unsigned int key = 0;
  // if the element given by the hash function is empty
  // then set the name and address to this element.
  if (ptr[key].GetName()=="nil"){
    ptr[key].SetName(name);
    ptr[key].SetAddress(address);

    return true;
  }

  // else, increment the array element one and try to insert there
  else {

  }
}

I typically implement my hash tables as an array of linked lists.

Code:

struct HashtableNode 
{
  string key;
  string value;
  HashtableNode* next;
};

const int HashtableSize = 31;

class Hashtable
{
  HashtableNode* table[HashtableSize];

  Hashtable()
  {
    for(int i=0; i<HashtableSize; i++)
      table[i] = NULL;
  }

  // very awful hash function
  int 
  hash(const string& key)
  {
    return key.size() % HashtableSize;
  }

  void
  insert(const string& name, const string& address)
  {
    HashtableNode* newNode;

    int h = hash(name);

    if(table[h])
    {
      HashtableNode* node = table[h];
      
      // walk the list to see if the key already exists
      while(node)
      {
        // if it does, set the value and return
        if(node->key == name)
        {
           node->value = address;
           return;
        }

        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;
  }

}

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.

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:

Code:

  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)
      {
        ptr[key].SetName(name);
        ptr[key].SetAddress(address);
        return true;
      }

      key++;
    }

    return false; // ran out of room    
  }

Hope that helps.

I asked my professor about other methods of doing it and he will go over the linked list method in two weeks since that seems to be one of the most efficient ways of handling hash tables. Right now, we are simply experimenting with introductory methods.
If you could please explain to me the following line of your code with(the linear probing solution):

Code:

if (ptr[key].GetName()=="nil" || ptr[key].GetName() == name)
...
}

Now, it seems to me that this if statement will allow insertion of our name-address pair if the value in the current array element is nil OR name. How will this work? Since this statement will insert the name-address pair regardless.... it just does not make any sense to me. If you would please clarify this I would be much obliged. And you probably understood this but nil is this programmers' method of telling the ptr that the current array element is empty.

If you could please explain to me the following line of your code with(the linear probing solution):

That code will insert at the current point if it is empty OR if the key matches. One property of a hashtable is that a key should not appear more than once. This check says that if there is already a node with that key, just use that slot.

It's probably easier to think about in a code situation.

Code:

Hashtable ht;
ht.insert("Joe", "54 West St.");
ht.insert("Peter", "3221 First Ave.");
ht.insert("Bob", "78 Broadway");

Now, say you wanted to change Joe's address.

Code:

ht.insert("Joe", "211 W 58 St.");

Without the condition I supplied above, insert() would simply add a second entry for Joe. Additionally, if you're searching the table in a linear fashion, then trying to grab the data for Joe would pull up the first, incorrect entry.

I hope that clarifies it a bit.

Thank you thefroggy for all your help with the Insert() function, I modified it a little bit so it can traverse through the whole table instead of starting at the hashed value. I have a new question though.
I would like to dynamically shrink my hashtable but there is a new problem that I am faced with. If I want to shrink the hashtable, I need to make sure that all of my elements are being copied into the new hashtable. So, I simply have my code traverse through all of my hashtable and search if each of my array elements are empty or not. If they are not empty then I insert that element from the old array to the new one..... well, easier said than done. This is what I have so far but for some reason it gives me a segmentation fault. Please tell me what is going wrong. Thank you.

Code:

void HashTable::Shrink()
  // shrink the table size whenever the table is fewer
  // than half the total table entries
{
  int old_size = tableSize;

  // Determine a new size and allocate a new array
  tableSize = currentSize/2;
  HashBucket* newhashptr = new HashBucket[tableSize];

  // Search for AND copy all the contents from the old array to the new array
  int j = 0;
  for (int i = 0; i < old_size; i++){
    // if hashtable value is not a null value
    if (ptr[i].GetName() != "nil"){
      // then place that value into the new array
      newhashptr[j] = ptr[i];
      j++;
    }
  }

  delete[] ptr; // Remove the old array
  ptr = newhashptr; // Point old name to new array

  cout << "\n**Resizing hashtable to size" << tableSize << "\n\n";

}

In this loop:

Code:

  int j = 0;
  for (int i = 0; i < old_size; i++){
    // if hashtable value is not a null value
    if (ptr[i].GetName() != "nil"){
      // then place that value into the new array
      newhashptr[j] = ptr[i];
      j++;
    }
  }

You never check to make sure that you have enough room for all the entries. What if your old table has 100 buckets and 75 of them are filled? You'll cut the table size to 50, then try to copy 75 items into 50 slots.

Your best option may be to keep track of how many slots are filled. Then, when you want to shrink it, you can set the new table size to that number. Note that if you do this, you won't be able to add anything else to the table.