Informatica I - le prestazioni di una tabella hash con bucket

Prestazioni delle funzioni di hash

Le prestazioni dipendono fortemente dalle caratteristiche della funzione di hash. Una "buona" funzione di hash minimizza le collisioni, cioè fornisce chiavi ridotte distribuite in maniera uniforme nella tabella. In questo modo, le liste in ogni bucket hanno tutte circa la stessa lunghezza (minima).

Caso peggiore

La funzione di hash restituisce sempre la stessa chiave ridotta, per ogni chiave possibile. Allora, tutti i dati vengono inseriti in un’unica lista. In questo caso, le O(1) prestazioni della tabella hash degenerano in quelle di una lista, tutte le operazioni sono O(n).

Se la funzione di hash restituisce chiavi ridotte che si distribuiscono uniformemente nella tabella, tutte le liste hanno la stessa lunghezza media. Se N è la dimensione della tabella, la lunghezza media di ciascuna lista è n/N. Tutte le operazioni sono O(N/n). E se la tabella è dimensionata in modo tale che N sia dello stesso ordine di grandezza di n, allora O(1).

Se queste due assunzioni sono verificate, tutte le operazioni sulla tabella hash sono in media O(1).

Riassumendo

In una tabella hash con bucket si ottengono prestazioni in media ottimali, ovvero O(1), se:

• La dimensione della tabella è circa uguale al numero di dati che saranno memorizzati nella tabella. Ovvero, se il fattore di riempimento è circa unitario (così si riduce al minimo anche lo spreco di memoria).
• La funzione di hash genera chiavi ridotte che siano uniformemente distribuite, ovvero produce liste di lunghezza quasi uguale alla lunghezza media.

Sotto queste ipotesi, le liste hanno quasi tutte lunghezza uno!