En este artículo, comenzamos a analizar el código fuente de Linkedhashmap. Linkedhashmap hereda el hashmap, lo que significa que Linkedhashmap se extiende en base a hashmap. Por lo tanto, antes de mirar el código fuente de LinkedHashmap, los lectores deben comprender el código fuente de HASHMAP. Puede consultar la introducción de mi artículo anterior "Serie de colección Java [3] ---- Análisis de código fuente hashmap". Mientras tenga una comprensión profunda del principio de implementación de Hashmap, y luego, la vista de los códigos fuente de Linkedhashmap, Hashset y Linkedhashset son muy simples. Por lo tanto, los lectores deben ser pacientes y estudiar el código fuente de Hashmap. Este es un buen negocio para comprar uno Get Three GRATIS. Al analizar el código fuente de HashMap anteriormente, utilicé el análisis orientado a problemas del código fuente para no analizarlo al azar como una mosca sin cabeza, y los lectores también podrían tener una comprensión más profunda del problema. En este artículo, decidí usar este método para analizar LinkedHashMap.
1. ¿Qué tipo de estructura se usa dentro de Linkedhashmap?
Como puede ver, dado que Linkedhashmap hereda de Hashmap, todavía hay una tabla de hash dentro de Linkedhashmap, pero Linkedhashmap ha reescrito una entrada y ha agregado dos variables miembros a la entrada de hashmap original, a saber, la referencia de nodo anterior y la referencia de nodo sucesor. De esta manera, todos los nodos están vinculados para formar una lista vinculada bidireccional. Al obtener elementos, simplemente atraviese la lista vinculada bidireccional directamente. Veamos cómo es la implementación de la entrada de Linkedhashmap.
Entrada de clase estática privada <k, v> extiende hashmap.entry <k, v> {// referencia del nodo anterior del nodo actual en la entrada de la lista vinculada bidireccional <k, v> antes; // Referencia del nodo posterior del nodo actual en la entrada de la lista vinculada bidireccional <k, v> después; Entrada (int hash, k key, v valor, hashmap.entry <k, v> next) {super (hash, clave, valor, siguiente); } // Eliminar este nodo de la lista vinculada bidireccional private void remove () {antes.after = después; después.before = antes; } // Inserte el nodo actual en un nodo existente en la lista bidireccional vinculada vacía privada addbefore (entrada <k, v> existenteTenny) {// La referencia del siguiente nodo del nodo actual se apunta al nodo dado después = existenteintry; // La referencia del nodo anterior del nodo de corriente apunta al nodo anterior del nodo dado antes = existenteTry.before; // La referencia del siguiente nodo del nodo dado puntos al nodo actual antes. // La referencia del nodo anterior del nodo dado dados al nodo actual después. } // ordenado en orden de acceso, registre cada vez que la operación se obtiene void RecordAccess (Hashmap <K, V> m) {Linkedhashmap <k, v> lm = (Linkedhashmap <k, v>) m; // si se clasifica en orden de acceso if (lm.accessorder) {lm.modcount ++; // eliminar primero de la lista vinculada bidireccional; // Ponte a la cola de la lista vinculada bidireccional addbefore (lm.header); }} void récordremoval (hashmap <k, v> m) {remove (); }}2. ¿Cómo implementa LinkedHashmap en orden en orden de inserción?
// El método que se llamará en el método PUT de la clase principal Void Addentry (int hash, k key, V value, int bucketIndex) {// llamando al método Addentry de la clase principal Super.addentry (hash, clave, valor, bucketIndex); // La siguiente operación es conveniente para la implementación de caché LRU. Si la capacidad de la caché es insuficiente, retire la entrada del elemento más antiguo <k, v> ancianos = header. después; if (removeLdestEntry (eldest)) {removeStryForKey (eldest.key); }} // El método void createEntry (int hash, k key, v valor, int bucketIndex) {// primero obtenga la entrada hashmap de hashmap.entry <k, v> old = table [bucketIndex]; // envuélvalo en la entrada propia de Linkedhashmap <k, v> e = nueva entrada <> (hash, clave, valor, antigua); tabla [bucketIndex] = e; // inserta el nodo actual en la cola de la lista vinculada bidireccional e.Addbefore (encabezado); tamaño ++;}LinkedHashmap anula los métodos de Addentry y CrearEntry de su clase de clase principal Hashmap. Cuando desee insertar un par de valor clave, el método PUT de su clase de clase principal se llamará primero. En el método PUT, verificaremos si la clave correspondiente existe en la tabla hash. Si existe, simplemente reemplace su valor directamente. Si no existe, llame al método Addentry para crear una nueva entrada. Tenga en cuenta que en este momento, se llama al método de Addentry de Linkedhashmap. Vemos el código anterior. Además de volver a llamar al método AddelDestEntry de la clase principal, este AddelDestEntry también llamará a RemoLDestEntry para eliminar el elemento más antiguo. Esta operación es principalmente para implementar el algoritmo LRU, que se analizará a continuación. Vemos que Linkedhashmap también reescribe el método CreateEntry. Cuando desee crear una nueva entrada, se llamará a este método. Después de cada vez que la entrada se coloca en la tabla hash, se llamará al método addBeFore para insertar el nodo actual en la cola de la lista vinculada bidireccional. De esta manera, la lista vinculada bidireccional registra el orden de cada nodo insertado. Al obtener elementos, simplemente atraviese la lista vinculada bidireccional. La siguiente figura muestra el funcionamiento de cada llamada para addbefore. Dado que es una lista vinculada bidireccional, antes de insertar el nodo actual en el nodo de la cabeza, en realidad está insertando el nodo actual en la cola de la lista vinculada bidireccional.
3. ¿Cómo usar LinkedHashMap para implementar la caché LRU?
Sabemos que la implementación de caché depende de la memoria de la computadora, y los recursos de memoria son bastante limitados, y es imposible almacenar elementos sin límite. Por lo tanto, necesitamos eliminar adecuadamente algunos elementos cuando la capacidad es insuficiente. Entonces, ¿qué elemento es mejor para eliminar? La idea del algoritmo LRU es que si se ha accedido a datos recientemente, las posibilidades de acceder en el futuro también son más altas. Por lo tanto, podemos eliminar datos a los que no se accede a menudo. A continuación, echemos un vistazo a cómo Linkedhashmap implementa el mecanismo LRU.
clase pública Linkedhashmap <k, v> extiende hashmap <k, v> implementa mapa <k, v> {// encabezado de lista de listas tanto en entrada transitoria privada <k, v> encabezado; // Ordena la orden de acceso booleano final privado en orden de acceso; ... public Linkedhashmap (int InitialCapacity, Float LoadFactor, Boolean AccessOrder) {super (InicialCapacity, LoadFactor); this.accessOrder = AccessOrder; } // Obtener valor de acuerdo con la clave public v get (clave de objeto) {// llamando al método de clase principal para obtener la entrada de entrada correspondiente <k, v> e = (entrada <k, v>) getEntry (clave); if (e == null) {return null; } // Si se clasifica en orden de acceso, el nodo después de cada uso se colocará al final de la lista vinculada bidireccional E.RecordAccess (esto); devolver E.Value; } Entrada de clase estática privada <k, v> extiende hashmap.entry <k, v> {... // Inserte el nodo actual en el frente de un nodo existente en la lista bidireccional vinculada void private addbefore (entrada <k, v> existente) {// la referencia del siguiente nodo de los puntos de nodo actuales al nodo dado después de = existente; // La referencia del nodo anterior del nodo de corriente apunta al nodo anterior del nodo dado antes = existenteTry.before; // La referencia del siguiente nodo del nodo dado puntos al nodo actual antes. // La referencia del nodo anterior del nodo dado dados al nodo actual después. } // ordenado en orden de acceso, registre cada vez que la operación void registreCcess (hashmap <k, v> m) {linkedhashmap <k, v> lm = (Linkedhashmap <k, v>) m; // si se clasifica en orden de acceso if (lm.accessorder) {lm.modcount ++; // eliminar primero de la lista vinculada bidireccional; // Ponte a la cola de la lista vinculada bidireccional addbefore (lm.header); }} ...} // Este método se llamará en el método de la clase principal, el método void Addentry (int hash, k key, v value, int bucketIndex) {// Calcule el método de Addentry de la clase principal Super.addentry (hash, key, valor, bucketIndex); // La siguiente operación es conveniente para la implementación de caché LRU. Si la capacidad de la caché es insuficiente, retire la entrada del elemento más antiguo <k, v> ancianos = header. después; if (removeLdestEntry (eldest)) {removeLDestForKey (eldest.key); }} // ¿Dónde eliminar el elemento más antiguo? Este método está diseñado para ser sobrescribido por subclases boolean boolean remoLeLDestEntry (map.entry <k, v> ancianos) {return false; }}Para ser más intuitivos, omití algún código irrelevante en el código publicado anteriormente. Podemos ver que LinkedHashmap tiene una orden de acceso variable miembro, que registra si debe ordenarse en orden de acceso. Proporciona un constructor que puede especificar el valor de AccessOrge en sí. Cada vez que llame al método GET para obtener el elemento, se llama a E.RecordAccess (esto), que moverá el nodo actual al final de la lista vinculada bidireccional. Ahora sabemos que si AccessOrder es verdadero, cada vez que obtengamos el elemento, moveremos este elemento al final de la lista de enlaces bidireccionales. El propósito de este paso es distinguir los elementos más utilizados de los que no se usan a menudo, y los elementos utilizados a menudo se colocan al final y los elementos menos utilizados se colocan en la cabeza. Volvamos al código anterior y veamos que cada vez que se llame al método de complemento, determinaremos si el elemento más antiguo debe eliminarse. La lógica del juicio es implementada por RemoLDestEntry, que está diseñada para ser anulada por subclases y reescribir la lógica en el interior. Tenga en cuenta que dado que los nodos visitados recientemente se trasladan a la cola de la lista vinculada bidireccional, el nodo más antiguo se saca del jefe de la lista vinculada bidireccional para su eliminación. El siguiente ejemplo implementa un caché LRU simple.
clase pública lrumap <k, v> extiende Linkedhashmap <k, v> {private int capacidad; Lrumap (int capacidad) {// llamando al constructor de clase principal, establecido en ordenar en orden de acceso super (capacidad, 1f, verdadero); this.capacity = capacidad; } @Override public Boolean RemoLeLDestEntry (MAP.Entry <k, v> ancianos) {// Cuando el par de valor clave es mayor o igual que la capacidad de la tabla hash devuelve this.size ()> = capacidad; } public static void main (string [] args) {lrumap <integer, string> map = new Lrumap <Integer, String> (4); map.put (1, "A"); map.put (2, "b"); map.put (3, "c"); System.out.println ("Colección original:" + map); Cadena s = map.get (2); System.out.println ("Get Element:" + map); map.put (4, "d"); System.out.println ("Después de la inserción:" + map); }}Los resultados son los siguientes:
Nota: Todo el análisis anterior se basa en JDK1.7, y habrá diferencias entre diferentes versiones, los lectores deben prestar atención.
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.