¿Qué función de hash usa Java para implementar la clase Hashtable?

Del libro CLRS (“Introducción a Algoritmos”), hay varias funciones hash, como mod, multiply, etc.

¿Qué función de hash utiliza Java para asignar las claves a las ranuras?

He visto que hay una pregunta aquí. Función Hashing utilizada en Java Language . Pero no responde la pregunta, y creo que la respuesta marcada para esa pregunta es incorrecta. Dice que hashCode () te permite hacer tu propia función hash para Hashtable, pero creo que está mal.

El número entero devuelto por hashCode () es la clave real para Hashtble, luego Hashtable usa una función hashing para hash el hashCode (). Lo que esta respuesta implica es que Java te da la oportunidad de darle a Hashtable una función de hash, pero no, está mal. hashCode () da la clave real, no la función hash.

Entonces, ¿qué función hash usa exactamente Java?

Cuando se agrega o se solicita una clave desde un HashMap en OpenJDK, el flujo de ejecución es el siguiente:

  1. La clave se transforma en un valor de 32 bits utilizando el método hashCode() definido por el desarrollador.
  2. El valor de 32 bits se transforma mediante una segunda función hash (de la cual la respuesta de Andrew contiene el código fuente) en un desplazamiento dentro de la tabla hash. Esta segunda función hash es proporcionada por la implementación de HashMap y no puede ser anulada por el desarrollador.
  3. La entrada correspondiente de la tabla hash contiene una referencia a una lista vinculada o nulo, si la clave aún no existe en la tabla hash. Si hay colisiones (varias teclas con el mismo desplazamiento), las claves junto con sus valores simplemente se recostackn en una lista individualmente vinculada.

Si el tamaño de la tabla hash fue elegido apropiadamente alto, el número de colisiones será limitado. Por lo tanto, una sola búsqueda toma solo un tiempo constante en promedio. Esto se llama tiempo constante esperado . Sin embargo, si un atacante tiene control sobre las claves insertadas en una tabla hash y conoce el algoritmo hash en uso, puede provocar muchas colisiones hash y, por lo tanto, forzar el tiempo lineal de búsqueda. Esta es la razón por la cual algunas implementaciones de la tabla hash se han cambiado recientemente para incluir un elemento aleatorio que hace que sea más difícil para un atacante predecir qué teclas provocarán colisiones.

Algo de arte ASCII

 key.hashCode() | | 32-bit value | hash table V +------------+ +----------------------+ HashMap.hash() --+ | reference | -> | key1 | value1 | null | | |------------| +----------------------+ | modulo size | null | | = offset |------------| +---------------------+ +--------------> | reference | -> | key2 | value2 | ref | |------------| +---------------------+ | .... | | +----------------+ V +----------------------+ | key3 | value3 | null | +----------------------+ 

De acuerdo con la fuente de hashmap, cada hashCode es hash utilizando el siguiente método:

  /** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 

La razón por la que cada hashCode se ha vuelto a codificar, es evitar aún más una colisión (ver comentarios arriba)

HashMap también usa un método para determinar el índice de un código hash (dado que la longitud siempre es una potencia de 2, puede usar & en lugar de%):

 /** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); } 

El método put tiene el siguiente aspecto:

 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); 

El propósito de un código hash es proporcionar una representación entera única para un objeto dado. Tiene sentido, entonces, que el método hashCode de Integer simplemente devuelva el valor porque cada valor sería exclusivo para ese objeto Integer.

Hashing en general se divide en dos pasos: a. HashCode b. Apresamiento

En el paso a. se genera un entero correspondiente a su clave. Esto puede ser modificado por usted en Java.

En el paso b. Java aplica una técnica de compresión para mapear el número entero devuelto por el paso a. a una ranura en el hashmap o hashtable. Esta técnica de compresión no se puede cambiar.

Creo que hay algo de confusión sobre el concepto aquí. Una función hash asigna una entrada de tamaño variable a una salida de tamaño fijo (el valor hash). En el caso de los objetos de Java, el resultado es un entero de 32 bits con signo.

La Hashtable de Java usa el valor hash como un índice en una matriz donde se almacena el objeto real, teniendo en cuenta la aritmética de módulo y las colisiones. Sin embargo, esto no es hash.

La implementación de java.util.HashMap realiza un intercambio de bits adicional en el valor hash antes de la indexación para proteger contra colisiones excesivas en algunos casos. Se llama “hash adicional”, pero no creo que sea un término correcto.

Para decirlo de una manera muy simple, el segundo hashing no es otra cosa que encontrar el número de índice de la matriz de cubo donde se almacenará el nuevo par clave-valor. Esta asignación se hace para obtener el número de índice del mayor valor int del código de hash de la clave obj. Ahora bien, si dos objetos clave desiguales tienen el mismo código hash, la colisión se producirá ya que se asignarán al mismo índice de matriz. En este caso, la segunda clave junto con su valor se agregará a la lista vinculada. Aquí, el índice de matriz apuntará al último nodo agregado.