9
Si tengo un juego de claves de 1000, ¿cuál es el tamaño adecuado para mi tabla hash y cómo se determina?Elección de un tamaño de tabla adecuado para un hash
A
Respuesta
9
Depende del factor de carga (el punto "por ciento 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 una máxima eficiencia. Si no estaba seguro del tamaño exacto, puede 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.
se puede utilizar el siguiente constructor para establecer el factor de carga:
Hashtable(int initialCapacity, float loadFactor)
1
3
Es necesario tener en cuenta la función hash también.
una regla de oro sugiere que el tamaño de la tabla sea aproximadamente el doble, de modo que haya espacio para expandirse y, con suerte, mantener pequeñas las colisiones.
Otra regla general es suponer que está realizando un tipo de hash 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 el valor del módulo.
¿Qué tipo de cosas has hecho? Más detalles deberían generar mejores consejos.
0
Dos veces es bueno.
No tiene un gran conjunto de claves. No se moleste en discusiones difíciles sobre su implementación de HashTable, y vaya para 2000.
+0
2000 no tiene un buen tamaño, porque no es excelente. 2001 sería bueno, no es primordial, pero al menos ni siquiera. Distribuirá las claves en la mesa mucho mejor. Una buena tabla hash se encargará de una buena función hash, pero la mayoría de las veces se usa el tamaño. – ReneS
+0
Esta es una pregunta interesante. Su afirmación es correcta si usa una clave hash de tipo: H (s) = s [0] + b * s [1] + b^2s [2] + ... [N] Creo que el estándar de la industria actual es para usar 2^k como tamaño y mejores funciones hash como Jenkins. La última vez que verifiqué que el estándar estaba funcionando con excelente, sin embargo. – fulmicoton
+0
Los números primos e impares son más fríos;) – ReneS
1
Déjelo crecer. Con este tamaño, el manejo automático está bien. Aparte de eso, 2 x tamaño + 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 generar y hacer crecer la tabla.
Sus claves están impulsando la efectividad y son lo suficientemente claras.
En pocas palabras: Haga la pregunta sobre el tamaño cuando tenga problemas tales como el tamaño o el rendimiento lento, aparte de eso: ¡No se preocupe!
+0
Preocúpese si el rendimiento * en esta área * se convierte en un problema. Si intenta manejarlo por adelantado, es más probable que inserte un error o simplemente tenga un código innecesariamente complejo que puede causar un problema de mantenimiento. –
+0
Estoy de acuerdo. Primero tenga el problema y busque una solución después. – ReneS
0
Me gustaría reiterar lo que https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany dijo anteriormente. 1000 no parece ser un gran hash para mí. He estado usando muchas tablas hash de ese tamaño en Java sin ver mucho en cuanto a problemas de rendimiento. Y casi nunca pierdo el tamaño o el factor de carga.
Si ejecutó un generador de perfiles en su código y determinó que la tabla hash es su problema, entonces sin dudas 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 usted cree que está. Intento no anticiparme.
Cuestiones relacionadas
- 1. Elección de un multiplicador para una función de hash (cadena)
- 2. Implementación de tabla hash
- 3. cuándo cambiar el tamaño de una tabla hash?
- 4. Elección de un idioma intermedio
- 5. Algoritmo de hash para la implementación de la tabla hash
- 6. ¿Cómo implementar una tabla hash de tamaño dinámico?
- 7. Tamaño de memoria de un hash u otro objeto?
- 8. Tabla hash persistente para programas de Ruby?
- 9. problemas para volver tabla hash
- 10. Tabla hash: ¿por qué el tamaño debe ser primordial?
- 11. hash de tamaño de cadena
- 12. SQL espacial: ¿tipo de datos más adecuado para un cuadrado?
- 13. ¿Usando una tabla hash dentro de un Parallel.ForEach?
- 14. Es adecuado para un desarrollador sin servidor
- 15. Diseño de tabla hash Python
- 16. Creando un campo de elección dinámica
- 17. contenedor de diccionario/mapa/árbol/hash adecuado en Flex
- 18. clave Adecuado para NSDictionary
- 19. ¿Qué algoritmos están disponibles para cambiar el tamaño de una tabla hash?
- 20. ¿Tiene una buena función hash para una tabla hash C++?
- 21. Construyendo una función hash/tabla hash
- 22. ¿Función hash para un par de largo?
- 23. Conversión de un hash en un hash anidado
- 24. ¿C# es adecuado para un lenguaje de scripting?
- 25. ¿Hay un lugar adecuado para una base de datos provisional?
- 26. ¿Es un administrador de contexto adecuado para este trabajo?
- 27. ¿Cómo obtener la clave de la tabla hash que tiene un valor específico?
- 28. Conversión de un hash anidado en un hash plano
- 29. ¿Es un diccionario de Python un ejemplo de una tabla hash?
- 30. tabla hash en JavaScript
Suponiendo que la función hash se comporta bien en el conjunto de claves esperadas. Una función hash casera puede no comportarse bien en una mesa de tamaño mínimo. Para una función casera, tendrías que ejecutar experimentos. –
Si la función hash no se comporta bien, los elementos colisionantes se almacenarán en el mismo contenedor (en una lista vinculada). La mesa con un tamaño mínimo no tendrá ningún efecto en el rendimiento. –