0

Looking for advice on hash functions and strings.

For PSET5, I decided to implement a trie but instead of storing [a - z] in each node, only storing [0 - 9]. For this to work, I hashed the words and included their hashes on the nodes.

Spell check works fine, valgrind returns no errors and check50 was successful but my hash function returns collisions. Which also means that when I check my results with the staff, some words are missed in my spell check (false positives).

I've included a counter for collisions on the dictionary and it returns:

Hash function returned 1 collisions out of a total number of 143091 words loaded. Note: some collisions may be duplicate dictionary words.

Here's the code for the hash function I am using. I've adapted the djb2 hash. Looking for a better way to do this to minimize collisions. Also, this is generating very large numbers which is inefficient since there are 143,091 words to be loaded.

long long hashdjb(string str) 
{
    unsigned long hash = 5381;
    int c = 0;
    for (int i = 0; i < strlen(str); ++i)
    {
        c = (int)str[i];
        hash = ((hash << 7) + hash) + c; // the << operator includes 5 bits of zeroes at the right
        // changing to 7 improved collisions
}
    hash = hash % (4294967291); //limits the size of the hash -- too small will cause collisions!
    // this is a modification I had to make to make sure the number
   // wouldn't blow up. Using here a large prime number.
   return (hash);
}
1

There are better options than the DJB2 algorithm! Try using this algorithm called Murmur2! From what I've gathered, it's great in terms of speed and excellent in distribution!

Here's a StackExchange post detailing this algorithm's performance compared with other common ones, such the one you use:

https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed

Now, here's some sample code that shows how the algorithm is implemented. This is only a head start, up to you how you would adapt it to the pset's case!

https://github.com/abrandoned/murmur2

There is a Murmur3 algorithm by the way, and this one's actually slightly faster! Just included it because it is worth the check but it's not detailed in the StackExchange post. Some sample code too:

https://github.com/PeterScott/murmur3

1
  • Thanks so much! Will research these. At first glance, Murmur2 looks like a great solution to improve results. – PXSOCS Jul 15 '18 at 20:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .