Hashing

MIT 6.006 Introduction to Algorithms, lecture 4, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part sets up a proof that finding an item by its key cannot beat log n time when an algorithm can only compare keys.

Key ideas

A set stores items so you can look them up by their key, which is what the items intrinsically are. The lecture is trying to make the find operation faster than log n, which is already much better than checking every item one by one. 0:33
The comparison model treats each stored item as a black box. The only thing an algorithm may do is compare keys, such as checking whether one key is equal to, smaller than, or bigger than another. 5:15
An algorithm in this model can be drawn as a decision tree. Each internal node is a comparison with two possible branches, and each leaf is a final output. 7:21
The number of comparisons in one run is the number of steps along a single path from the top of the tree to one leaf, not the total number of nodes in the tree. 9:32
Since the search can return any of the n stored items, the tree needs at least n leaves, one for each possible output. 9:58

Words to know

key: The part of an item that you search by. Two items are the same for searching if their keys match.
comparison model: A limited way of working where the only thing you can do with items is compare their keys two at a time. You cannot look inside the keys.
decision tree: A diagram that shows every possible path a program can take, where each step is a yes or no question that splits the path into two branches.
leaf: The end point of a branch in a decision tree, where the program stops and gives its output.

Example

Imagine you have n sealed boxes, and one of them holds the prize. You are only allowed to ask questions like 'is this box heavier than that one?' Each answer can only send you down one of two paths, so the questions form a branching tree, and the tree must have room for every box to be the final answer.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part explains why comparison-based searching cannot beat logarithmic time, and how a direct access array can search in constant time but wastes space when keys are large.

Key ideas

A correct search must be able to return any of the n stored items or say the key is missing, so it needs at least n+1 possible endpoints (leaves) in its decision tree. 10:20
The worst-case number of comparisons equals the height of the tree, and a tree with n+1 leaves must have a height of at least log n. So comparison-based search takes at least logarithmic time. 12:33
Each comparison branches only a fixed number of ways, so comparisons alone cannot go faster than logarithmic. To go faster, the search has to branch a number of ways that grows with the input. 14:03
A direct access array uses the key as a position: an item with key 10 is stored at position 10, so finding, inserting, or deleting it takes constant time in the worst case. 16:43
The catch is that the key range can be far bigger than the number of items. Storing nine-digit MIT IDs for a few hundred people would need an array of about 10 to the 9th spaces, wasting most of the space. 18:54

Words to know

direct access array: A list where each item's key is used as its exact position, so you can jump straight to it without searching.
height: How many steps it takes to get from the top of a tree down to the bottom in the longest case.
branching factor: How many different paths a single step in a tree can lead to.
universe: The full range of possible keys you could ever store, whether or not you use them all.

Example

Imagine a hotel with a locker for each guest, and the locker number is the guest's room number. If you know the room number, you walk straight to the right locker without checking any others. But if room numbers go up to ten million and only 300 guests are staying, most of the lockers would sit empty and waste space.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part explains why a direct access array wastes space when keys come from a huge range, and how a hash function can shrink the array, which creates collisions that must then be handled.

Key ideas

A direct access array can hold a set quickly, but its size u is the largest key allowed, so a large universe of keys needs far too much space. 20:20
Keys must be integers here, because each key is used directly as an index (an address) in the array. Each key also has to fit in one machine word so lookups stay fast. 21:04
To save space, we use a smaller array of size m, roughly the number of items we store. A hash function h squeezes each big key down into a spot from 0 to m minus 1. 24:40
Squeezing many keys into few spots means two keys will sometimes land in the same spot. This is unavoidable, and it is called a collision. 26:36
There are two ways to deal with a collision. One is to store the extra item in another open spot in the same array, which is called open addressing. 29:31

Words to know

hash function: A rule that takes a key and turns it into a smaller number, which is used as the spot where the key is stored.
collision: When two different keys get the same spot from the hash function, so there is no room for both in that one spot.
open addressing: A way to handle collisions by searching the array for another empty spot and storing the item there.
pigeonhole principle: If you have more items than boxes, at least one box must hold more than one item.

Example

Imagine a hotel with 10 rooms and 8 guests, where each guest gets a room based on the first letter of their name. Two guests with names starting with the same letter may be sent to the same room, so the staff have to find another empty room for the second guest. That is like a collision, and finding a nearby empty room is like open addressing.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part explains how hash tables handle two keys landing in the same spot, and why picking a hash function at random helps keep lookups fast.

Key ideas

Any fixed hash function will sometimes send two different keys to the same index, and this is called a collision. 33:57
Chaining handles a collision by storing a pointer at that index to a second data structure, such as a linked list or dynamic array, that holds all the keys sent there. To look up a key, you check each item in that small structure. 30:43
The division method is a simple way to shrink a huge range of keys into a small set of slots: take the key and compute its remainder when divided by m (key mod m). 34:40
A fixed hash function can always be beaten by a bad set of inputs, so the lecturer chooses a hash function randomly instead, after the user has picked their inputs. 37:52
The random hash functions come from a family called universal hash functions, which are designed so that a randomly chosen one gives good performance on average. 39:19

Words to know

chaining: A way to handle collisions where each slot in the table holds a small list of all the items that landed there.
collision: When two different keys get sent to the same slot in a hash table.
deterministic: Always producing the same result for the same input. A deterministic hash function gives the same answer every time you run it.
universal hash function: A hash function picked at random from a special group of functions, built so that the chance of two keys colliding stays low.

Example

Imagine a coat check with numbered hooks, where each coat goes on the hook matching the first letter of its owner's name. Sometimes two coats land on the same hook, so you hang the extra coats on a small rack attached to that hook. When you look for a coat, you only need to check that small rack, not the whole room.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–52:48

This part explains how a random choice of hash function, called a universal hash family, keeps the lists in a hash table short on average.

Key ideas

The table does not use one fixed hash function. When the program starts, it picks a random a and b from a range, so the user cannot predict which function is used and cannot easily force bad collisions. 42:53
Universal means that for any two different keys, the chance they land in the same spot (a collision) is at most 1/m, where m is the table size. 43:34
To measure chain length, the lesson uses an indicator random variable: it is 1 if two keys collide and 0 if they do not. Adding these up for one spot gives the chain length there. 46:04
Using expected value, the average chain length works out to about 1 plus (n minus 1) divided by m. So if m is at least about n, chains stay short on average. 51:32
If the table fills up so that m is no longer large compared with n, the whole table is rebuilt with a bigger m, the same way a dynamic array grows. 52:15

Words to know

hash family: A group of many possible hash functions. The table picks one at random from the group when it starts.
collision: When two different keys get sent to the same spot in the table.
indicator random variable: A simple counter that is 1 when something happens (like a collision) and 0 when it does not.
expected value: The average result you would get if you repeated a random process many times.

Example

Think of a coat check where each coat is put on a hook chosen by a secret random rule picked when the room opens. Because nobody knows the rule, nobody can plan to pile all the coats on one hook. With enough hooks, the piles stay small on average.

3 checked practice questions for this part are in the app.

← Lecture 3: Sets and Sorting · Lecture 6: Binary Trees, Part 1 →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York