que - tabla hash implementacion

función hash perfecta

Question

Estoy intentando descifrar los valores

10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0

Necesito una función que los asigne a una matriz que tenga un tamaño de 13 sin causar colisiones.

He pasado varias horas pensando en esto y buscando en Google y no puedo resolver esto. No me he acercado a una solución viable.

¿Cómo me gustaría encontrar una función hash de este tipo? He jugado con gperf, pero realmente no lo entiendo y no pude obtener los resultados que estaba buscando.

Answer 1

Encontré uno

Probé algunas cosas y encontré una semi-manualmente:

(n ^ 28) % 13

La parte semi-manual fue la siguiente secuencia de comandos de ruby ​​que usé para probar funciones candidatas con un rango de parámetros:

t = [10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0]
(1..200).each do |i|
  t2 = t.map { |e| (e ^ i) % 13 }
  puts i if t2.uniq.length == t.length
end

Answer 2

Bob Jenkins también tiene un programa para esto: http://burtleburtle.net/bob/hash/perfect.html

A menos que tenga mucha suerte, no hay una función hash perfecta "agradable" para un conjunto de datos determinado. Los algoritmos de hashing perfecto usualmente usan una función de hashing simple en las teclas (usando suficientes bits para que no tenga colisiones) y luego usan una tabla para finalizarla.

Answer 3

En algunas plataformas (por ejemplo, incrustadas), la operación de módulo es costosa, por lo que es mejor evitar % 13 . Pero la operación AND de bits de orden inferior es barata y equivalente a un módulo de una potencia de 2.

Intenté escribir un programa simple (en Python) para buscar un hash perfecto de tus 11 puntos de datos, usando formas simples como ((x << a) ^ (x << b)) & 0xF (donde & 0xF es equivalente a % 16 , dando un resultado en el rango 0..15, por ejemplo). Pude encontrar el siguiente hash sin colisiones que proporciona un índice en el rango 0..15 (expresado como una macro C):

#define HASH(x)    ((((x) << 2) ^ ((x) >> 2)) & 0xF)

Aquí está el programa de Python que utilicé:

data = [ 10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0 ]

def shift_right(value, shift_value):
    """Shift right that allows for negative values, which shift left
    (Python shift operator doesn''t allow negative shift values)"""
    if shift_value == None:
        return 0
    if shift_value < 0:
        return value << (-shift_value)
    else:
        return value >> shift_value

def find_hash():
    def hashf(val, i, j = None, k = None):
        return (shift_right(val, i) ^ shift_right(val, j) ^ shift_right(val, k)) & 0xF

    for i in xrange(-7, 8):
        for j in xrange(i, 8):
            #for k in xrange(j, 8):
                #j = None
                k = None
                outputs = set()
                for val in data:
                    hash_val = hashf(val, i, j, k)
                    if hash_val >= 13:
                        pass
                        #break
                    if hash_val in outputs:
                        break
                    else:
                        outputs.add(hash_val)
                else:
                    print i, j, k, outputs

if __name__ == ''__main__'':
    find_hash()

Answer 4

Hice una comprobación rápida y usé la función hash SHA256 y luego la división modular por 13 funcionó cuando la probé en Mathematica. Para c ++ esta función debe estar en la biblioteca openssl. Ver este post

Sin embargo, si estuvieras haciendo un montón de hash y búsquedas, la división modular es una operación bastante costosa para hacer repetidamente. Hay otra forma de asignar una función hash de n bits a los índices i-bit. Vea esta post de Michael Mitzenmacher sobre cómo hacerlo con una operación de cambio de turno en C. Espero que eso ayude.

Answer 5

Intente lo siguiente, que asigna sus n valores a índices únicos entre 0 y 12 (1369% (n + 1))% 13

Answer 6

Sólo algunas divagaciones casi analíticas:

En tu conjunto de números, once en total, tres son impares y ocho son pares. Mirar las formas más simples de hash -% 13 - le dará los siguientes valores de hash: 10 - 3, 100 - 9, 32 - 6, 45 - 6, 58 - 6, 126 - 9, 3 - 3, 29 - 3 , 200 - 5, 400 - 10, 0 - 0

Lo cual, por supuesto, es inutilizable debido al número de colisiones. Se necesita algo más elaborado.

¿Por qué decir lo obvio? Teniendo en cuenta que los números son tan pocos, cualquier algoritmo elaborado, o mejor dicho, "menos simple", probablemente será más lento que la instrucción de cambio o (lo que prefiero) simplemente buscar en un vector de tamaño corto / largo sin signo de once posiciones y usar el índice del partido.

¿Por qué utilizar una búsqueda de vectores?

1. Puede ajustarlo ajustando los valores que aparecen con más frecuencia hacia el principio del vector.
2. Supongo que el propósito es conectar el índice hash en un conmutador con una numeración agradable y secuencial. En ese sentido, parece inútil utilizar primero un interruptor para encontrar el índice y luego conectarlo a otro interruptor. ¿Quizás deberías considerar no usar hash e ir directamente al interruptor final?
3. La versión del interruptor de hashing no se puede ajustar con precisión y, debido a los valores muy diferentes, hará que el compilador genere un árbol de búsqueda binario que dará como resultado muchas comparaciones y saltos condicionales / de otro tipo (especialmente costosos) que llevan tiempo ( He asumido que ha recurrido al hash por su velocidad y requiere espacio.
4. Si desea acelerar la búsqueda vectorial adicionalmente y está utilizando un sistema x86, puede implementar una búsqueda vectorial basada en las instrucciones del ensamblador repne scasw (corto) / repne scasd (largo) que será mucho más rápido. Después de un tiempo de configuración de unas pocas instrucciones, encontrará la primera entrada en una instrucción y la última en once seguido de una limpieza de algunas instrucciones. Esto significa 5-10 instrucciones, mejor caso y 15-20 peor. Esto debería vencer al hash basado en el interruptor en todos, pero quizás en uno o dos casos.

Answer 7

Si conoces las claves exactas, es trivial producir una función hash perfecta:

int hash (int n) {
  switch (n) {
    case 10:   return 0;
    case 100:  return 1;
    case 32:   return 2;
    // ...
    default:   return -1;
  }
}