Hash, chi può aiutarmi?

[Zittino Bob]

Ciao a tutti, devo presentare un elaborato e mi è stato richiesto quanto segue relativo alle tecniche di eliminazione di collisioni delle tabelle di hashing.

Riporto quanto mi è stato chiesto:
"Una strategia alternativa per risolvere il problema delle collisioni in una tabella di hash, sarebbe di definire una sequenza, f(i) = ri (cioè r di i), dove r0=0 e r1,r2 ... rn è una permutazione random dei primi n interi (ogni intero appare esattamente una volta).

a. Provare che con questa strategia, se la tabella non è piena, il problema delle collisioni può sempre essere risolto.

b. Questa strategia favorisce l'eliminazione del clustering?

c. Se il load factor della tabella è Q, qual'è il tempo stimato per effettuare un inserimento?

d. Se il load factor della tabella è Q, qual'è il tempo stimato per effettuare una ricerca con successo?"


Qualcuno può aiutarmi?
Grazie a tutti...