← OlimpiApp
Medio
Informatica · Strutture dati
Hash con scansione lineare: dove finisce la chiave 7?
Una tabella hash ha $m = 11$ celle con indici da 0 a 10 e funzione $h(k) = k \bmod 11$. Le collisioni si risolvono con scansione lineare: se la cella h(k) è occupata si provano, nell'ordine, le celle h(k)+1, h(k)+2, ... (modulo 11) finché se ne trova una libera. Partendo da tabella vuota si inseriscono nell'ordine le chiavi: 18, 41, 22, 44, 59, 32, 73, 7. In quale cella viene memorizzata la chiave 7?