¿Tiene sentido para cambiar el tamaño de una tabla hash abajo? ¿Y cuando?

Question

Mi aplicación tabla hash tiene una función para cambiar el tamaño de la mesa cuando los alcances de carga cerca de 70%. Mi tabla hash se implementa con encadenamiento separado para las colisiones.

¿Tiene sentido que debería cambiar el tamaño de la tabla de dispersión hacia abajo en cualquier punto o debería simplemente dejar las cosas como son? De lo contrario, si aumento el tamaño (por casi el doble, de hecho sigo esto: http://planetmath.org /encyclopedia/GoodHashTablePrimes.html ) cuando la carga es del 70%, debería cambiar su tamaño abajo cuando la carga llega al 30% o por debajo?

Answer 1

¿Estás escribiendo la tabla hash para uso general, o hay un propósito específico para ello? Sugiero no cambiar el tamaño más pequeño para una implementación general. Esto mantendrá su sencilla mesa y evitar que se golear memoria en condiciones en que la mesa se llena y se vacía a menudo. Si al final de correr en una condición en la que las necesidades de la tabla hash para ser reducidos en tamaño, extenderlo en ese punto en el tiempo.

Answer 2

Las tablas hash no tiene que tener longitudes de número primo si usted tiene una función hash de buena calidad (ver aquí ). Puedes hacer que las potencias de dos, lo que acelera considerablemente hasta cálculos de índice.

¿Por qué es relevante para la cuestión? Porque cuando se encoge una tabla hash de potencias de dos, puede dejar todas las entradas en la parte baja donde están y simplemente añadir la lista enlazada en i ranura (desde la mitad superior) en la lista enlazada en i - n/2 ranura.

Answer 3

Si la memoria no es barato, no lo toque. Si la memoria no es caro, cambiar el tamaño de la histéresis como usted ha sugerido. Cuando haya terminado, el resultado de perfil para asegurarse de que funciona bien y tener algo no se hace tonta.

Answer 4

Primera idea: La única razón para el cultivo de una tabla hash se debe a que el rendimiento disminuye tabla hash si hay demasiadas colisiones. El crecimiento de la mesa cuando su carga sea superior al 70% es una buena regla del pulgar para evitar que esto suceda, pero es sólo una regla del pulgar. Mucho mejor es mantener un registro del número de colisiones y sólo crecerá la tabla hash si superan un cierto límite o una vez que se alcanzó una cierta relación de colisión. Después de todo, ¿por qué quiere hacer crecer una tabla hash que se carga en un 90%, aún no tiene una sola colisión? Se tendría ninguna ventaja.

Segunda idea: La única razón para reducir una tabla hash es para ahorrar memoria, sin embargo, la contracción que podría aumentar el número de colisiones y por lo tanto disminuir el rendimiento de la búsqueda. Esta es una velocidad clásica vs el comercio de memoria fuera y por qué debe resolverlo por sí mismo? Dejar en manos de quien esté utilizando su código. Simplemente nunca contraerá por su cuenta, pero ofrecen un método de contracción. Si bajo uso de memoria es un requisito, el que está utilizando su código puede llamar encoge con regularidad. Si el máximo rendimiento si un requisito, el que está utilizando su código nunca debe llamar a encoger. Todos los demás pueden utilizar algún tipo de heurística para decidir si y cuándo llamar al psiquiatra.

Tercera idea: Cuando está creciendo o disminuyendo, siempre creciendo / reducir el tamaño de tal manera que después de la operación se garantiza un cierto factor de carga. P.ej. cuando en crecimiento, siempre crecer para que después el factor de carga es de 50% y cuando la contracción, siempre reducir el tamaño de tal manera que después el factor de carga es 70%. Por supuesto, eso no dice nada sobre el número de colisiones, por lo que añadir un elemento inmediatamente después de crecer / reducción puede hacer que la tabla hash a crecer de nuevo, pero que es inevitable, ya que simula el efecto de un cultivo / contracción suele ser demasiado caro. También reducirá a menudo se llama una vez que no hay otras modificaciones son cepilladas, por lo que debe y no guardar la memoria de evitar tener que volver a crecer en el futuro.

última idea: Para cada decisión que tomas, que hará que la tabla hash mejor para algunos casos de uso y peor para otros. Si sabe cómo se va a utilizar su tabla hash, esto no será un problema. Sin embargo, si no lo hace, y por lo general no es así, ¿por qué tomar estas decisiones por sí mismo? Sólo delegarlas. Permitir al usuario de su código de personalizar todos los pequeños detalles, por ejemplo, cuánto para aumentar o reducir, ya sea permitiendo que todos estos factores que pueden establecer cuando se crea su tabla hash o permitiendo su tabla hash para tener delegar funciones (funciones de devolución que se puede pedir siempre que no sabe qué hacer). De esta manera todos los usuarios de su código puede personalizar su código, incluso en tiempo de ejecución para cualquier escenario de uso que lo requieran.