Qual è una buona strategia di crescita per le tabelle hash? Se il numero di elementi supera il numero di bucket, aumento il numero di bucket con la seguente formula:
n = int(n * 1.618033988749895) | 1;
Suona sensato? (La parte | 1 garantisce di ottenere un numero dispari.)
Manterrei il rapporto di crescita un po ' meno della media aurea. Ciò significa che (supponendo che fossero contigui) a un certo punto, i pezzi che hai scartato sarebbero bastati a recuperare il chunk successivo di cui hai bisogno. Infatti, per semplicità (per non parlare di evitare la matematica FP) probabilmente userò solo n + n/2 | 1 .
La prossima domanda è quando hai bisogno di fare la crescita. Questo varia ampiamente a seconda di come si risolvono le collisioni. Se si utilizza il sondaggio lineare, è probabile che si desideri ridimensionarlo quando la tabella si trova in un punto intorno al 70-80% (al massimo) al massimo. Verso l'estremo opposto, se utilizzi il concatenamento, in genere puoi attendere fino a quando la tabella non viene riempita eccessivamente di un fattore di circa 3 o 4.
Uno dei miei preferiti è usare una tabella di alberi bilanciati. In questo caso, devo ancora vedere una situazione in cui il ridimensionamento ha avuto molto senso - mentre si riempie troppo il tavolo, lentamente degrada da O (1) a O (lg N), ma dovresti essere abbastanza alcuni ordini di grandezza sulla dimensione del tavolo prima che valesse la pena di ridimensionare.
Una buona strategia di crescita tiene conto
I due problemi evidenti con quel piano di crescita sono la possibile frammentazione della memoria, anche se questo dipende anche da come viene implementato l'array sottostante) e naturalmente dal fatto che l'espressione trabocca: il lato destro dell'espressione può comportare un overflow. In C, questo ha prodotto un comportamento indefinito. In altre lingue, questo può produrre un'eccezione di runtime o un nuovo valore di n che è più piccolo di quello precedente.
Leggi altre domande sui tag data-structures hashing