c# - values - hashtable using
Hashtables(diccionario, etc.) con claves enteras (3)
He estado desconcertando sobre esto por unos días ... siéntete libre de derribar cualquiera de mis suposiciones.
Estamos usando un diccionario con claves enteras. Supongo que el valor de la clave en este caso se usa directamente como hash. ¿Significa esto (si las claves están agrupadas en un rango pequeño) que la distribución de la clave hash (igual que la clave misma, ¿verdad?) Estará en un rango similar y, por lo tanto, ¿una mala elección para una tabla hash?
¿Sería mejor proporcionar un IEqualityComparer que hiciera algo inteligente con números primos y módulo matemático para calcular un hash mejor distribuido?
Antes de hacer algo inteligente, probaría la velocidad del mismo tal como está y veré si es adecuado para ti. Si no es así, entonces intente lo inteligente. Pero esperaría que fuera mejor dejarlo en paz; es más importante que los hashes no colisionen, y mientras eso esté sucediendo, la vida estará bien.
Suponiendo que está utilizando una implementación de tabla hash de biblioteca estándar, es probable que la clave no sea el hash, incluso si la clave es un número entero, exactamente por la razón que señala.
Entonces, aunque su lógica con respecto a las distribuciones hash es correcta, su suposición inicial de que las claves enteras significarían que hashes = keys probablemente no lo es.
Si me equivoco re: .NET entonces bueno; esto es más de una respuesta generalizada. :)
No se usa directamente porque el diccionario aún pedirá la clave para su hash, pero el valor hash de un Int32 es solo el valor, por lo que el empuje de su pregunta es relevante, sí.
Creo que la forma en que funciona el diccionario .NET no depende de que los valores hash se distribuyan uniformemente. Toma hash % bucketCount donde bucketCount siempre es primo. (Eso es de memoria, podría estar equivocado).
De todos modos, podrías terminar con un conjunto ineficiente de claves, si están espaciadas por el recuento de cubos. Sin embargo, ese siempre será el caso: una tabla hash solo sería genuinamente O (1) para todas las claves si tuvieran valores hash únicos y la tabla mantuviera un conjunto de cubos para cada posible hash :) En realidad, tiende a no ser un problema. Si usted sabe que será un problema, entonces sí, un IEqualityComparer<T> podría ayudar.