Hash tables

With 47 stored in a table of 7 buckets, the computer goes straight to bucket 47 mod 7 = 5 instead of searching the whole table.

Turning a key into a position

So far, finding a value meant searching: up to n steps in an unsorted array or a linked list. Arrays, though, can reach any position in one step. What if the key itself told you the position? If your keys were small whole numbers, say student numbers from 0 to 99, you could keep an array of 100 cells and store student k in cell k. MIT's notes call this a direct access array. It fails when the possible keys are huge, like phone numbers or words, because you cannot afford a cell for every possible key.

A hash function solves that by squeezing any key into a small range of positions, 0 to m − 1. A simple one for whole numbers is h(k) = k mod m, the remainder after dividing by m. The array of m cells is the hash table, and its cells are often called buckets. To store 47 with m = 7, compute 47 mod 7 = 5 and put it in bucket 5. To find 47 later, compute the same thing and look only in bucket 5.

Collisions and chaining

There is a problem. With 7 buckets and more than 7 possible keys, some keys must share a bucket: 12, 33 and 47 all give remainder 5. This is called a collision, and MIT's notes point out that it cannot be avoided, by the pigeonhole principle. The usual remedy is chaining: each bucket holds a small list, a chain, of every key that hashed there. Finding 47 then costs 1 step for the hash plus one comparison for each key checked in chain 5. If 12 and 33 are ahead of it, that is 1 + 3 = 4 steps.

How long are the chains? If the keys spread evenly, each chain holds about n/m keys, a number called the load factor. Keep m about as large as n and the chains stay short, so finding, inserting and deleting take a constant number of steps on average. The danger is a bad spread. If every key hashes to the same bucket, one chain holds all n keys and the table is no better than a linked list. In the lab, set 7 buckets and insert 14, 21 and 28: they all land in bucket 0.

Hash tables in JavaScript

You seldom write a hash table yourself, because JavaScript has Map and Set. The ECMAScript specification says they "must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements". In other words, map.get(key) and set.has(x) must be faster than searching the whole collection. MDN adds that a Map keeps keys in insertion order and, unlike a plain object, contains no default keys that could collide with yours.

const price = new Map();
price.set("apple", 1.2);
price.set("bread", 2.5);
console.log(price.get("bread")); // 2.5, no search through the list
console.log(price.has("milk"));  // false
const seen = new Set([4, 8, 15]);
console.log(seen.has(8));        // true