Hashing
Introduzido
Vocabulário
| English | Significado |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | A function mapping a key to a hash value used to choose or locate a table position. |
| collision/kəˈlɪʒn/ | A conflict such as different keys mapping to the same hash location, or simultaneous transmissions interfering on a shared network medium. |
| chaining/ˈtʃeɪnɪŋ/ | Handling hash collisions by storing multiple entries at one bucket. |
| open addressing | Handling hash collisions by probing other positions within the table. |
| load factor/ləʊd ˈfæktə/ | The number of stored hash-table entries divided by the number of buckets or slots. |
| clustering | Groups of occupied hash-table positions that can lengthen probe sequences. |
English
Spread, collide, resolve
- A hash function maps a key to a bucket: $h(k) = k \bmod 13$ sends $4, 17, 30, 43$ all to bucket $4$ — a collision. Chaining hangs a list off each bucket; open addressing walks to the next free slot.
{exercise:uni-cs0503-buckets}
Prática
Under h(k) = k mod 13, the keys 4, 17, 30, 43 all land —
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Each key leaves remainder 4 on division by 13 — one crowded bucket.
English
The load factor rules the chain
- With $m$ buckets and $n$ keys, the load factor $\alpha = n/m$ is also the average chain length: our fixed keys $[4, 17, 30, 43, 12, 25, 38]$ give $\alpha = 7/13 \approx 0.54$ — bucket $4$ holds four keys, bucket $12$ holds three, ten buckets sit empty.
- Successful search costs about $1 + \alpha/2$ comparisons with chaining; grow $m$ with $n$ and the expected cost stays $O(1)$ — that resize is why dictionaries stay fast.
{exercise:uni-cs0503-load}
Prática
Seven keys in thirteen buckets give a load factor of —
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Alpha is keys over buckets: 7/13 is about 0.54 — also the average chain length.
English
Probing and clustering
- Linear probing on $4, 17, 30, 43$: slot $4$; then $17$ probes $4 \to 5$; $30$ probes $4, 5 \to 6$; $43$ probes $4, 5, 6 \to 7$. Total: $1 + 2 + 3 + 4 = 10$ probes for four insertions.
- Clustering grows those runs, which is why real tables keep $\alpha$ under about $0.75$. Do not modulo a power of two when keys share low bits (pick a prime), and never mutate a key while it sits in the table.
{exercise:uni-cs0503-probe}
Prática
Linear-probing inserts of 4, 17, 30, 43 take —
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
1 + 2 + 3 + 4 = 10: each new key walks the growing cluster.