constant time, most of the time

say you work at a library and someone asks for War and Peace. you need its shelf number.

if your list of books isn't sorted, you read it from the top until you find it. that's a linear search, O(n). sort the list and you can do a binary search, O(log n). better, but the reader still waits while you flip pages.

what you want is to just know. someone says "War and Peace", you say "4578". that's what a hash table does, in O(1), most of the time.

#a function that turns names into numbers

a hash function takes some bytes, like a book title, and gives back a number. for a hash table, it has to do three things:

• the same input always gives the same number. if War and Peace is 4578 today and 12 tomorrow, you'll never find it again.
• different inputs spread out over different numbers. they can't all be different, since there are more possible titles than slots, but the fewer that land on the same one, the better.
• the number fits the array. a table with 10,000 slots needs numbers from 0 to 9,999.

put it next to an array: hash the title, get 4578, and store the shelf number at index 4578. to find it later, hash the title again and read index 4578. no searching, just one jump.

you'll almost never write one yourself. in JavaScript it's Map, and the spec says it has to be a hash table, or something else with lookups faster than linear on average:

const shelves = new Map();
shelves.set('War and Peace', 4578);
shelves.set('1984', 1532);
console.log(shelves.get('War and Peace')); // 4578

plain objects work too, but they come with keys you never put there:

const shelves = {};
console.log(shelves['constructor'] ? 'found' : 'not found'); // found

#what they're good for

looking things up. which room is each teacher in?

const rooms = new Map([
  ['Donald E. Knuth', 'A123'],
  ['Alan Kay', 'B456'],
]);
console.log(rooms.get('Alan Kay')); // B456

catching duplicates. has this guest already come in? a Set is a hash table with keys and no values:

const entered = new Set();
 
function arrive(guest) {
  if (entered.has(guest)) return 'already in';
  entered.add(guest);
  return 'welcome';
}
 
console.log(arrive('Erick Wendel')); // welcome
console.log(arrive('Erick Wendel')); // already in

caching. if building a page is slow, keep it under its URL and hand that back next time:

const cache = new Map();
 
async function getPage(url) {
  if (!cache.has(url)) cache.set(url, await render(url));
  return cache.get(url);
}

#collisions

say the hash function puts each city in a slot by its first letter. Augusta goes in slot a. then Annapolis wants slot a too. two keys, one slot: that's a collision.

the usual fix is a list in each slot. Augusta and Annapolis both live in slot a, and finding one means walking that list.

with three cities that's fine. with thousands starting with a, slot a is a long linked list and the rest of the table sits empty. two things keep it from getting there:

• a hash function that spreads keys evenly. first letter is a terrible one.
• enough slots for what you're storing.

#the numbers

on average a hash table reads like an array and inserts like a linked list. the worst case is every key in the same slot, and then it's a linked list with extra steps.

#load factor

the load factor is how full the table is: items divided by slots. 6 items in 8 slots is 0.75.

the fuller it gets, the more keys collide, so tables grow before they fill up. Java's HashMap grows past 0.75, and Python's dict past two thirds. growing means a new array twice the size, with every item hashed again, because the slot an item lands in depends on how many slots there are.

that's O(n) every now and then. but the array doubles each time, so it happens less and less, and spread over all the inserts it still comes out to O(1) each. constant time, most of the time.