1. Información general
En este artículo, vamos a explorar la implementación interna de la clase LinkedHashMap . LinkedHashMap es una implementación común de la interfaz Map .
Esta implementación particular es una subclase de HashMap y, por lo tanto, comparte los componentes básicos de la implementación de HashMap . Como resultado, es muy recomendable repasar eso antes de continuar con este artículo.
2. LinkedHashMap vs HashMap
La clase LinkedHashMap es muy similar a HashMap en la mayoría de los aspectos. Sin embargo, el mapa hash vinculado se basa tanto en la tabla hash como en la lista vinculada para mejorar la funcionalidad del mapa hash.
Mantiene una lista doblemente vinculada que se ejecuta a través de todas sus entradas además de una matriz subyacente de tamaño predeterminado 16.
Para mantener el orden de los elementos, el hashmap vinculado modifica la clase Map.Entry de HashMap agregando punteros a las entradas anterior y siguiente:
static class Entry extends HashMap.Node { Entry before, after; Entry(int hash, K key, V value, Node next) { super(hash, key, value, next); } }Observe que la clase Entry simplemente agrega dos punteros; antes y después de lo cual le permite conectarse a la lista vinculada. Aparte de eso, utiliza la implementación de la clase Entry de HashMap.
Finalmente, recuerde que esta lista enlazada define el orden de iteración, que por defecto es el orden de inserción de elementos (orden de inserción).
3. LinkedHashMap de pedido de inserción
Echemos un vistazo a una instancia de mapa hash vinculado que ordena sus entradas de acuerdo con cómo se insertan en el mapa. También garantiza que este orden se mantendrá durante todo el ciclo de vida del mapa:
@Test public void givenLinkedHashMap_whenGetsOrderedKeyset_thenCorrect() { LinkedHashMap map = new LinkedHashMap(); map.put(1, null); map.put(2, null); map.put(3, null); map.put(4, null); map.put(5, null); Set keys = map.keySet(); Integer[] arr = keys.toArray(new Integer[0]); for (int i = 0; i < arr.length; i++) { assertEquals(new Integer(i + 1), arr[i]); } }Aquí, simplemente estamos haciendo una prueba rudimentaria y no concluyente sobre el orden de las entradas en el mapa hash vinculado.
Podemos garantizar que esta prueba siempre se aprobará ya que siempre se mantendrá el pedido de inserción. No podemos ofrecer la misma garantía para un HashMap.
Este atributo puede ser de gran ventaja en una API que recibe cualquier mapa, hace una copia para manipularlo y lo devuelve al código de llamada. Si el cliente necesita que el mapa devuelto se ordene de la misma manera antes de llamar a la API, entonces un mapa hash vinculado es el camino a seguir.
El orden de inserción no se ve afectado si se vuelve a insertar una clave en el mapa.
4. Orden de acceso LinkedHashMap
LinkedHashMap proporciona un constructor especial que nos permite especificar, entre el factor de carga personalizado (LF) y la capacidad inicial, un mecanismo / estrategia de ordenación diferente llamado orden de acceso :
LinkedHashMap map = new LinkedHashMap(16, .75f, true);El primer parámetro es la capacidad inicial, seguido del factor de carga y el último parámetro es el modo de pedido . Entonces, al pasar verdadero , activamos el orden de acceso, mientras que el valor predeterminado era el orden de inserción.
Este mecanismo garantiza que el orden de iteración de los elementos es el orden en el que se accedió por última vez a los elementos, desde el acceso menos reciente hasta el acceso más reciente.
Por lo tanto, crear un caché de uso menos reciente (LRU) es bastante fácil y práctico con este tipo de mapa. Una operación put u get exitosa da como resultado un acceso para la entrada:
@Test public void givenLinkedHashMap_whenAccessOrderWorks_thenCorrect() { LinkedHashMap map = new LinkedHashMap(16, .75f, true); map.put(1, null); map.put(2, null); map.put(3, null); map.put(4, null); map.put(5, null); Set keys = map.keySet(); assertEquals("[1, 2, 3, 4, 5]", keys.toString()); map.get(4); assertEquals("[1, 2, 3, 5, 4]", keys.toString()); map.get(1); assertEquals("[2, 3, 5, 4, 1]", keys.toString()); map.get(3); assertEquals("[2, 5, 4, 1, 3]", keys.toString()); }Observe cómo se transforma el orden de los elementos en el conjunto de claves a medida que realizamos operaciones de acceso en el mapa.
En pocas palabras, cualquier operación de acceso en el mapa da como resultado un orden tal que el elemento al que se accedió aparecería en último lugar si se realizara una iteración de inmediato.
Después de los ejemplos anteriores, debería ser obvio que una operación putAll genera un acceso de entrada para cada una de las asignaciones en el mapa especificado.
Naturalmente, la iteración sobre una vista del mapa no afecta el orden de iteración del mapa de respaldo; solo las operaciones de acceso explícito en el mapa afectarán el orden .
LinkedHashMap también proporciona un mecanismo para mantener un número fijo de asignaciones y seguir eliminando las entradas más antiguas en caso de que sea necesario agregar una nueva.
El método removeEldestEntry puede anularse para hacer cumplir esta política para eliminar asignaciones obsoletas automáticamente.
Para ver esto en la práctica, creemos nuestra propia clase de mapa hash vinculado, con el único propósito de hacer cumplir la eliminación de asignaciones obsoletas mediante la extensión de LinkedHashMap :
public class MyLinkedHashMap extends LinkedHashMap { private static final int MAX_ENTRIES = 5; public MyLinkedHashMap( int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor, accessOrder); } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_ENTRIES; } }Nuestra anulación anterior permitirá que el mapa crezca hasta un tamaño máximo de 5 entradas. Cuando el tamaño supere ese valor, cada nueva entrada se insertará a costa de perder la entrada más antigua en el mapa, es decir, la entrada cuya hora de último acceso precede a todas las demás entradas:
@Test public void givenLinkedHashMap_whenRemovesEldestEntry_thenCorrect() { LinkedHashMap map = new MyLinkedHashMap(16, .75f, true); map.put(1, null); map.put(2, null); map.put(3, null); map.put(4, null); map.put(5, null); Set keys = map.keySet(); assertEquals("[1, 2, 3, 4, 5]", keys.toString()); map.put(6, null); assertEquals("[2, 3, 4, 5, 6]", keys.toString()); map.put(7, null); assertEquals("[3, 4, 5, 6, 7]", keys.toString()); map.put(8, null); assertEquals("[4, 5, 6, 7, 8]", keys.toString()); }Observe cómo las entradas más antiguas al comienzo del conjunto de claves siguen disminuyendo a medida que agregamos nuevas al mapa.
5. Consideraciones de rendimiento
Al igual que HashMap , LinkedHashMap realiza las operaciones básicas de mapa de agregar, eliminar y contener en tiempo constante, siempre que la función hash esté bien dimensionada. También acepta una clave nula y valores nulos.
Sin embargo, es probable que este rendimiento de tiempo constante de LinkedHashMap sea un poco peor que el de tiempo constante de HashMap debido a la sobrecarga adicional de mantener una lista doblemente vinculada.
La iteración sobre las vistas de colección de LinkedHashMap también toma un tiempo lineal O (n) similar al de HashMap . Por otro lado, el rendimiento de tiempo lineal de LinkedHashMap durante la iteración es mejor que el tiempo lineal de HashMap .
Esto se debe a que, para LinkedHashMap , n en O (n) es solo el número de entradas en el mapa independientemente de la capacidad. Considerando que, para HashMap , n es la capacidad y el tamaño sumado, O (tamaño + capacidad).
Load Factor and Initial Capacity are defined precisely as for HashMap. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for LinkedHashMap than for HashMap, as iteration times for this class are unaffected by capacity.
6. Concurrency
Just like HashMap, LinkedHashMap implementation is not synchronized. So if you are going to access it from multiple threads and at least one of these threads is likely to change it structurally, then it must be externally synchronized.
It's best to do this at creation:
Map m = Collections.synchronizedMap(new LinkedHashMap());The difference with HashMap lies in what entails a structural modification. In access-ordered linked hash maps, merely calling the get API results in a structural modification. Alongside this, are operations like put and remove.
7. Conclusion
In this article, we have explored Java LinkedHashMap class as one of the foremost implementations of Map interface in terms of usage. We have also explored its internal workings in terms of the difference from HashMap which is its superclass.
Hopefully, after having read this post, you can make more informed and effective decisions as to which Map implementation to employ in your use case.
El código fuente completo de todos los ejemplos utilizados en este artículo se puede encontrar en el proyecto GitHub.