# constant time, most of the time

2023-11-28 · 5 min read · #data-structures · #algorithms

Source: https://jopcmelo.com/writing/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.**

*(sketch: three book titles go into a box marked hash, where a gear turns, and each comes out as an arrow to its own slot in a row of eight)*

you'll almost never write one yourself. in JavaScript it's `Map`, and [the spec](https://tc39.es/ecma262/#sec-map-objects) says it has to be a hash table, or something else with lookups faster than linear on average:

```javascript
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:

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

## what they're good for

looking things up. which room is each teacher in?

```javascript
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:

```javascript
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:

```javascript
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.

*(sketch: slots a to e. slot a holds a chain: Augusta, then Annapolis, then Auburn. slot b holds Boston alone)*

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

|        | hash table, average | hash table, worst | array  | linked list |
| ------ | ------------------- | ----------------- | ------ | ----------- |
| read   | `O(1)`              | `O(n)`            | `O(1)` | `O(n)`      |
| insert | `O(1)`              | `O(n)`            | `O(n)` | `O(1)`      |
| delete | `O(1)`              | `O(n)`            | `O(n)` | `O(1)`      |

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](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/HashMap.html), and Python's dict past [two thirds](https://github.com/python/cpython/blob/main/Objects/dictobject.c). 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.

*(sketch: eight slots with six full, load factor 0.75. an arrow marked double, then hash again leads to sixteen slots with the same six spread out, load factor 0.375)*

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.**