comprensión del código hash

Question

función hash es importante en la implementación de la tabla hash. Sé que en Java Objeto tiene su código hash, que podría generarse a partir de la función de hash débil.

A continuación se presenta un fragmento que es "función hash suplemento"

static int hash(Object x) { 
    int h = x.hashCode(); 

    h += ~(h << 9); 
    h ^= (h >>> 14); 
    h += (h << 4); 
    h ^= (h >>> 10); 
    return h; 
} 

nadie puede ayudar a explicar lo que es la idea fundamental de un algoritmo de hash ? generar un entero no duplicado? Si es así, ¿cómo lo hacen estas operaciones bit a bit ?

Answer 1

Lo que normalmente está tratando de hacer con un algoritmo hash es convertir una gran clave de búsqueda en un pequeño número no negativo, para buscar un registro asociado en una tabla y hacerlo más rápido que M log2 N (donde M es el costo de una "comparación" y N es el número de elementos en la "tabla") típico de una búsqueda binaria (o búsqueda en árbol).

Si tiene la suerte de tener un hash perfecto, sabrá que cualquier elemento de su conjunto de claves (conocido!) Se reducirá a un valor único y diferente. Los hashes perfectos son principalmente de interés para cosas como los compiladores que necesitan buscar palabras clave en el lenguaje.

En el mundo real, tiene valores hash imperfectos, donde varias teclas son todas hash con el mismo valor. Está bien: ahora solo tiene que comparar la clave con un pequeño conjunto de coincidencias candidatas (las que tienen un valor de ese valor), en lugar de un conjunto grande (la tabla completa). Los pequeños conjuntos se llaman tradicionalmente "cubos". Utiliza el algoritmo hash para seleccionar un segmento, luego utiliza otra estructura de datos de búsqueda para los propios contenedores. (Si la cantidad de elementos en un depósito es conocida o se espera con seguridad que sea realmente pequeña, la búsqueda lineal no es irracional. Los árboles de búsqueda binaria también son razonables.)

Las operaciones bit a bit en su ejemplo se parecen mucho a registro de cambio de análisis de firma, que intenta comprimir un patrón de bits único y largo en un patrón corto, aún único.

Answer 2

Una función hash es cualquier procedimiento bien definido o función matemática que convierte una gran cantidad de datos, posiblemente de tamaño variable, en un pequeño dato, generalmente un entero único que puede servir como índice para una matriz. Los valores devueltos por una función hash se denominan valores hash, códigos hash, sumas hash, sumas de comprobación o simplemente hash. (wikipedia)

Uso de hash de objetos de lenguaje "humano" es un valor corto y compacto basado en las propiedades del objeto. Es decir, si tiene dos objetos que varían de alguna manera, puede esperar que sus valores de hash sean diferentes. El buen algoritmo hash produce diferentes valores para diferentes objetos.

Answer 3

Ese código está tratando de mejorar la calidad del valor hash machacando los bits.

El efecto general es que, para un x.hashCode() determinado, se espera obtener una mejor distribución de valores hash en todo el rango de enteros. El rendimiento de ciertos algoritmos mejorará si comenzó con una implementación de hashcode deficiente, pero luego mejora los códigos hash de esta manera.

Por ejemplo, hashCode() para un Entero humilde en Java simplemente devuelve el valor entero. Si bien esto está bien para muchos propósitos, en algunos casos se quiere un código hash mucho mejor, por lo que poner el hashCode a través de este tipo de función lo mejoraría significativamente.

Answer 4

Básicamente, lo que estás tratando de lograr con una función hash es dar a todos los bits del código hash una probabilidad aproximada del 50% de que se active o desactive dado un elemento en particular que se va a aplicar.De esta forma, no importa cuántos "cubos" tenga tu tabla hash (o dicho de otra manera, cuántos bits inferiores tomas para determinar el número de cubeta) - si cada bit es tan aleatorio como posible, entonces un artículo siempre será asignado a un cubo esencialmente aleatorio.

Ahora, en la vida real, muchas personas usan funciones hash que no son tan buenas. Tienen algunos aleatoriedad en algunos de los bits, pero no en todos ellos. Por ejemplo, imagina que si tienes una función hash cuyos bits 6-7 son parciales, digamos en el típico código hash de un objeto, tienen un 75% de posibilidades de ser configurados. En este ejemplo inventado, si nuestra tabla de hash tiene 256 cubos (es decir, el número de cubeta proviene de los bits 0-7 del código hash), entonces estamos descartando la aleatoriedad que existe en los bits 8-31, y una menor la porción de los cubos tenderá a llenarse (es decir, aquellos cuyos números tienen los bits 6 y 7 establecidos).

La función hash suplementaria básicamente trata de propagar cualquier aleatoriedad que haya en los códigos hash en un mayor número de bits. Entonces, en nuestro ejemplo hipotético, la idea sería que parte de la aleatoriedad de los bits 8-31 se mezclaría con los bits inferiores, y diluiría el sesgo de los bits 6-7. Todavía no será perfecto, pero mejor que antes.

Answer 5

Si está generando una tabla hash, lo principal que quiere transmitir al escribir su función hash es garantizar la uniformidad, no necesariamente para crear valores completamente únicos.

Por ejemplo, si tiene una tabla hash del tamaño 10, no quiere una función hash que devuelve un hash de 3 una y otra vez. De lo contrario, ese cubo específico forzará un tiempo de búsqueda de O (n). Desea una función hash tal que regrese, por ejemplo: 1, 9, 4, 6, 8 ... y asegúrese de que ninguno de sus cubos sea mucho más pesado que los otros.

Para sus proyectos, le recomiendo que utilice un conocido algoritmo hash como MD5 o incluso mejor, SHA y use los primeros k bits que necesite y descarte el resto. Estas son funciones comprobadas y como programador, sería inteligente usarlas.

Answer 6

Podría ser cualquier cosa que desee, siempre y cuando se adhieran a la general contract se describe en el documento, que en mis propias palabras son:

• Si llama 100 (N) veces hashCode en un objeto, toda los tiempos debe devolver el mismo valor, al menos durante ese ejecución del programa (ejecución del programa subsiguiente puede devolver una diferente)
• Si o1.equals(o2) es cierto, entonces o1.hashCode() == o2.hashCode() debe ser cierto también
• Si o1.equals(o2) es falsa, entonces o1.hashCode() == o2.hashCode() puede haber cierto, pero yo t ayuda a que no lo sea

Y eso es todo.

Dependiendo de la naturaleza de su clase, el hashCode() e puede ser muy complejo o muy simple. Por ejemplo, la clase String que puede tener millones de instancias necesita una implementación muy buena hashCode, y usa números primos para reducir la posibilidad de colisiones.

Si para su clase tiene sentido tener un número consecutivo, está bien, no hay ninguna razón por la que deba complicarlo todo el tiempo.