0

So I'm working on a program that works with a hash table. Here's how it goes:

1) Reads in a text file into a vector of "Symbol" objects (contains a name and a number) 2) Hashes the name of the Symbol object. 3) Inserts this object into the hash table.

So far I've been storing the uniquely generated hash keys as an array of integers. I then loop through the array and see if there's duplicates.

If there are, I know there's a collision. This method has proven to be successful however, now I have to write a rehash() function so I can get a new key that won't result in a collision. But I can't figure out how to do this.

I've included my Loop where I check the array of keys and my current hash function as well as my output. Any suggestions on where to go would be really appreciated.

for (int i=0; i < TABLE_SIZE; i++)
        {
              if (i != j)
              {
                if (array[i] == array[j])
                {
                    cout << endl;
                      cout << "Collision occurred at" << array[i] << endl;
                    cout << "Now rehashing..." << endl;
                    // REHASH FUNCTION SHOULD GO HERE --> rec.key = rehash(data);
                    cout << "The new key is: " << rec.key << endl;
                    break;
                }
              }
        }

        dataTable.insert(rec); //inserts the record object into the HashTable.

Existing Hash Function:

int hasher (string data)
  // POST: the index of entry is returned
  {       int sum = 0;
          for (int k = 0; k < data.length(); k++)
              sum = sum + int(data[k]);
          return  sum % TABLE_SIZE;
  }

Output I'm Getting:

count 2 The key for this Symbol object is: 7

  num
  2
  The key for this Symbol object is: 0


  Collision occurred at0
  Now rehashing...
  The new key is: 1
  myFloat
  4
  The key for this Symbol object is: 18

  myDouble
  5
  The key for this Symbol object is: 14

  name
  6
  The key for this Symbol object is: 18


  Collision occurred at18
  Now rehashing...
  The new key is: 1
  address
  6
  The key for this Symbol object is: 7


  Collision occurred at7
  Now rehashing...
  The new key is: 1
  salary
  5
  The key for this Symbol object is: 1

  gpa
  4
  The key for this Symbol object is: 18


  Collision occurred at18
  Now rehashing...
  The new key is: 1
  gdp
  5
  The key for this Symbol object is: 0


  Collision occurred at0
  Now rehashing...
  The new key is: 1
  pi
  5
  The key for this Symbol object is: 7


  Collision occurred at7
  Now rehashing...
  The new key is: 1
  city
  6
  The key for this Symbol object is: 0


  Collision occurred at0
  Now rehashing...
  The new key is: 1
  state
  6
  The key for this Symbol object is: 20

  county
  6
  The key for this Symbol object is: 2

  ch
  0
  The key for this Symbol object is: 14


  Collision occurred at14
  Now rehashing...
  The new key is: 1
  ch2
  0
  The key for this Symbol object is: 1


  Collision occurred at1
  Now rehashing...
  The new key is: 1
  ID
  1
  The key for this Symbol object is: 15

  studentID
  1
  The key for this Symbol object is: 13

  max
  3
  The key for this Symbol object is: 11

  max2
  3
  The key for this Symbol object is: 19

  greeting
  6
  The key for this Symbol object is: 13


  Collision occurred at13
  Now rehashing...
  The new key is: 1
  debt
  5

As you can see, when there is a collision it successfully detects it. Now I just need a way to rehash the key once again so that it doesn't happen in the future... because now the rehash is also a collision.

5
  • 3
    Are you implementing a hash table? Then the typical design is to use one hash function, accept that there will be collisions (note that several hash functions only barely reduce the odds of collisions), and resolve collisions using open addressing or separate chaining. Why do you think you need another hash function?
    – user395760
    Mar 17, 2014 at 21:35
  • 1
    What are you actually trying to accomplish? Is there a reason you're not just using std::hash_map/std::unordered_map?
    – patros
    Mar 17, 2014 at 21:36
  • @delnan yes I'm implanting a hash table and I did so with separate chaining and I've done it successfully. But when there's a collision, I need to rehash the string and insert back into the table. This is my resolve part. Mar 17, 2014 at 22:00
  • 2
    Rehashing still won't guarantee that you won't get another collision. The only way to guarantee that is to know all the keys you might have to hash at compile time, and pick a hash function that maps each one to a distinct hash bucket. For arbitrary strings not known until run-time (or indeed most data where the number of bits that tend to vary is more than the number in your hash function result type) that's just impractical and you must deal with collisions. Mar 17, 2014 at 22:06
  • 1
    @user2704533 If that's your collision resolution strategy, you are not using separate chaining. Actually, it's not even a proper collision resolution strategy, because (as Tony D also explains), it doesn't actually work. You should be using a collision resolution strategy that works, a good start is separate chaining or open addressing. There are some hash tables that use several hash functions, but they it took researchers a long time to get them working well, and if you were building on their work you would know its name (e.g. cuckoo hashing). So don't try that. Start small.
    – user395760
    Mar 17, 2014 at 22:23

5 Answers 5

2

A simple method for resolving hash conflicts is separate chaining. Basically your data structure has a bunch of linked lists, so when there are collisions you just append the result to the other values that collided here. There are other methods that have more efficient insert/lookup time, but they, obviously, require more effort to implement.

1

Say your array is:

#define N ...
struct element table[N];

then you can define two hash functions (independently!), let's say int h(data); int g(data); where 0 <= h < N and 1 <= g < N. Make sure that the value returned by g is relatively prime to N. Then, to insert a new element, you do:

int i = h(data);
if(table[i] is free)
     /* Go ahead! */
else {
     /* Was occupied, try alternatives */
     int j = g(data);
     for(k = i + j; k != i; k = (k + j) % N)
         if(table[k] is free) {
             /* Found a free space, go ahead */
             break;
         }
     if(k == i) {
         /* Table is full */
     }
}

Search is similar.

The easiest way to get the value of g always relatively prime to N is to just take 1. Slightly harder is to ensure that N is prime, and g is always less than N.

Using g == 1 makes data to bunch up, slowing down searches; different values of g avoid this.

1
  • This appears to be functionally equivalent to open addressing. Mar 17, 2014 at 22:52
1

When you look at Implementing a hash function without collisions you are taking about years of research. To put in one word you are trying to implement perfect hashing.

What you have implemented is called Resolving collisions by chaining. The disadvantage of this process is that whenever there is a collision the search take a worst case time of O(n) where n is the number of elements in the sub chain

Choosing a Hash function

The following are approaches in choosing a has function

1) Division method
2) Multiplication method
3) Resolving Collisions by Open Addressing
4) Probing Strategies
5) Universal Hashing. (Where the probability of collisions is infinitely low)
6) Perfect Hashing. (Which is possible only in some cases).

Please go through Lecture 7 and Lecture 8 from
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/
to gain more insight into the above methods and if you are interested in writing you own universal Hashing function I think the knowledge you gain from the lectures will a good starting point.

All the best

1

So I'm working on a program that works with a hash table. Here's how it goes:

1) Reads in a text file into a vector of "Symbol" objects (contains a name and a number) 2) Hashes the name of the Symbol object. 3) Inserts this object into the hash table.

So far I've been storing the uniquely generated hash keys as an array of integers. I then loop through the array and see if there's duplicates.

If there are, I know there's a collision. This method has proven to be successful however, now I have to write a rehash() function so I can get a new key that won't result in a collision.

I'm not sure if you're trying to implement what the NIST calls double-hashing, 2-choice hashing or a cuckoo hash. I think you're talking about double-hashing.

If you know every possible input, you can pick two hashes that have the properties you're looking for. Of course, if you know every possible input, you can pick a single hash that doesn't have any collisions.

If you don't care about performance, you can pick two different cryptographically secure hash functions, such as SHA3 and Skein. However, I highly doubt you'll want that. When blogs were discussing the meet-in-the-middle vulnerability in a widely-used hash function, I figured the simplest solution would be to use a function -- such as a cryptographically secure hash function -- engineered to be collision resistant. The simplest hash function I knew of that I felt would fit the bill, TEA, was more than ten times slower than the function it was meant to replace. Please note: TEA isn't secure for anything else, and since it would be a bad choice for a hash map, it's hard to find any use for it.

You could simply pick two wildy different hash functions and hope for the best.

There's SipHash, which is designed by a cryptographer to be collision-resistant even though it's not cryptographically secure. However, not everyone's happy with its performance (section "Hash Functions For Dynamic Languages"). Additionally, I'm not familiar with any similar analysis on SipHash's competition, so while I'm comfortable pointing you at SipHash, I'm not comfortable recommending a second hash.

I am much more comfortable recommending using a different approach to handle collisions. What you want to do isn't wrong, but it's off the beaten path and it's hard to find good advice for doing it.

So, my recommendations, (in order of preference) are:

  • Use std::unordered_map. Unfortunately, while you can replace the hash function used by std::unordered_map, it's a pain.
  • Use a single hash function, and handle collisions with separate chaining (use std::vector (nice for CPU cache, little more trouble adding/removing elements) or std::list for your lists).
  • Use a single hash function, and handle collisions with linear probing, this at least will play well with your CPU's cache.
  • If all else fails, use double-hashing, pick a fast hash algorithm that you know is vulnerable to collisions for the first hash, and SipHash to handle collisions. If there are few collisions, you'll have a fast hash map, and if there are lots of collisions, it'll be reasonable to rely on SipHash to handle them. If you're paranoid about collisions, you should assume that every insert or retrieval will call both hash functions. You'll have to decide if that's acceptable.

This method has proven to be successful however, now I have to write a rehash() function so I can get a new key that won't result in a collision. But I can't figure out how to do this.

I've included my Loop where I check the array of keys and my current hash function as well as my output. Any suggestions on where to go would be really appreciated.

In short:

  • when inserting, check if the slot is empty:
    • if the slot is empty, put the item there (you are done)
    • if something's already in the slot, call the rehash() method on the original key, if the slot suggested by rehash() is empty, put the item there; otherwise, call rehash(rehash(key)), and continue doing so until you find an empty slot (at least, that's how I unserstand the NIST page on double-hashing)
  • when retrieving, you have to find an empty slot before you can say an item is not in the map; e.g., if hash(key) returns an empty slot, you're done; if hash(hey) returns a slot with the item you're looking for, you're done; it hash(key) returns a slot with a different item, then you must call rehash(key) and rehash(rehash(key)) etc. until you either find what you're looking for or you find an empty slot
  • when removing items from the hash map, you'll probably want to use tombstones to say "I deleted what was here, but you'll need to keep calling rehash() to see if the element you're looking for is in the map"
  • when growing the hash, you basically create a larger container, and insert each element one at a time

If that seems daunting, reconsider whether std::unordered_map fits the bill.


I can now recommend a collision resistant hash other than SipHash (or, in fact, several).

0

The rehash could be something simple, like adding a number relatively prime to the table size, to the index, (open addressing). It could take multiple rehashes to find an available index in a hash table when adding keys to a hash table.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.