¿Cómo implementa Java las tablas hash?
algorithm (5)
En mis propias palabras:
Se crea un objeto de Entry para contener la referencia de la clave y el valor.
El HashMap tiene una matriz de Entry .
El índice para la entrada dada es el hash devuelto por key.hashCode()
Si hay una colisión (dos claves dieron el mismo índice), la entrada se almacena en el atributo .next de la entrada existente.
Así es como se pueden almacenar dos objetos con el mismo hash en la colección.
De this respuesta obtenemos:
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
Déjame saber si tengo algo mal.
¿Alguien sabe cómo Java implementa sus tablas hash (HashSet o HashMap)? Dados los diversos tipos de objetos que uno puede querer poner en una tabla hash, parece muy difícil encontrar una función hash que funcione bien para todos los casos.
HashMap y HashSet son muy similares. De hecho, el segundo contiene una instancia del primero.
Un HashMap contiene una matriz de cubos para contener sus entradas. El tamaño de la matriz siempre es potencias de 2. Si no especifica otro valor, inicialmente hay 16 depósitos.
Cuando coloca una entrada (clave y valor) en ella, decide el cubo donde se insertará la entrada calculándola a partir del código hash de su clave (el código hash no es su dirección de memoria y el hash no es un módulo ). Las diferentes entradas pueden colisionar en el mismo grupo, por lo que se incluirán en una lista.
Las entradas se insertarán hasta que alcancen el factor de carga. Este factor es 0.75 por defecto, y no se recomienda cambiarlo si no está muy seguro de lo que está haciendo. 0,75 como factor de carga significa que un HashMap de 16 cubos solo puede contener 12 entradas ( 16 * 0,75 ). Luego, se creará una serie de cubos, duplicando el tamaño del anterior. Todas las entradas serán puestas nuevamente en la nueva matriz. Este proceso se conoce como " rehashing" y puede ser costoso.
Por lo tanto, una buena práctica, si sabe cuántas entradas se insertarán, es construir un HashMap especificando su tamaño final:
new HashMap(finalSize);
Hay dos formas generales de implementar un HashMap. La diferencia es cómo se trata con las colisiones.
El primer método, que es uno de los usuarios de Java, hace que cada contenedor en un HashMap contenga una lista enlazada individualmente. Para lograr esto, cada grupo contiene un tipo de entrada , que almacena en caché el código hash, tiene un puntero a la clave, un puntero al valor y un puntero a la siguiente entrada. Cuando se produce una colisión en Java, se agrega otra entrada a la lista.
El otro método para manejar las colisiones es simplemente colocar el artículo en el siguiente cubo vacío. La ventaja de este método es que requiere menos espacio, sin embargo, complica las eliminaciones, ya que si el contenedor que sigue al elemento eliminado no está vacío, uno debe verificar si ese elemento está en el contenedor correcto o incorrecto, y desplazarlo Si originalmente ha chocado con el elemento que se está eliminando.
Java depende de la implementación de cada clase del método hashCode () para distribuir los objetos de manera uniforme. Obviamente, un método hashCode () incorrecto resultará en problemas de rendimiento para tablas hash grandes. Si una clase no proporciona un método hashCode (), el valor predeterminado en la implementación actual es devolver alguna función (es decir, un hash) de la dirección del objeto en la memoria. Citando desde el documento API:
Por más que sea razonablemente práctico, el método hashCode definido por la clase Object devuelve enteros distintos para objetos distintos. (Esto generalmente se implementa al convertir la dirección interna del objeto en un entero, pero el lenguaje de programación JavaTM no requiere esta técnica de implementación).
Puede comprobar la fuente de HashMap , por ejemplo.