HashMaps

A HashMap is a data structure that serves as a map, implemented using a hashing function.

“Map” means a data structure for storing and accessing data via a key -> value relationship.

MDN documentation on Maps: “The Map object holds key-value pairs and remembers the original insertion order of the keys. Any value (both objects and primitive values) may be used as either a key or a value.”

Construct a map

const contacts = new Map()
contacts.set('Jessie', {phone: "213-555-1234", address: "123 N 1st Ave"})

Parameters

iterablean array or other iterable objects whose elements are key-value pairs. (For example, arrays with two elements, such as [[ 1, 'one' ],[ 2, 'two' ]].) Each key-value pair is added to the new Map.

Description

A Map object iterates its elements in insertion order — a for...of loop returns an array of [key, value] for each iteration.

Objects and maps compared

Object is similar to Map—both let you set keys to values, retrieve those values, delete keys, and detect whether something is stored at a key. Because of this (and because there were no built-in alternatives), Objects have been used as Maps historically.

However, there are important differences that make Map preferable in certain cases:

• The keys of an object can only be strings or symbols, whereas they can be any value for a map, including functions, objects, and any primitive data type.
• The keys in map are ordered while keys added to the object are not. Thus, when iterating over it, a map object returns keys in order of insertion.
• An Object has a prototype, so there are default keys in the map that could collide with your keys if you're not careful.

In other words, you can give a HashMap one or more pairs of a key and a value that goes with it, and later give it the key to use to look up a particular value. We use this to organise the data that our program needs to keep track of.

Other terms similar to “map” include a dictionary, associative array, or a symbol table. Another term for this is a Hash Table, and in fact, in the early versions of Java, “HashTable” was the name of the class that was later replaced by HashMap.

A hash function is a mathematical function that you run a number through and get a result. Usually a unique result (though not always, there are different kinds of hash functions used for different purposes). HashMap uses the result you get from feeding the key through the hash function to decide where in its internal data structure to stash the value.

The advantage of doing it this way is that the HashMap can later look at the key and just figure out, without having to look at anything else, where to find the value. Usually, this is a lot faster than alternative approaches, especially if you have a lot of key/value pairs.

Implementing a HashMap:

Actually, there are two ways to build a hashMap: arrays and binary search trees. The most common implementation of hashMaps is using an array and a hash function.

The first step to implement a HashMap is to have a hash function. This function will map every key to its value. Keys are mapped into an array of “buckets” using the hash function. If we have 1000 values in our array of buckets and we are trying to determine whether a certain value exists in our hashmap, we use a hash function to be able to reference values in our hashmap.

A common hash function is using modulus %. If we have a hashmap of 10 different buckets and we have 1000 values we need to map, we can mod each value by 10 to assign it to a certain bucket. If we want to ‘get’ a certain value, we find which bucket we need to look in and then find the value within.

When deciding what hash function to use to map values, we aim for two things:

1. A hash function that produces as few collisions as possible.
2. An array big enough to hold all the required values. If we have a big enough bucket we won’t have collisions thus the search time would be O(1).

The name hashMap or hash comes from the technique used within called hashing. Hashing is a technique of converting a large String to small String that represents the same String.

The example I usually use is the following, although strictly speaking it’s not, in mathematical terms, a hash function:

Let’s say you need to keep track of a lot of people’s names.

Let’s say it’s bar tabs. You’re running a bar. When people open a tab, they hand you their credit card, and you chuck it in a shoebox under the cash register.

When it comes time to pay the tab, the customer tells you their name and you paw through the credit cards in the shoebox to find their credit card. Usually, there aren’t that many credit cards, and it doesn’t take you that long to find it.

Your bar gets popular and pretty soon you have dozens of credit cards in your shoebox. It’s starting to take too long to find the right credit card, even though you’re keeping the credit cards sorted alphabetically by name.

To speed things up, you decide to start using dividers to separate the box in sections, one for each letter of the alphabet.

Now you can look at somebody’s name (the key) and know right away which section to look in. If, for example, their name starts with the letter “O” that means they’re in the 15th section of the box.

That, right there, is, metaphorically speaking, the hash function. By looking at the key data (their name) you can figure out, without looking through the credit cards, which section the value (their card) is in.

Things to remember:

Hashmaps are always a good datatype to consider using when writing algorithms because of its time complexity. They provide constant time complexity for basic operations, get, set, and delete, if the hash function is properly written.

Resources:

Map