7
Conozco el principio básico de la estructura de datos de la tabla hash. Si tengo una tabla hash de tamaño N, tengo que distribuir mis datos en estos N tan poco como sea posible.¿Cómo implementar una tabla hash de tamaño dinámico?
Pero en realidad, la mayoría de los idiomas tienen sus tipos de tablas hash integradas. Cuando los uso, no necesito saber el tamaño de la tabla hash de antemano. Simplemente pongo todo lo que quiero en eso. Por ejemplo, en Ruby:
h = {}
10000000.times{ |i| h[i]=rand(10000) }
¿Cómo puede hacer esto?
un buen enfoque de reposición es doblar el tamaño de la tabla, y luego cuando busca un valor, tiene su clave, y realiza una búsqueda modulu en su tabla hash comenzando con 'hash% current_size', luego' hash % current_size/2', etc. Cuando encuentre el valor, puede volver a generarlo. De esta forma, puede realizar un reinicio lento sin perder demasiado rendimiento, ya que los valores accedidos comúnmente se actualizan automáticamente. –
@DvirVolk, lazy rehash es agradable. Ya conoce la entrada en la tabla hash más alta y sabe dónde insertar las tablas hash inferiores. Pero es posible que tenga una situación en la que una entrada contenga toda la tabla de cubos vacíos. Ese "cambio de tamaño incremental" de wiki es una solución de velocidad de tradoff para el tamaño de datos, según entiendo (finalmente tienes 2 * N cubetas donde N es el tamaño de la tabla hash más alta). El tamaño de duplicación es bueno para "copiar todas las entradas" por el hecho de que tiene que dividir cubos individuales en dos o combinar dos en uno (sin recálculo de hash) con la reutilización de listas enlazadas de cubetas antiguas. – ony