hash de 16 bits eficiente [cerrado]

Question

hash de 16 bits eficiente [cerrado]

#1 de Martin Trigaux (3 votos)

-5

Estoy buscando una manera de hacer un ID de 16 bits de aproximadamente 100 bits de datos. La solución debe ser fácil de implementar, o ya debería estar implementada en c ++, debe ser rápida de evaluar, y lo más importante es que los valores de la ID deben distribuirse de manera uniforme, lo que quiere decir que un valor no debe tener una mayor probabilidad de ser implementado. tomado de otro.

hash

pregunta bob 19.06.2012 - 09:33

fuente

1 respuesta

Lea otras preguntas en las etiquetas hash

¿Diferencia entre phpp, php y phP? [cerrado] ¿Cómo puedo acceder a un ec2-xx-xx-xx-xx.us-west-2.compute.amazonaws.com? este enlace no se abrirá en mi navegador: [cerrado]

score 3 · Accepted Answer

Como se mencionó en la pregunta Rook link, 16bits es muy muy débil, reduciendo 100 bits a 16 lleva a ~ 6 posibles colisiones por hash.

¿Estás seguro de que necesitas un hash para eso? 16 bits es suficiente para ser almacenado en un entero y simplemente podría incrementarse si solo necesita una forma de identificar un objeto (limitado a 65536).

Si, sin embargo, desea utilizar una función hash, puede intentar usar algo muy simple como hash de Pearson que producirá un hash de 8 bits.

h := 0
for each c in C loop
  index := h xor c
  h := T[index]
end loop
return h

Cito Wikipedia, las ventajas de esta función son:

Es extremadamente simple.
Se ejecuta rápidamente en procesadores de recursos limitados.
No hay una clase simple de entradas para las cuales las colisiones (salidas idénticas) sean especialmente probables.
Dado un pequeño conjunto de entradas privilegiadas (por ejemplo, palabras reservadas para un compilador), la tabla de permutación se puede ajustar para que esas entradas produzcan valores hash distintos, produciendo lo que se llama una función hash perfecta.

La adaptación a 16bits no debería ser demasiado difícil. Por ejemplo, esta página da un ejemplo de adaptación, pero creo que el autor olvidó cambiar el tamaño de la tabla a 65535, el código sería:

static unsigned short T[] = {
    // The values 0..65535 shuffled into random order.
};

static inline unsigned hashOf(unsigned h,const char* s) {
    for (int c = *s++; c; c = *s++) {
        h = T[h ^ (65535 & c)];
    }
    return h;
}