C++ Hash Table

I learned about hash tables in my Data Strucutures and Algorithms class. I thought they were the coolest thing because you could access and insert data immediately! Why would you not use hash tables everywhere? But there are drawbacks as I learned, like collisions.

The Project

Since hash tables were so powerful I wanted to build one. I thought a good application for it might be a word unscrambler. A word unscrambler is the thing you use to cheat in Words with Friends and scrabble. It takes in a set of letters (like "abc") and outputs a list of possible words to create from them (like cab, dab, and bad). A hash table is great for this because we need to compare permutations of the letters against all words to see if they match, meaning that permutation is a word. All these comparisons need to be fast, and a hash table is fast for accessing elements, just like looking up words in a dictionary.

Results

I downloaded a dictionary with 236k words, and engineered a hash table dictionary with collision resolution by chaining. If you want to know the math behind the whole thing then look into the presentation linked below, but the final table had an average lookup of 8 words. This means that when I want to compare one permutation of the input string (like bad), then I only need to compare it against 8 other words on average. In the computer science world, this is lightning quickâš¡.

Here we can see how my application performs when given up to 9 letters.

As you can see the total time is takes to unscramble quickly increases with more letters. This is because the permutations grow very quickly. There are n! permutations for n characters, and my algorithm tests each permutation against an average of 8 words.

What I Learned

  1. Hash Tables - I learned how to engineer one from top to bottom: collision resolution techniques for building them, hash functions for inserting and deleting, and managing the size of the table and the time it takes to find what you're looking for.
  2. Computation - This was my first project that used more than 20% of the CPU, so I realized that a lot of computer science is about making things efficient. Processing power is limited, so computer science is really about building amazing efficient things.

Conclusion

Hash tables are super cool and I really enjoyed this project. I hope I get to make one later when I'm working in the real world. I've finally broken through to the other side of computational power and made an application that will break if you push it too hard. I now understand the importance of efficient code.