metodos - hashtable keys c#

Matriz de enteros hash

Question

Estoy usando un conjunto de hash en el que almaceno una matriz de enteros (32 bits). Esto significa que necesito un algoritmo para hash una matriz de enteros. Estoy buscando un hash entero de 32 bits (C # int).

He intentado y editado dos algoritmos existentes, en los que puede ver las cuatro versiones de abajo, incluido su punto de referencia.

Mis preguntas son las siguientes:

1. ¿Crees que el algoritmo inferior es bueno para este propósito?

2. ¿Hay un mejor algoritmo disponible para este propósito?

Información del programa

• Normalmente, una matriz tiene 16 entries y los enteros son smaller than 10 , aunque ambos deben admitir valores más grandes. Podría decir que los valores más grandes que tienen alguna posibilidad de ocurrir son 200 entradas y enteros de valor 20.
• Estoy usando el HashSet en un algoritmo de búsqueda de primer aliento, para comparar si dos nodos son iguales. http://en.wikipedia.org/wiki/Breadth-first_search .
• Para este programa específico no puedo usar código inseguro.

Puntos de referencia y código

a continuación están mis puntos de referencia y mi código, del peor al mejor desempeño en mi programa.

• Coordinates2D es una estructura que contiene un int x y un int y.
• El total de entradas en el HashSet al final de ejecución es 356525
• No pude recuperar el número de colisiones exactamente. El número dado es la cantidad de veces que se comparó un objeto y no fue igual (mismo hash, objeto diferente). Sin embargo, esto ocurre muchas veces entre los mismos objetos. Este valor varía un poco por ejecución, ya que el programa es multiproceso.
• La semilla MurMurHash3 es semilla const uint seed = 144

MurMurHash3 utilizando bytes recuperados de las coordenadas directamente

El código es igual a https://gist.github.com/automatonic/3725443 La matriz de bytes se recupera usando el siguiente código:

int size = Marshal.SizeOf(typeof(Coordinates2D));
int length = carCoords.Length;
Byte[] bytes = new Byte[size * length];
for (int i = 0; i < length; ++i)
{
    GCHandle pinStructure = GCHandle.Alloc(carCoords[i], GCHandleType.Pinned);
    Marshal.Copy(pinStructure.AddrOfPinnedObject(), bytes, i*size, size);
    pinStructure.Free();
}

// Hash the byte array
return MurMurHash3.Hash(new System.IO.MemoryStream(bytes));

Esto es increíblemente ineficiente, debido a la copia.

• Rendimiento: 40880ms
• Colisiones: <84

MurMurHash3 utilizando bytes recuperados de los enteros en los objetos

public static int Hash2(RushHourPathLengthNode.Coordinates2D[] coords)
{
    const uint c1 = 0xcc9e2d51;
    const uint c2 = 0x1b873593;

    uint h1 = seed;
    uint k1 = 0;
    uint streamLength = (uint)coords.Length * 2;

    for (int i = 0, l = coords.Length; i < l; ++i)
    {
        // Do it for X
        byte[] chunk = BitConverter.GetBytes(coords[i].x);

        /* Get four bytes from the input into an uint */
        k1 = (uint)
           (chunk[0]
          | chunk[1] << 8
          | chunk[2] << 16
          | chunk[3] << 24);

        /* bitmagic hash */
        k1 *= c1;
        k1 = rotl32(k1, 15);
        k1 *= c2;

        h1 ^= k1;
        h1 = rotl32(h1, 13);
        h1 = h1 * 5 + 0xe6546b64;


        // Do it for y
        chunk = BitConverter.GetBytes(coords[i].y);

        /* Get four bytes from the input into an uint */
        k1 = (uint)
           (chunk[0]
          | chunk[1] << 8
          | chunk[2] << 16
          | chunk[3] << 24);

        /* bitmagic hash */
        k1 *= c1;
        k1 = rotl32(k1, 15);
        k1 *= c2;

        h1 ^= k1;
        h1 = rotl32(h1, 13);
        h1 = h1 * 5 + 0xe6546b64;
    }

    // finalization, magic chants to wrap it all up
    h1 ^= streamLength;
    h1 = fmix(h1);

    unchecked //ignore overflow
    {
        return (int)h1;
    }
}

Esto es mucho más eficiente ahora que la copia se ha ido.

• Rendimiento: 16640ms
• Colisiones: <92

MurMurHash3 usando números enteros

public static int Hash(RushHourPathLengthNode.Coordinates2D[] coords)
{
    const uint c1 = 0xcc9e2d51;
    const uint c2 = 0x1b873593;

    uint h1 = seed;
    uint k1 = 0;
    uint streamLength = (uint)coords.Length * 2;

    for (int i = 0, l = coords.Length; i < l; ++i)
    {
        k1 = (uint)coords[i].x;

        //bitmagic hash
        k1 *= c1;
        k1 = rotl32(k1, 15);
        k1 *= c2;

        h1 ^= k1;
        h1 = rotl32(h1, 13);
        h1 = h1 * 5 + 0xe6546b64;

        k1 = (uint)coords[i].y;

        //bitmagic hash
        k1 *= c1;
        k1 = rotl32(k1, 15);
        k1 *= c2;

        h1 ^= k1;
        h1 = rotl32(h1, 13);
        h1 = h1 * 5 + 0xe6546b64;
    }

    // finalization, magic chants to wrap it all up
    h1 ^= streamLength;
    h1 = fmix(h1);

    unchecked //ignore overflow
    {
        return (int)h1;
    }
}

• Rendimiento: 13027 ms
• Colisiones: <95

Hash usando multiplicación de suma entera

int hash = 17;
for (int i = 0, l = carCoords.Length; i < l; ++i)
{
    hash = hash * 31 + carCoords[i].x;
    hash = hash * 31 + carCoords[i].y;
}
return hash;

• Rendimiento: 4564ms
• Colisiones: <44

Como ve, este es mucho más eficiente. Funciona bien con cualquier número primo. Según entiendo, no hay ninguna prueba científica de que esto funcione, lo cual no me agrada demasiado.

Según Michal B., una versión más rápida usaría el cambio de bits. Sin embargo, las pruebas muestran que esto no es un hash exitoso. El problema lleva mucho más tiempo para ejecutarse (no finalizó en 5 minutos). El cambio de bits podría ser bueno, pero parece que el 31 (número primo) es crucial.

int hash = 17;
for (int i = 0, l = carCoords.Length; i < l; ++i)
{
    hash = hash << 5 - carCoords[i].x;
    hash = hash << 5 - carCoords[i].y;
}
return hash;

Answer 1

¿Has considerado usar una curva de relleno de espacio para generar el hash? Esto minimizará (o eliminará) las colisiones para la resolución elegida (maxX, maxY)

Aquí hay dos preguntas SO y sus respuestas que usan este método.

1. Asignación de valor N-dimensional a un punto en la curva de Hilbert
2. Calcule el valor de Hilbert de un punto para usar en un Hilbert R-Tree?

¡Espero que esto ayude!

Answer 2

Al final fui con el último algoritmo.

int hash = 17;
for (int i = 0, l = carCoords.Length; i < l; ++i)
{
    hash = hash * 19 + carCoords[i].x;
    hash = hash * 19 + carCoords[i].y;
}
return hash;

Esto es muy rápido de calcular, y para los números (pequeños) que estoy usando el hash es increíble.

Si vas a usar esto, asegúrate de que los números que usas sean números primos. Debido a esto, no puedes usar el cambio de bits para optimizarlo.