Hash tables: a crash course on what they are

Fri, 18 Jul 2014, by Josh Maines

This is really just a placeholder for unwritten content that explains hash tables in an easy-to-understand fashion.  I will update it later with pictures and more information.

What are hash tables?

If you ever used an array in a programming language and thought "there has to be a better way to search through this array" you should consider using hash tables.  A hash table is like a book of arrays or an array of arrays even.  You basically have indexes which say where sections of content are.  Then, you optionally have subsections inside each section.  In that sense, you could think of it like looking in a phone book for John Smith and skipping to the page where names with the letter s begin so you can search fewer pages for the name smith.

For you game developers out there, think of it like this:

You have an array or a dictionary of names for randomly generated content.  You want to generate a sword that has specific attributes but you don't want to search for the number for each attribute's index number in the array of attributes.  You find it easier to just code a search function that finds the attribute's name in the array by looping through it until the value matches.  The performance doesn't really matter at first because you only have maybe 20 or 30 attributes in the array.  However, you decide to add more and more attributes to that array until eventually your game is failing to search through the thousands of attribute names you have quickly enough.  You need a way to speed up the process of searching the database of attributes.  The hash table is your solution.

I recommend that all software programmers learn about hash tables as soon as they can, because it is not only a very useful technique but also a very popular interview topic.  For the longest time, I didn't even know what a hash table was, so I must have seemed very foolish to some interviewers for software development positions.  However, I always called them dictionaries and always thought it was a fairly simply idea.  It wasn't until I was interviewed that I thought "well, there's something new to learn about" and found out my terminology was wrong... well, different anyway.  Regardless of what you call this technique, it is useful, and honestly, I still don't understand why we call them hash tables.