Hemos analizado los dos conjuntos de ArrayList y LinkedList. Sabemos que ArrayList se implementa en función de las matrices, y LinkedList se implementa en función de las listas vinculadas. Cada uno tiene sus propias ventajas y desventajas. Por ejemplo, ArrayList será mejor que LinkedList al posicionar y buscar elementos, mientras que LinkedList será mejor que ArrayList al agregar y eliminar elementos. El hashmap introducido en este artículo combina las ventajas de ambos. Su capa subyacente se implementa en base a una tabla hash. Si no se considera el conflicto hash, la complejidad del tiempo del hashmap, además, la eliminación, la modificación y las operaciones de búsqueda pueden alcanzar una O sorprendente (1). Primero veamos la estructura de la tabla hash en la que se basa.
Como se puede ver en la figura anterior, una tabla hash es una estructura compuesta de una matriz y una lista vinculada. Por supuesto, la figura anterior es un mal ejemplo. Una buena función hash debe intentar promediar la distribución de elementos en la matriz, reducir los conflictos hash y reducir la longitud de la lista vinculada. Cuanto más larga la longitud de la lista vinculada significa que más nodos deben atravesar durante la búsqueda, peor será el rendimiento de la tabla hash. A continuación, echemos un vistazo a algunas variables miembros de Hashmap.
// Capacidad inicial predeterminada estática final int default_initial_capacitity = 1 << 4; // Capacidad máxima predeterminada estática final int maximumummum_capacity = 1 << 30; // factor de carga predeterminado se refiere a cuánto la tabla hash puede alcanzar el float final estático default_load_factor = 0.75f; // hastes hastes vacío en la entrada final <?> [] Vacía Entrada <k, v> [] table = (entrada <k, v> []) vacía_table; // tamaño hashmap, es decir, el número de pares de valores clave almacenados en el tamaño de hashmap transitorio int tamiz; // El umbral de los pares de valor clave se usa para determinar la capacidad de la tabla hash que se debe amplificar int threshold; // el factor de carga de carga final; Fail-Fast Mecanismo Transient int modCount; // Use el umbral predeterminado de alternativo hash estático final int alternativa_hashing_threshold_default = integer.max_value; // La semilla de hash aleatoria ayuda a reducir el número de colisiones hash transitorias intsehseed = 0;
Como se puede ver en las variables del miembro, la capacidad inicial predeterminada de HASHMAP es 16, y el factor de carga predeterminado es 0.75. El umbral es el umbral del par de valores clave que se puede almacenar en el conjunto. El valor predeterminado es la capacidad inicial*Factor de carga, es decir, 16*0.75 = 12. Cuando el par de valor clave debe exceder el umbral, significa que la tabla hash ya está saturada en este momento. Si se continúan agregando los elementos, se agregará el conflicto hash, lo que degradará el rendimiento de HASHMAP. En este momento, el mecanismo de expansión de capacidad automática se activará para garantizar el rendimiento de HASHMAP. También podemos ver que la tabla hash es en realidad una matriz de entrada, y cada entrada almacenada en la matriz es el nodo de encabezado de la lista vinculada unidireccional. Esta entrada es una clase interna estática de hashmap, echemos un vistazo a las variables de entrada de los miembros.
Entrada de clase estática <k, v> implementa map.entry <k, v> {fin final k clave; // valor de la tecla V; // Entrada de valor <k, v> siguiente; // La referencia a la siguiente entrada int hash; // Histocódigo ... // omitir el siguiente código}Una instancia de entrada es un par de valores clave que contiene clave y valor. Cada instancia de entrada tiene una referencia a la siguiente instancia de entrada. Para evitar cálculos repetidos, cada instancia de entrada también almacena el código hash correspondiente. Se puede decir que la matriz de entrada es el núcleo de HASHMAP, y todas las operaciones se realizan para esta matriz. Dado que el código fuente de HashMap es relativamente largo, es imposible introducir todos sus métodos de manera integral, por lo que solo nos centramos en los puntos clave para introducirlos. A continuación, estaremos orientados a los problemas y exploraremos el mecanismo interno del hashmap en profundidad para los siguientes problemas.
1. ¿Qué operaciones hace Hashmap durante la construcción?
// Constructor, pase la capacidad de inicialización y el factor de carga public HASHMAP (int InitialCapacity, Float LoadFactor) {if (InicialCapacity <0) {Throw New IlegalArGumentException ("Capacidad inicial ilegal:" + InicialCapacity); } // Si la capacidad de inicialización es mayor que la capacidad máxima, configúrela a la capacidad máxima if (inicialcapacity> maximum_capacity) {inicialcapacity = maximum_capacity; } // Si el factor de carga es inferior a 0 o el factor de carga no es un número de punto flotante, se lanza una excepción si (LoadFactor <= 0 || float.isnan (LoadFactor)) {arroja nueva IlegalArgumentException ("Factor de carga ilegal:" + LoadFactor); } // Establecer el factor de carga this.loadFactor = LoadFactor; // El umbral es el umbral de capacidad de inicialización = InicialCapacity; init ();} void init () {}Todos los constructores llamarán a este constructor. En este constructor, vemos que, además de hacer alguna verificación de los parámetros, hace dos cosas: establezca el factor de carga en el factor de carga entrante y establezca el umbral en el tamaño de inicialización entrante. El método init está vacío y no hace nada. Tenga en cuenta que en este momento, no se crea una nueva matriz de entrada en función del tamaño de inicialización entrante. Entonces, ¿cuándo crearemos una nueva matriz? Sigue leyendo.
2. ¿Qué operaciones se realizarán cuando Hashmap agrega pares de valores clave?
// Ponga pares de valor clave en hashmap public v put (k key, valor v) {// inicialize if (table == vacía_table) {// Inicializa la tabla hash inflatetable (umbral); } if (key == null) {return putfornullkey (valor); } // Calcule el código hash de la clave int hash = hash (clave); // colocar la posición de la tabla hash de acuerdo con el código hash int i = indexfor (hash, table.length); para (entrada <k, v> e = table [i]; e! = null; e = e.next) {objeto k; // Si la clave correspondiente ya existe, reemplace su valor de valor y devuelva el valor original if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v OldValue = e.Value; e.value = valor; E.RecordAccess (esto); devolver OldValue; }} modcount ++; // Si no hay una clave correspondiente, agregue la entrada a HASHMAP Addentry (hash, clave, valor, i); // devuelve nulo return null;}Puede ver que al agregar pares de valor clave, primero verificará si la tabla hash es una mesa vacía, y si es una tabla vacía, se inicializará. Luego realice operaciones posteriores y llame a la función hash para calcular el código hash de la clave aprobada. Coloque la ranura especificada de la matriz de entrada de acuerdo con el código hash, y luego atraviese la lista vinculada unidireccional de la ranura. Si el aprobado ya existe, realice una operación de reemplazo; de lo contrario, se creará una nueva entrada y se agregará a la tabla hash.
3. ¿Cómo se inicializa la tabla hash?
// Inicializa la tabla hash y la capacidad de la tabla hash se expandirá, porque es posible que la capacidad entrante no sea una potencia de 2 vacío privado inflatetable (int tosize) {// La capacidad de la tabla hash debe ser un poder de 2 int capacidad = redondeuptOpowerOf2 (tosizar); // Establezca el umbral, aquí es generalmente la capacidad * umbral de carga de carga = (int) math.min (capacidad * loadFactor, maximum_capacity + 1); // Crear una nueva tabla hash con una tabla de capacidad especificada = nueva entrada [capacidad]; // Inicializa la semilla hash inithashSteedasNeeded (capacidad);}Como sabemos anteriormente, al construir un hashmap, no crearemos una nueva matriz de entrada, pero verifique si la tabla hash actual es una tabla vacía durante la operación de colocación. Si es una tabla vacía, llame al método inflatetable para la inicialización. El código para este método se publica arriba. Puede ver que la capacidad de la matriz de entrada se recalculará dentro del método, porque el tamaño de inicialización se pasa al construir el hashmap puede no ser una potencia de 2, por lo que debe convertir este número en una potencia de 2 y luego crear una nueva matriz de entrada basada en la nueva capacidad. Al inicializar la tabla hash, reinicie el umbral nuevamente, y el umbral es generalmente de capacidad*factor de carga. Además, la semilla hash (hashseed) se inicializará al inicializar la tabla hash. Este hashseed se usa para optimizar la función hash. El valor predeterminado es 0, y no se usa algoritmo de hash alternativo, pero también puede establecer el valor de hashseed por sí mismo para lograr el efecto de optimización. Esto se discutirá en detalle a continuación.
4. ¿Cuándo determina Hashmap si necesita expandir la capacidad y cómo expande la capacidad?
// Agregue el método de entrada y primero determine si desea expandir la capacidad Void AddEntry (int hash, k key, v value, int bucketIndex) {// Si el tamaño de hashmap es mayor que el umbral y el valor de la ranura correspondiente de la tabla hash no está vacío si ((tamaño> = umbral) && (null! = Table [bucketIndex]) {// Umbral, indica que un conflicto hash está a punto de ocurrir, por lo que expandir el cambio de tamaño de la capacidad (2 * TABLE.LIGTH); hash = (nulo! = clave)? hash (clave): 0; bucketIndex = indexfor (hash, table.length); } // se muestra aquí que el tamaño de hashmap no excede el umbral, por lo que no es necesario expandir la capacidad createEntry (hash, key, valor, bucketIndex);} // Extender la tabla de hash Void RESIZ (int NewCapacity) {Entrada [] Oldtable = Table; int // Si la capacidad máxima actual ya está en uso, solo puede aumentar el umbral if (OldCapacity == Maximum_Capacity) {umbral = Integer.max_value; devolver; } // de lo contrario, expanda la entrada de capacidad [] newtable = nueva entrada [newCapacity]; // el método para migrar la transferencia de tabla hash (newtable, inithashseedasneeded (newcapacity)); // Establezca la tabla hash actual en la nueva tabla hash tabla = newtable; // Actualiza el umbral de tabla hash = (int) Math.min (NewCapacity * LoadFactor, Maximum_Capacity + 1);}Al llamar al método PUT para agregar un par de valores clave, si no hay una clave en la colección, llame al método Addentry y cree una nueva entrada. Cuando vea el código de complemento publicado anteriormente, antes de crear una nueva entrada, primero determinará si el tamaño del elemento de colección actual excede el umbral. Si el umbral excede el umbral, llame al cambiar el tamaño de la expansión. La nueva capacidad pasada es el doble de la tabla hash original. En el método de cambio de tamaño, se creará una nueva matriz de entrada con una capacidad del doble de la tabla hash original. Luego, todos los elementos en la antigua tabla hash se migran a la nueva tabla hash, donde se puede realizar una rehash, y si realizar la rehash se realiza de acuerdo con el valor calculado por el método inithashseedasneeded. Una vez que se completa la migración de la tabla hash, la tabla hash actual se reemplaza con una nueva, y finalmente el valor umbral del hashmap se recalcula en función de la nueva capacidad de la tabla hash.
5. ¿Por qué el tamaño de la matriz de entrada debe ser una potencia de 2?
// devuelve el índice de matriz correspondiente al código hash static int indexFor (int h, int longitud) {return h & (longitud-1); }El método indexFor calcula el subíndice correspondiente en la matriz basada en el código hash. Podemos ver que el operador (&) se usa dentro de este método. La operación es realizar operaciones de bits en dos operandos. Si los dos bits correspondientes son 1, el resultado es 1, de lo contrario, es 0. Las operaciones a menudo se usan para eliminar los valores altos de los operandos, como: 01011010 y 00001111 = 00001010. Volvamos al código y vea lo que hace H & (Longitud-1).
Se sabe que la longitud pasada es la longitud de la matriz de entrada. Sabemos que el subíndice de la matriz se calcula a partir de 0, por lo que el subíndice máximo de la matriz es longitud-1. Si la longitud es una potencia de 2, entonces los bits binarios de la longitud-1 son seguidos por 1. En este momento, la función de H & (Longitud-1) es eliminar el valor de alto bit de H y dejar solo el valor de bajo bit de H como subíndice de la matriz. A partir de esto, podemos ver que el tamaño de la matriz de entrada se define como un poder de 2 para usar este algoritmo para determinar el subíndice de la matriz.
6. ¿Cómo calcula el código hash el código hash?
// La función que genera el código hash final int hash (objeto k) {int h = hashseed; // Si la tecla es de tipo de cadena, use otro algoritmo hash if (0! = H && k instanceOf string) {return sun.misc.hashing.stringhash32 ((string) k); } h ^= k.hashcode (); // La función de perturbación h ^ = (h >>> 20) ^ (h >>> 12); devolver h ^ (h >>> 7) ^ (h >>> 4);}Las dos últimas líneas del método hash son el algoritmo que realmente calcula el valor hash. El algoritmo que calcula el código hash se llama función de perturbación. La llamada función de perturbación es mezclar todo. Puede ver que aquí se utilizan cuatro operaciones de turno de derecha a derecha. El propósito es mezclar el alto valor de H y el bajo valor para aumentar la aleatoriedad del valor bajo. Como anteriormente, sabemos que el subíndice de la matriz de posicionamiento se determina en función del valor de bajo bit del código hash. El código hash de la clave es generado por el método hashcode, y el bajo valor del código hash generado por un método hashcode malo puede tener mucha repetición. Para hacer que el código hash se asigne de manera relativamente uniforme en la matriz, la función de perturbación es útil, combinando las características del valor de alto bit en el valor de bajo bits, aumentando la aleatoriedad del valor de bajo bit, lo que hace que la distribución hash sea más floja, mejorando así el rendimiento. La siguiente figura da un ejemplo para ayudar a comprender.
7. ¿Qué está pasando con el hash de reemplazo?
Vemos que en el método hash, el hashseed se asignará primero a h. Este hashseed es una semilla hash, que es un valor aleatorio, y se usa para ayudar a optimizar la función hash. El hashseed predeterminado es 0, lo que significa que el algoritmo de hash alternativo no se usa de forma predeterminada. Entonces, ¿cuándo usar hashseed? Primero, debe establecer el hash alternativo para habilitar y establecer el valor de jdk.map.althashing.threshold en la propiedad del sistema. Este valor es -1 de forma predeterminada en la propiedad del sistema. Cuando es -1, el valor umbral de usar el hash alternativo es entero.max_value. Esto también significa que nunca puede usar un hash de reemplazo. Por supuesto, puede establecer este umbral un poco más pequeño, de modo que se genere una hashseed aleatoria cuando el elemento establecido alcance el umbral. Esto aumenta la aleatoriedad de la función hash. ¿Por qué usar el hash alternativo? Cuando el elemento establecido alcanza el umbral que establece, significa que la tabla hash está relativamente saturada, y la posibilidad de conflictos hash aumentará enormemente. En este momento, el uso de una función hash más aleatoria para los elementos adicionales puede hacer que los elementos agregados se distribuyan más al azar en la tabla hash.
Nota: Todo el análisis anterior se basa en JDK1.7, y habrá cambios importantes entre las diferentes versiones, los lectores deben prestar atención.