Hash Table implementation

This is a discussion on Hash Table implementation within the C++ Programming forums, part of the General Programming Boards category; Hello there all, I wanted to have a question answered. I need to know how we would be able to ...

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    92

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

  2. #2
    Registered User
    Join Date
    May 2003
    Posts
    161
    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.

  3. #3
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    One question

    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.

  4. #4
    Registered User
    Join Date
    May 2003
    Posts
    161
    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.

  5. #5
    Registered User
    Join Date
    Sep 2002
    Posts
    92

    Shrinking a HashTable

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

  6. #6
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    > // Determine a new size and allocate a new array
    > tableSize = currentSize/2;

    I think this should be:
    tableSize = tableSize/2;

  7. #7
    Registered User
    Join Date
    May 2003
    Posts
    161
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Writing array, to file
    By zootreeves in forum C Programming
    Replies: 9
    Last Post: 09-08-2007, 06:06 PM
  2. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-25-2007, 12:36 AM
  3. Hash table creation and insertion
    By tgshah in forum C Programming
    Replies: 1
    Last Post: 01-23-2006, 07:54 PM
  4. Not sure on hash table memory allocations
    By Thumper333 in forum C Programming
    Replies: 3
    Last Post: 09-27-2004, 10:00 PM
  5. hash table data structure implementation
    By sanju in forum C Programming
    Replies: 1
    Last Post: 09-27-2002, 06:06 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21