¿Es posible implementar una tabla hash bien distribuida sin usar el operador%?

11

Estoy buscando implementar una tabla hash rápida y bien distribuida en C #. Tengo problemas para elegir mi función de restricción de hash que toma un código de hash arbitrario y lo "restringe" para que pueda usarse para indexar los cubos. Hay dos opciones que veo hasta ahora:

  • Por un lado, puede asegurarse de que sus cubos siempre tengan un número primo de elementos, y para restringir el hash, simplemente modúlelo por el número de cubos. Esto es, de hecho, lo que hace el Diccionario de .NET . El problema con este enfoque es que usar% es extremadamente lento en comparación con otras operaciones; Si observa las tablas de instrucciones de Agner Fog , idiv(que es el código de ensamblado que se genera para%) tiene una latencia de instrucción de ~ 25 ciclos para los procesadores Intel más nuevos. Compare esto con alrededor de 3 mul, o 1 para operaciones bit a bit como and, oro xor.

  • Por otro lado, puede hacer que el número de cubos sea siempre una potencia de 2. Todavía tendrá que calcular el módulo del hash para que no intente indexar fuera de la matriz, pero esta vez será menos costoso. . Dado que para potencias de 2 % Nes justo & (N - 1), la restricción se reduce a una operación de enmascaramiento que solo toma 1-2 ciclos. Esto lo hace sparsehash de Google . La desventaja de esto es que contamos con los usuarios para proporcionar buenos hashes; enmascarar el hash esencialmente corta parte del hash, por lo que ya no tomamos en cuenta todos los bits del hash. Si el hash del usuario está distribuido de manera desigual, por ejemplo, solo se completan los bits más altos o los bits más bajos son consistentemente iguales, entonces este enfoque tiene una tasa de colisiones mucho más alta.

Estoy buscando un algoritmo que pueda usar que tenga lo mejor de ambos mundos: toma en cuenta todos los bits del hash y también es más rápido que usar%. No necesariamente tiene que ser un módulo, solo algo que se garantiza que esté en el rango 0..N-1(donde N es la longitud de los cubos) y tiene una distribución uniforme para todas las ranuras. ¿Existe tal algoritmo?

Gracias por ayudar.

c# algorithms language-agnostic hashing James Ko
fuente
1
Busque el efecto de avalancha , así como la explicación en murmurhash3 (smhasher) . Sin embargo, el punto fundamental de su pregunta no se aborda adoptando una mejor función hash. En cambio, es una pregunta acerca de por qué los usuarios no adoptan la misma mejor función hash en primer lugar, y una solicitud de contramedidas (como si los usuarios fueran maliciosamente perezosos).
rwong
Una explicación gráfica y una demostración de avalancha
rwong
Para un módulo rápido (2^N +/- 1), consulte stackoverflow.com/questions/763137/…
rwong el
@rwong Lo siento, pero no estoy muy seguro de qué tiene que ver tu comentario con mi publicación. No controlo el hash proporcionado por el usuario, por lo que no estoy buscando una mejor función hash. Tampoco entiendo lo que quiere decir con "usuarios malintencionados perezosos".
James Ko
44
Si la función hash es deficiente, el implementador de la tabla hash no puede hacer nada para "arreglar" la distribución deficiente. Módulo un número primo no repara un hash pobre. Considere una función hash que produce como salida, múltiplos de un número primo. He visto tal problema en el código de producción real.
Frank Hileman

Respuestas:

9

Las implementaciones de tablas hash modernas no utilizan la función de módulo. A menudo usan la potencia de tablas de dos tamaños y cortan bits innecesarios. Una función hash ideal permitiría esto. El uso de módulos combinados con tamaños de tablas de números primos surgió en los días en que las funciones hash eran generalmente deficientes, ya que a menudo se encuentran en el desarrollo .net. Recomiendo leer sobre SipHash , una función hash moderna, luego leer sobre otras funciones modernas, como xxHash .

Debo explicar por qué las funciones hash de .net son a menudo deficientes En .net, los programadores a menudo se ven obligados a implementar funciones hash anulando GetHashcode. Pero .net no proporciona las herramientas necesarias para garantizar que las funciones creadas por el programador sean de alta calidad, a saber:

  • encapsulación del estado hash en una estructura o clase
  • funciones "agregar" hash, que agregan nuevos datos al estado hash (agregue una matriz de bytes, o un doble, por ejemplo)
  • una función hash "finalizar" para producir la avalancha
  • encapsulación del resultado hash: en .net tiene una opción, un entero con signo de 32 bits.

Para obtener más información sobre el uso de un resultado de función hash como índice de tabla hash, consulte las definiciones de formas universales de hashing en este documento: Hash universal más rápido de 64 bits usando multiplicaciones sin acarreo

Frank Hileman
fuente
3

Para usar AND mientras mantiene todos los bits, use XOR también.

Por ejemplo temp = (hash & 0xFFFF) ^ ( hash >> 16); index = (temp & 0xFF) ^ (temp >> 8);,.

Para este ejemplo, no hay módulo y los 32 bits de hashefecto son de 8 bits index. Sin embargo, si es o no más rápido que el DIV es algo que depende de demasiados factores, y puede ser más lento que el DIV en algunos casos (por ejemplo, hash grande e índice pequeño).

Brendan
fuente
Esto siempre será más rápido que DIV / IDIV, sin embargo, no creo que responda a mi pregunta index, estará en el rango [0..255]. Necesito algo en el rango [0..n-1], donde nestá el número de cubos.
James Ko
@JamesKo Pero si está implementando un diccionario, también controla el número de depósitos (hasta cierto punto). Entonces, en lugar de números primos, puedes elegir potencias de dos. (Si hacerlo sería realmente una buena idea, no puedo decírtelo.)
svick
@svick Para potencias de 2 podríamos hacer una simple operación de máscara. Como se mencionó en la pregunta, estoy buscando una forma barata de hacer esto con números primos para que incluso los hashes mal distribuidos sean acomodados.
James Ko
1

Puede aprovechar el hecho de que muchos enteros primos tienen un inverso multiplicativo modular. Ver este artículo . Ha satisfecho una de las restricciones al hacer que su índice de cubeta sea primo y el módulo 2 ^ n, que son intrínsecamente primos.

El artículo describe el algoritmo para encontrar un número tal que multiplicar por ese número e ignorar el desbordamiento producirá el mismo resultado que si se hubiera dividido por el tamaño del índice del depósito.

BobDalgleish
fuente