This page assumes nothing. Every symbol the parent note throws at you — h, U, m, Pr, mod, p, α, E[⋅], the indicator Xxy — is built here from the ground up, in the order that lets each one lean on the one before it. Read top to bottom; by the end the parent note reads like plain English.
Look at the figure. On the left is a pile of keys (arbitrary things — words, IDs, numbers). In the middle is the rule (a machine). On the right is the table: a row of numbered boxes. The rule reads a key and points at exactly one box.
Two keys landing in the same box is called a collision (the coral pair in the figure). Collisions are not errors — the box just holds a little list (a chain) — but too many in one box means slow searching. Everything in this topic is about keeping collisions rare. (For how a full box is handled, see Hashing — chaining vs open addressing.)
Picture a giant warehouse containing every possible key: all account numbers from 0 to 999999999, or every possible word. The keys you actually insert are a tiny handful pulled from this warehouse.
Why the topic needs it: the guarantee must hold for any keys the enemy might pick, and "any" means "any from U". We name the warehouse so we can say "for every x,y in U" precisely.
We write h(x) for "the box that rule h sends key x to". If h(x)=h(y), keys x and y collide.
The figure shows two different rules h1 and h2 over the same keys. Notice: under h1 the two coral keys collide; under h2 they land apart. Different rule, different collisions — this is the seed of the whole idea. If we can choose which rule, we can dodge bad collisions.
The symbol ∈ means is a member of ("belongs to"). So h∈H = "h is one of the rules in the family".
Why the topic needs it: the entire trick is drawing a rule at random from H. You cannot draw at random from a single rule — you need a bag to draw from. H is that bag.
Our random experiment is: draw a card h from the deck H, uniformly at random.
So Prh∈H[h(x)=h(y)] reads: "pick a random rule from the bag; what fraction of the bag's rules make x and y collide?" The little "h∈H" under Pr just says which thing is being randomised — the rule, not the keys.
The figure is the mental model of this probability: a bag of coloured tokens (each token = one rule). Green tokens = "this rule keeps x,y apart", red tokens = "this rule collides them". The probability of collision is just (red tokens) ÷ (all tokens). Universal will mean: for every pair x,y, the red fraction is at most m1.
Concrete picture: roll a fair die, let X be the top face. Sometimes X=1, sometimes 6; the average over many rolls is 61+2+3+4+5+6=3.5. That 3.5 is E[X]. You never see3.5 on one roll — it's the centre of gravity of the outcomes.
Why the topic needs it: we can't promise "you will never have collisions". We promise something weaker but honest — "on average, very few". That average is E.
Picture a clock with b marks. Counting a steps around it, mod is where the hand stops. E.g. 34mod17: go 34 steps around a 17-mark clock — two full loops (34 = 17+17) land you back at 0. So 34mod17=0.
The figure shows the clock idea: numbers 0,1,2,… wrapping around a circle of m marks. Why the topic needs mod: it is the squeezer that forces any big number into the valid range [0,m−1] — the last step of ha,b(k)=((ak+b)modp)modm.
Why the topic needs it: the whole punchline is "expected work =O(1+α)". Keep boxes proportional to keys (m=Θ(n)) and α stays a small constant, so every operation is expected O(1). Growing the table to keep α small is the job of Load factor and rehashing.
