Zittino Bob
09-11-2004, 18:07
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...
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...