7
Conosco il principio di base della struttura dati della tabella hash. Se ho una tabella hash di dimensione N, devo distribuire i miei dati in questi N bucket nel modo più uniforme possibile.Come implementare una tabella hash di dimensioni dinamiche?
Ma in realtà, la maggior parte delle lingue ha i tipi di tabella hash incorporati. Quando li uso, non ho bisogno di conoscere la dimensione della tabella hash in anticipo. Ho appena messo tutto ciò che voglio. Ad esempio, in Ruby:
h = {}
10000000.times{ |i| h[i]=rand(10000) }
Come può farlo?
un buon approccio di rilocalizzazione è raddoppiare la dimensione della tabella, e quindi quando si cerca un valore, si ha la sua chiave e si esegue una ricerca modulu nella tabella hash che inizia con "hash% current_size', quindi" hash " % current_size/2', ecc. Quando trovi il valore, puoi riutilizzarlo. In questo modo puoi eseguire il pigro rifacimento senza perdere troppe prestazioni, perché i valori comunemente raggiunti vengono rehashed automaticamente. –
@DavirVolk, pigro rehash è bello. Conoscete già la voce nella tabella di hash più in alto e sapete dove inserirvi dalle tabelle hash più basse. Ma potresti avere una situazione in cui qualche voce manterrà l'intera tabella di secchi vuoti. Quel "ridimensionamento incrementale" da wiki è la soluzione della velocità tradoff per la dimensione dei dati, come ho capito (finalmente si detengono 2 * N bucket in cui N è la dimensione della tabella hash più in alto). La dimensione del raddoppio è buona per "copiare tutte le voci" in base al fatto che è necessario dividere singoli bucket in due o unire due in uno (senza ricalcolo hash) con il riutilizzo di elenchi collegati di vecchi bucket. – ony