melreams.com

I was reading this article about programming interviews a little while ago and one of the things they mentioned was that “A startlingly high percentage of interview questions reduce to breadth-first search or the use of a hash table to count uniques. You need to be able to write a BFS cold, and you need to understand how a hash table is implemented.” I saw that and started thinking wait a minute, how is a hash table implemented? I’m sure we covered that in college, but that was quite a while ago and I’ve forgotten a lot of stuff.

Quick note: Hash tables are also known as hash maps, dictionaries, associative arrays and probably more. I usually call them hash maps because that’s what they’re called in java.

For data structures, hash maps are really kind of cool. Under the hood, the data is actually stored in an array of linked lists. The interesting part is how the hash map decides where to put new elements. In a hash map, each array index is a bucket to put elements in, not the location of a single element. It uses a hash function (according to wikipedia, “any function that can be used to map data of arbitrary size to data of fixed size”, basically you give it an object and it gives you a number in a certain range) to decide which bucket to put any given item in. Hash % array length = array index to add item to. If there’s already an item in that bucket, it walks down the linked list to the last item and adds the new item to it. Because there can be multiple items in each “bucket,” the hash map creates an entry element that contains both the key and the value so it can find the right value for a given key when you ask for an element back.

Dividing the whole collection of keys and values into buckets is how hash maps work so quickly. If you had to search the whole list of keys each time it would much longer to get an element back from the hash map, but because of the bucketing system you only have to look at the elements in one bucket. It’s also very fast to add elements because you don’t need to worry about resorting the list, you just find the right bucket and add your new element to the end of the list.

There is a complication, though: the more items in each bucket the longer it takes to find an item. If your “buckets” fill up, you’ll need to expand the hash map by making a longer array and recalculating which bucket to put each and every item into. That can be a pretty bad performance hit if you have enough items in your hash map already. You also don’t necessarily want to avoid that problem by using a very large array, that just eats up memory for no good reason if you have so many buckets that you never end up putting anything in most of them.

Because of the bucketing system, hash maps are a great way to count uniques – being able to quickly find the right bucket and look through only a few items means you can add items or see whether the hash map already contains the item you want to add. On the other hand, hash maps aren’t very useful if you care about the order of your items or if you’re just going to process all of them in a loop. Getting a list of every element in a hash map involves walking each linked list in each bucket, which can take some time (and memory!) if you have enough items. If you’re going to process everything in your collection, skip the overhead of a hash map and just use an array list or linked list.

Okay, so given all of those implementation details, why are hash maps interesting to ask about in an interview? While it’s generally a good idea to understand data structures because they’re so core to what we do as programmers, I’m suspicious they get asked about in interviews because those interviewers were asked about them. Unless you’re interviewing a recent grad and want to make sure they paid attention in class, I’m not convinced that you really learn anything interesting about someone’s ability to code by asking for more details than what a hash map is good for and when you should use one. I mean, it’s been years since I forgot how a hash map actually works and I manage to write code that does what I meant most of the time :)