Before you can read the parent note (Hash table — structure), you must be able to read every symbol it uses without pausing. This page builds each one from nothing, in the order they depend on each other.
Figure 1 — A six-box array A B C D E F with indices 0..5 printed underneath. Box 3 is highlighted orange with an arrow reading "jump straight here, no walking past 0,1,2". Takeaway: knowing the index lets you land on a box directly.
We will call the number of boxes the capacity and give it the letter m. So a valid index is any whole number from 0 up to m−1.
Recall Why do indices stop at
m−1, not m?
Because we start counting at 0. ::: An array of m boxes has indices 0,1,2,…,m−1 — that is exactly m numbers, and box m would be off the end.
This is why the parent note links Sets and Maps / Dictionaries — a hash table is the machine that makes dictionaries fast. A set is just a map that stores keys with no values (it only remembers whether a key is present).
The parent note throws around n, m, "buckets", and "slots". Here they are, once and clearly.
Figure 2 — Eight boxes indexed 0..7; three are filled green ("key") and five are empty white. A blue arrow labels the whole row "m = 8 boxes exist (capacity)"; text below reads "n = 3 boxes filled right now → alpha = n/m = 3/8 = 0.375". Takeaway: m counts boxes that exist, n counts boxes filled now.
The parent writes index = hash(key) % m and h(k) = k mod m. Here we finally define what those marks mean. The symbol % in program code, the word mod in maths, and the notation modall mean the same single operation — take the remainder. (So when the parent writes hash(key) % m, read it as "hash(key) modulo m".) This is the most important operator on the page, so we build it from zero.
WHY this exact tool and not division? We have a possibly gigantic number (a hash code, maybe billions) but only m boxes. We need to fold that huge number down into a valid index 0…m−1 — and modulo is precisely the operation whose output is guaranteed to be a legal index. Ordinary division would give a fraction; subtraction would overflow the range. Only "the remainder" is trapped inside [0,m−1] by definition. That is why it's the compression step.
Figure 3 — Five slots 0,1,2,3,4 arranged around a clock face. An orange hand points at slot 2, captioned "12 mod 5 = 2 (wrap around like a clock)"; below in red "22 mod 5 = 2 too → collision!". Takeaway: modulo maps any number onto the dial 0..m−1, and different inputs can point to the same slot.
Notice three different keys (12,22,17) all produced index 2. That is the whole reason collision resolution exists — and you just derived it with one operator.
Recall What is
7mod7? And 0mod7?
Both are 0. ::: 7=1×7+0 and 0=0×7+0 — any exact multiple of m, including 0 itself, has remainder 0.
Now that we have "key", "index", and "mod", we can finally read the star of the show.
The notation h:keys→{0,1,…,m−1} (which the parent writes) is read: "h is a rule sending each key to one number in the set {0 up to m−1}." The arrow → just means "produces". The curly braces {…} mean "the collection of these numbers".
The parent's string hash uses ∑i=0L−1si⋅pL−1−i. That wall of symbols scares people off. Disarm it piece by piece — and note it uses only the ⋅ (multiply) and the power ab from §0.
Here L is the length of the string (how many characters), si is the i-th character's number (its ASCII code), and pL−1−i is the base p raised to a power (repeated multiplication, from §0) — read Polynomial rolling hash & Rabin–Karp for why the powers descend as i grows. The one thing you need here is: this formula treats the string as a number written in base p, so that letter order changes the result. A plain sum s0+s1+… would ignore order and make "ab" and "ba" collide.
