Elegir un tamaño de tabla adecuado para un hash

Question

Si tengo un conjunto de claves de 1000, ¿cuál es el tamaño adecuado para mi tabla Hash y cómo se determina?

Answer 1

Depende del factor de carga (el punto porcentual lleno donde la tabla aumentará su tamaño y redistribuirá sus elementos). Si sabe que tiene exactamente 1000 entradas, y ese número nunca cambiará, puede establecer el factor de carga en 1.0 y el tamaño inicial en 1000 para obtener la máxima eficiencia. Si no estaba seguro del tamaño exacto, podría dejar el factor de carga en su valor predeterminado de 0.75 y establecer su tamaño inicial en 1334 (tamaño esperado / LF) para realmente buen rendimiento, a un costo de memoria extra.

Puede usar el siguiente constructor para establecer el factor de carga:

Hashtable(int initialCapacity, float loadFactor) 

Answer 2

También debe tener en cuenta la función hash.

una regla general sugiere que el tamaño de la mesa sea aproximadamente el doble, de modo que haya espacio para expandirse y, con suerte, mantener el número de colisiones pequeño.

Otra regla general es suponer que está haciendo algún tipo de hashing relacionado con el módulo, luego redondee el tamaño de su tabla al siguiente número primo más grande y use ese número primo como valor del módulo.

¿Qué tipo de cosas estás haciendo hash? Más detalles deberían generar mejores consejos.

Answer 3

Hay una discusión sobre estos factores en la documentación de Hashtable

Answer 4

Déjalo crecer. Con este tamaño, el manejo automático está bien. Aparte de eso, 2 x size + 1 es una fórmula simple. Los números primos también son buenos, pero tan pronto como su conjunto de datos alcance un cierto tamaño, la implementación de hash podría decidir volver a mostrar y hacer crecer la tabla.

Sus claves están impulsando la efectividad y es de esperar que sean lo suficientemente distintas.

Conclusión: haga la pregunta de tamaño cuando tenga problemas como el tamaño o el rendimiento lento, aparte de eso: ¡No se preocupe!

Answer 5

Dos veces es bueno.

No tienes un gran conjunto de teclas. No te preocupes por las discusiones difíciles sobre tu implementación de HashTable, y ve por 2000.

Answer 6

Me gustaría reiterar lo que https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany dijo anteriormente. 1000 no me parece un gran hash. He estado usando muchas tablas hash sobre ese tamaño en Java sin ver muchos problemas de rendimiento. Y casi nunca me molesto con el tamaño o el factor de carga.

Si ha ejecutado un generador de perfiles en su código y ha determinado que la tabla hash es su problema, entonces comience a ajustar. De lo contrario, no asumiría que tienes un problema hasta que estés seguro.

Después de todo, en la mayoría de los códigos, el problema de rendimiento no está donde crees que está. Intento no anticiparme.