1. Hashing Functions
Problem: store customer records so they can be retrieved quickly. Each record has a unique key (e.g. Social Security number). A hashing function assigns memory location .
Most common choice:
Why it’s good:
- Easy to evaluate — just one remainder.
- Onto (surjective) — every location can be used.
Surjective: for every in the codomain there is at least one with .
Example:
Collisions
is not one-to-one (more keys than locations), so two keys can map to the same place — a collision.
- → collision at 14.
Linear probing resolves it: use the first free location after the occupied one,
Location 15 is free, so the second record goes to 15.
2. Pseudorandom Numbers
True randomness is very hard to produce; systematic methods produce pseudorandom numbers — fast to generate, but too predictable for some tasks (e.g. security).
Linear congruential method
Choose: modulus , multiplier , increment , seed with
Generate
For numbers in use .
Example: :
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 7 | 8 | 6 | 1 | 2 | 0 | 4 | 5 | 3 |
, so the sequence repeats with period 9: 3, 7, 8, 6, 1, 2, 0, 4, 5, 3, …
Pure multiplicative generator: . Widely used: , — generates numbers before repeating.
3. Check Digits
Append an extra digit computed from the others; on reading, recompute it to detect errors.
3.1 Parity check bits
For bit string :
- if the number of 1s is even, if odd.
- Detects an odd number of bit errors; misses an even number of errors.
Example (last bit = parity bit):
01100101: = parity bit ✓ → accept (may still hide an even number of errors).11010110: ✗ → reject.
3.2 Universal Product Codes (UPC)
12 digits: 1 product category · 5 manufacturer · 5 product · 1 check digit. Valid iff
(odd positions weighted 3, even positions weighted 1).
(a) First 11 digits 79357343104 → ; ⇒ check digit 2.
(b) 041331021641 → ⇒ not valid.
3.3 ISBN-10
10-digit code (language, publisher, book number, check digit). The check digit may be X (= 10).
(ISBN-13 was later introduced for more titles.)
Example — find the check digit of 007288008:
.
Example — validate 084930149X:
⇒ not valid.
3.4 Error detection with ISBN-10
Common errors: single error (one digit wrong) and transposition (two digits swapped). ISBN-10 detects both.
Single error: with , , all other digits equal:
because , and , (11 is prime).
Transposition of unequal digits in positions (, ):
because and .
Why mod 11 works so well: 11 is prime, so a product of two non-multiples of 11 is never . (Whether UPC detects these errors: Exercises 26–27.)