Reescribir el código fuente del mapa hash
El mecanismo de almacenamiento Hash fue analizado a través del código fuente de HashMap y HashSet.
De hecho, HashSet y HashMap tienen muchas similitudes. Para HashSet, el sistema utiliza un algoritmo hash para determinar la ubicación de almacenamiento de los elementos del conjunto, lo que garantiza que los elementos del conjunto se puedan almacenar y recuperar rápidamente. Para HashMap, los valores clave del sistema se tratan como un todo y la ubicación de almacenamiento de los valores clave siempre se calcula de acuerdo con el algoritmo Hash, lo que garantiza que los pares clave-valor mapeados se puedan almacenar y recuperar rápidamente. .
Antes de introducir el almacenamiento de colecciones, cabe señalar que, aunque las colecciones afirman almacenar objetos Java, en realidad no colocan objetos Java en colecciones de colecciones, sino que solo conservan referencias a estos objetos en colecciones de colecciones. En otras palabras, una colección Java es en realidad una colección de múltiples variables de referencia que apuntan a objetos Java reales.
Colección y referencia
Al igual que una matriz de tipos de referencia, cuando colocamos un objeto Java en una matriz, en realidad no colocamos el objeto Java en la matriz, simplemente poner la referencia al objeto. Las referencias se colocan en matrices y cada elemento de la matriz es una variable de referencia.
Implementación de almacenamiento de HashMap
Cuando un programa intenta colocar múltiples valores clave en un HashMap, tome el siguiente fragmento de código como ejemplo:
Java código
Cadena HashMap lt, Double gtmap = nueva cadena HashMap lt, Double gt()
Map.put("Chino",
); Map.put("Mathematics", 89.0);
Map.put("English", 78.2);
HashMap utiliza el llamado "algoritmo hash" para determinar el almacenamiento. Ubicación de cada elemento.
Cuando el programa ejecuta map.put("Chinese", 80.0);, el sistema llamará al método hashCode() de "Chinese" para obtener su valor hashCode: cada objeto Java tiene un hashCode(). método, que se puede utilizar para obtener su valor hashCode. Después de obtener el valor de hashCode de este objeto, el sistema determinará la ubicación de almacenamiento del elemento en función del valor de hashCode.
Podemos ver el código fuente del método put(K key, V value) de la clase HashMap:
Código Java
Public V put( Clave K, valor V)
{
// Si la clave es nula, llame al método putForNullKey para su procesamiento.
if (key == null)
Return putForNullKey(value);
//Calcule el valor hash según el código clave de la clave.
int hash = hash(key . hashcode());
//Busca el índice del valor hash especificado en la tabla correspondiente.
int i = indexFor(hash, table . length);
// Si la entrada en el índice I no está vacía, atraviesa continuamente el siguiente elemento del elemento E a través de a. bucle.
for(Entrada lt;k,V gte =Tabla[I];e!= nulle = e.next)
{
Objeto k;
//Se descubre que la clave especificada es igual a la clave que se va a colocar (el valor hash es el mismo
//Devuelve verdadero en comparación igual)
if(e. hash = = hash amp; amp((k = e.key) == clave
|| key.equals(k)))
{
V oldValue = e.value
e.value =value;
e acceso al registro(this);
Devuelve el antiguo. value;
}
}
//Si la entrada en el índice I está vacía, no hay ninguna entrada aquí.
modcount;
//Agregar claves y valores al índice I.
addEntry(hash, clave, valor, I);
Devolver nulo
}
El programa anterior utiliza una interfaz interna importante : Mapa. entradas y cada mapa. La entrada es en realidad un par clave-valor. Como se puede ver en el programa anterior, cuando el sistema decide almacenar pares clave-valor en un HashMap, no considera el valor en la entrada en absoluto y solo determina la ubicación de almacenamiento de cada entrada en función de los cálculos clave. Esto también explica la conclusión anterior: podemos considerar completamente los valores en el conjunto de mapeo como archivos adjuntos a la clave. Cuando el sistema determina la ubicación de almacenamiento de la clave, puede guardar el valor allí.
El método anterior proporciona un método para calcular HashCode en función del valor de retorno de hashcode (): hash(). Este es un cálculo matemático puro. El método es el siguiente:
. Código Java
Hash entero estático(entero h)
{
^=(h gt; gt gt^(h gt; gt gt12);
Devuelve h ^(h gt; gt gt7)^(h gt; gt gt4);
}
Para cualquier objeto dado, siempre que su HashCode( ) devuelve el mismo valor, entonces el valor del código hash calculado llamando al método hash(int h) es siempre el mismo. A continuación, el programa llamará al método indexFor(int h, int length) para calcular si el objeto debe almacenarse. en la matriz de la tabla. Qué índice. El código del método indexFor (int h, int length) es el siguiente:
Código Java
Índice entero estático para (entero h, entero). longitud)
{
Devuelve h amp (longitud -1);
}
Este método es muy inteligente, siempre pasa H; (table.length -1) para obtener la ubicación de almacenamiento del objeto, y la longitud de la matriz inferior de HashMap es siempre 2 elevado a la enésima potencia. Esto se puede ver en la introducción del constructor HashMap más adelante. p>
Cuando la longitud es siempre múltiplo de 2. Cuando, H; (longitud-1) será un diseño muy inteligente: suponiendo H = 5, Longitud = 16, entonces h amp Longitud-1 obtendrá 5; si h = 6, longitud = 16, entonces h; longitud-1 obtendrá 6... Si H = 15, longitud = 16, entonces H longitud -1 obtendrá 15; entonces h; longitud -1 obtendrá 0; cuando h= 17, cuando longitud = 16, entonces h longitud -1 obtendrá 1... Esto asegura que el valor del índice calculado esté siempre dentro del índice de la matriz de la tabla.
Como se puede ver en el código fuente del método put anterior, cuando el programa intenta colocar un par clave-valor en un HashMap, el programa primero determina la ubicación de almacenamiento de la entrada según el código hash. () valor de retorno de la clave: si el valor de retorno de hashCode() de la clave de dos entradas es el mismo, entonces su ubicación de almacenamiento es la misma. Si las claves de las dos entradas devuelven verdadero mediante una comparación de igualdad, el valor de la entrada recién agregada sobrescribirá el valor de la entrada original en la colección, pero la clave no lo sobrescribirá. Si las claves de estas dos entradas devuelven falso a través de la comparación de igualdad, entonces la entrada recién agregada formará una cadena de entrada con la entrada original en la colección, y la entrada recién agregada se ubicará al principio de la cadena de entrada; consulte la descripción de el método addEntry() para más detalles.
Cuando se agrega un par clave-valor a un HashMap, la ubicación de almacenamiento del par clave-valor (es decir, el objeto Entry) está determinada por el valor de retorno de su clave hashCode(). Cuando el valor de retorno de hashCode() de la clave de dos objetos de Entrada es el mismo, la clave comparará los valores a través de eqauls() para decidir si adopta un comportamiento de sobrescritura (devuelve verdadero) o genera una cadena de Entrada (devuelve falso) .
El programa anterior también llama al código AddEntry(hash, key, value, I); donde addEntry es el método de acceso al paquete proporcionado por HashMap y solo se usa para agregar un par clave-valor. El siguiente es el código de este método:
Código Java
void addEntry(int hash, K key, V value, int bucketIndex)
{
//Obtiene la entrada en el índice bucketIndex especificado.
Entrada ltk, V gte = table [bucket index]; // ①
//Coloque la entrada recién creada en bucketIndex y haga que la nueva entrada apunte a la entrada original.
table[bucketIndex] = nueva entrada ltk, V gt(hash, key, value, e
//Si el número de pares clave-valor en el mapa excede el); límite,
if(size gt;=threshold)
//Ampliar la longitud del objeto de la tabla a 2 veces.
Resize (2 * table . length); // ②
}
El código del método anterior es muy simple, pero contiene un diseño muy elegante. : El sistema siempre coloca el objeto Entrada recién agregado en el índice de depósito de la matriz de tabla; si ya hay un objeto Entrada en el índice de depósito, entonces el objeto Entrada recién agregado apunta al objeto Entrada original (generando una cadena de Entrada). Si no hay ningún objeto Entrada en el índice bucketIndex, es decir, la variable e en el código 1 en el programa anterior es nula, es decir, el objeto Entrada recién agregado apunta a nulo, es decir, no se genera ninguna cadena de Entrada.
Código fuente JDK
Puede encontrar un archivo comprimido src.zip en el directorio de instalación de JDK, que contiene todos los archivos fuente de la biblioteca de clases básica de Java. Siempre que el lector esté interesado en aprender, puede abrir este archivo comprimido en cualquier momento para leer el código fuente de la biblioteca de clases Java, lo cual es muy útil para mejorar la capacidad de programación del lector. Cabe señalar que el código fuente contenido en src.zip no contiene comentarios en chino como el anterior, estos comentarios los agrega el propio autor.
Opciones de rendimiento del algoritmo hash
Como se puede ver en el código anterior, cuando el mismo depósito almacena la cadena de entrada, la entrada recién colocada siempre se encuentra en el depósito. La primera entrada al barril está al final de esta cadena de entrada.
Hay dos variables en el programa anterior:
* tamaño: esta variable almacena el número de pares clave-valor contenidos en este HashMap.
* umbral: esta variable contiene el límite de pares clave-valor que HashMap puede acomodar. Su valor es igual a la capacidad de HashMap multiplicada por el factor de carga.
Como se puede ver en el código ② del programa anterior, cuando el tamaño es mayor que; = umbral, HashMap llamará automáticamente al método de cambio de tamaño para expandir la capacidad de HashMap. Cada vez que se amplía, la capacidad del HashMap se duplica.
La tabla utilizada en el programa anterior es en realidad una matriz ordinaria. Cada matriz tiene una longitud fija. La longitud de esta matriz es la capacidad del HashMap. HashMap contiene los siguientes constructores:
* HashMap(): construye un HashMap con una capacidad inicial de 16 y un factor de carga de 0,75.
* HashMap(int inicialCapacity): construye un HashMap con capacidad inicial y factor de carga 0,75.
* HashMap (capacidad inicial int, factor de carga flotante): crea un HashMap con la capacidad inicial especificada y el factor de carga especificado.
Cuando crea una tabla hash, el sistema crea automáticamente una matriz de tabla para contener las entradas en la tabla hash. El siguiente es el código del constructor en HashMap:
Código Java
//Crea un HashMap con la capacidad de inicialización y el factor de carga especificados.
public HashMap(int capacidad inicial, float loadFactor)
{
//La capacidad inicial no puede ser negativa.
if(capacidad inicial lt; 0)
Lanza una nueva IllegalArgumentException(
"Capacidad inicial ilegal:"
Capacidad inicial);
//Si la capacidad inicial es mayor que la capacidad máxima, mostraré la capacidad.
if (capacidad inicial gt; capacidad máxima)
CAPACIDAD inicial = max _ CAPACIDAD;
//El factor de carga debe ser mayor que 0.
if(Load factor lt= 0 || Float.isNaN(loadFactor))
Lanza una nueva IllegalArgumentException(
Factor de carga);
//Calcule el valor cuadrado más pequeño mayor que la capacidad inicial.
int capacidad = 1;
mientras (capacidad lt capacidad inicial)
Capacidad lt lt = 1
this.loadFactor = Factor de carga;
//Establezca el límite de capacidad en capacidad*factor de carga.
Umbral = (int)(capacidad * factor de carga);
//Inicializar matriz de tabla
tabla = nueva entrada [capacidad]; /p>
init();
}
El código en negrita en el código anterior contiene una implementación de código concisa: encuentre la enésima potencia de 2 mayor que el valor mínimo de capacidad inicial y Úselo como la capacidad real del HashMap (guardada por la variable Capacidad). Por ejemplo, dada una capacidad inicial de 10, la capacidad real de HashMap es 16.
Como se puede ver en el código del programa ①, la esencia de la tabla es una matriz, una matriz con una longitud de capacidad.
Para HashMap y sus subclases, utilizan un algoritmo hash para determinar dónde se almacenan los elementos en la colección. Cuando el sistema comience a inicializar el HashMap, el sistema creará una matriz de entrada con una longitud de capacidad. La ubicación en esta matriz donde se pueden almacenar los elementos se llama "depósito" y cada depósito tiene su índice asignado, por lo que el sistema puede acceder rápidamente a los elementos almacenados en el depósito en función de su índice.
En cualquier momento, cada depósito de HashMap almacena solo un elemento (es decir, una entrada). Debido a que el objeto Entry puede contener una variable de referencia (es decir, el último parámetro del constructor Entry) para apuntar a la siguiente entrada, puede suceder que solo haya una entrada en el depósito HashMap, pero esta entrada apunte a otra entrada. esto forma una cadena de elementos. Como se muestra en la Figura 1:
Figura 1. Gráfico de almacenamiento de HashMap
Leer la implementación de HashMap
Cuando solo hay una entrada almacenada en cada depósito de HashMap, es decir, la cadena de entrada no se genera mediante un puntero —— HashMap tiene el mejor rendimiento: cuando el programa obtiene el valor correspondiente a través de la clave, el sistema solo necesita calcular primero el valor de retorno de la clave. Encuentre el índice de la clave en la matriz de la tabla según el valor de retorno de hashCode, luego saque la entrada en el índice y finalmente devuelva el valor correspondiente a la clave. Eche un vistazo al código del método get(clave K) de la clase HashMap:
Código Java
public V get (clave de objeto)
{
//Si la clave está vacía, llame a getForNullKey para obtener el valor correspondiente.
if (key == null)
Return getForNullKey();
// Calcula el código hash de la palabra clave en función del valor del código hash de la palabra clave.
int hash = hash(key . hashcode());
//Obtiene directamente el valor en el índice especificado en la matriz de la tabla,
for( Entrada lt ; k, V gte = table[indexFor(hash, table . length)]
e! = null
//Buscar la siguiente entrada en la cadena de entrada
.e = e.next) // ①
{
Objeto k;
//Si la palabra clave de la entrada es Lo mismo que la palabra clave buscada.
if(e . hash == hash amp; amp((k = e.key) == clave
|| key.equals(k)))
Devolver e.value
}
Devolver null
}
Como se puede ver en el código anterior, si el HashMap Solo hay una entrada en cada depósito, y HashMap puede recuperar rápidamente las entradas en el depósito de acuerdo con el índice. En el caso de un "conflicto de hash", un solo depósito almacena no una entrada, sino una cadena de entradas, y el sistema; solo puede recorrer cada entrada por turno hasta que se encuentre el elemento que desea buscar; si el elemento que desea buscar está al final de la cadena de elementos (el primero que se coloca en el depósito), el sistema debe realizar un bucle. hasta el final para encontrar el elemento.
En resumen, HashMap trata el valor clave como un todo en la capa inferior, y este todo es un objeto de entrada. La capa inferior de HashMap utiliza la matriz Entry[] para almacenar todos los pares clave-valor. Cuando es necesario almacenar un objeto de entrada, su ubicación de almacenamiento se determinará en función de un algoritmo hash. Cuando es necesario recuperar una entrada, se encontrará su ubicación de almacenamiento según el algoritmo hash y la entrada se recuperará directamente.
Se puede ver que la razón por la que HashMap puede almacenar y recuperar rápidamente los elementos que contiene es completamente similar a lo que mi madre nos enseñó en la vida real desde la infancia: se deben colocar diferentes cosas en diferentes lugares para que se puedan encontrar rápidamente cuando sea necesario. .
Al crear un HashMap, hay un factor de carga predeterminado (el valor predeterminado es 0,75), que es un compromiso entre la sobrecarga de tiempo y espacio: aumentar el factor de carga puede reducir la memoria ocupada por la tabla hash ( es decir, la matriz de entrada), pero aumentará el costo de tiempo de consultar datos, y la consulta es la operación más frecuente (tanto el método get() como el put() de HashMap usan la consulta al reducir el factor de carga mejorará el rendimiento); de consulta de datos, pero aumentará el número de tablas hash y el espacio de memoria ocupado.
Después de dominar el conocimiento anterior, podemos ajustar adecuadamente el valor del factor de carga de acuerdo con las necesidades reales al crear un HashMap; si el programa se preocupa por los costos de espacio y la memoria es escasa, el factor de carga puede ser apropiado; aumenta si el programa se preocupa por la sobrecarga de tiempo y la memoria es suficiente, el factor de carga se puede reducir adecuadamente. Normalmente, los programadores no necesitan cambiar el valor del factor de carga.
Si sabe desde el principio que HashMap guardará múltiples pares clave-valor, puede utilizar una mayor capacidad de inicialización al crearlo. Si el número de entradas en HashMap nunca excede la capacidad * factor de carga, HashMap no necesita llamar al método resize() para reasignar la matriz de la tabla, lo que garantiza un mejor rendimiento. Por supuesto, configurar la capacidad inicial demasiado alta al principio puede desperdiciar espacio (el sistema necesita crear una matriz de entrada con una longitud de capacidad), por lo que también debe tener cuidado con la configuración de capacidad inicial al crear un HashMap.