Ha senso per ridimensionare un basso Hash Table? E quando?

Question

La mia implementazione Hash Table ha una funzione per ridimensionare la tabella in cui il corso di carico di circa il 70%. Il mio Hash Table è implementata con concatenazioni separate per le collisioni.

Ha senso che avrei dovuto ridimensionare la tabella in basso hash in qualsiasi punto o dovrei semplicemente lasciare le cose come stanno? In caso contrario, se aumentare la dimensione (da quasi il doppio, in realtà seguo questo: http://planetmath.org /encyclopedia/GoodHashTablePrimes.html ) quando il carico è del 70%, dovuto a ridimensionare il basso quando il carico ottiene il 30% o al di sotto?

Answer 1

Stai scrivendo la tabella di hash per uso generale, o c'è uno scopo specifico per questo? Io non suggerisco di ridimensionamento più piccola per un'implementazione generale. Ciò manterrà il vostro tavolo semplice e tenerlo da botte di memoria in condizioni in cui la tavola viene riempito e svuotato spesso. Se si finisce per imbattersi in una condizione in cui le esigenze di tabella hash di ridurre in termini di dimensioni, estenderla a quel punto nel tempo.

Answer 2

Le tabelle hash non devono avere lunghezze prime-numerici se si dispone di una funzione di hash di buona qualità (vedi qui ). È possibile farli potenze di due, che accelera notevolmente fino calcoli di indice.

Perché questo è pertinente alla questione? Perché quando si compatta una tabella hash potenze di due, è possibile lasciare tutte le voci nella parte inferiore dove si trovano e semplicemente aggiungere l'elenco collegato nello slot i (dalla metà superiore) sulla lista collegata nello slot i - n/2.

Answer 3

Se la memoria è a buon mercato, lascia stare. Se la memoria è costoso, ridimensionare con isteresi come avete suggerito. Una volta fatto, il profilo il risultato per assicurarsi che si comporta bene e non hanno fatto qualcosa di stupido.

Answer 4

Per prima idea: L'unica ragione per la coltivazione di una tabella hash è perché le prestazioni tabella hash diminuisce se ci sono troppe collisioni. Crescente tavolo quando il carico supera il 70% è una buona regola del pollice per evitare che ciò accada, ma è solo una regola del pollice. Molto meglio è quello di tenere traccia del numero di collisioni e crescere solo la tabella hash se superano un certo limite o una volta un certo rapporto di collisione viene colpito. Dopo tutto, perché si vuole far crescere una tabella hash che viene caricato del 90%, ma non ha una singola collisione? Essa non avrebbe alcun vantaggio.

Seconda idea: L'unico motivo per ridurre una tabella hash è quello di salvare la memoria, eppure contrazione potrebbe aumentare il numero di collisioni e ridurre le prestazioni di ricerca in tal modo. Si tratta di una velocità classica vs commercio memoria fuori e perché si dovrebbe risolverli autonomamente? Lascia fare a chi sta utilizzando il codice. Proprio mai ridursi da soli, ma offrire un metodo strizzacervelli. Se l'utilizzo della memoria bassa è un requisito, chi sta usando il codice può chiamare shrink regolarmente. Se il massimo delle prestazioni, se un requisito, chi sta utilizzando il codice non dovrebbe mai chiamare ridursi. Tutti gli altri possono utilizzare un qualche tipo di euristica per decidere se e quando chiamare strizzacervelli.

terza idea: Quando crescita o in calo, sempre crescere / ridursi in tal modo un che dopo l'operazione è garantito un certo fattore di carico. Per esempio. quando cresce, crescere sempre in modo che dopo il fattore di carico è del 50% e quando contrazione, ridurre sempre in tal modo un che poi il fattore di carico è del 70%. Naturalmente, che non dice nulla circa il numero di collisioni, in modo da aggiungere un elemento subito dopo la crescita / contrazione può causare la tabella hash a crescere di nuovo, ma che è inevitabile come simulare l'effetto di un crescere / strizzacervelli di solito è troppo costoso. Anche ridursi sarà spesso chiamato una volta ogni ulteriore modifica sono piallati, quindi dovrebbe invece salvare la memoria che evitano il crescere di nuovo in futuro.

Ultima idea: Per ogni decisione che prendete, si farà la tabella hash meglio per alcuni casi di utilizzo e peggio per altri. Se si sa come la vostra tabella hash sta per essere utilizzato, questo non sarà un problema. Eppure, se non lo fai, e di solito non lo fai, perché prendere queste decisioni da soli? Basta delegare. Permette all'utente di personalizzare il codice per tutti i piccoli dettagli, per esempio quanto per aumentare o ridurre, sia consentendo tutti questi fattori da impostare quando viene creata la vostra tabella hash o consentendo la vostra tabella hash di avere funzioni delegate (funzioni di callback che si può sempre chiedere quando incerto sul da farsi). In questo modo ogni utente del vostro codice può personalizzare il codice, anche in fase di esecuzione per qualsiasi scenario di utilizzo che lo richiedono.