El Java HashMap bajo el capó

1. Información general

En este artículo, vamos a explorar la implementación más popular de la interfaz de mapa del marco de colecciones de Java con más detalle, retomando donde lo dejó nuestro artículo de introducción.

Antes de comenzar con la implementación, es importante señalar que las interfaces principales de la colección List y Set extienden Collection, pero Map no.

En pocas palabras, HashMap almacena valores por clave y proporciona API para agregar, recuperar y manipular datos almacenados de varias maneras. La implementación se basa en los principios de una tabla hash , que suena un poco compleja al principio, pero en realidad es muy fácil de entender.

Los pares clave-valor se almacenan en lo que se conoce como depósitos, que juntos forman lo que se llama una tabla, que en realidad es una matriz interna.

Una vez que conocemos la clave bajo la cual se almacena o se almacenará un objeto, las operaciones de almacenamiento y recuperación ocurren en un tiempo constante , O (1) en un mapa hash bien dimensionado.

Para comprender cómo funcionan los mapas hash bajo el capó, es necesario comprender el mecanismo de almacenamiento y recuperación empleado por HashMap. Nos centraremos mucho en estos.

Finalmente, las preguntas relacionadas con HashMap son bastante comunes en las entrevistas , por lo que esta es una forma sólida de preparar una entrevista o prepararse para ella.

2. La API put ()

Para almacenar un valor en un mapa hash, llamamos a la API put que toma dos parámetros; una clave y el valor correspondiente:

V put(K key, V value);

Cuando se agrega un valor al mapa bajo una clave, se llama a la API hashCode () del objeto clave para recuperar lo que se conoce como el valor hash inicial.

Para ver esto en acción, creemos un objeto que actuará como clave. Solo crearemos un único atributo para usar como código hash para simular la primera fase del hash:

public class MyKey { private int id; @Override public int hashCode() { System.out.println("Calling hashCode()"); return id; } // constructor, setters and getters }

Ahora podemos usar este objeto para mapear un valor en el mapa hash:

@Test public void whenHashCodeIsCalledOnPut_thenCorrect() { MyKey key = new MyKey(1); Map map = new HashMap(); map.put(key, "val"); }

No pasa mucho en el código anterior, pero preste atención a la salida de la consola. De hecho , se invoca el método hashCode :

Calling hashCode()

A continuación, se llama internamente a la API hash () del mapa hash para calcular el valor hash final utilizando el valor hash inicial.

Este valor hash final finalmente se reduce a un índice en la matriz interna o lo que llamamos una ubicación de depósito.

La función hash de HashMap se ve así:

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

Lo que debemos tener en cuenta aquí es solo el uso del código hash del objeto clave para calcular un valor hash final.

Mientras está dentro de la función put , el valor hash final se usa así:

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

Observe que se llama a una función putVal interna y se le da el valor hash final como primer parámetro.

Uno puede preguntarse por qué la clave se usa nuevamente dentro de esta función, ya que ya la hemos usado para calcular el valor hash.

La razón es que los mapas hash almacenan tanto la clave como el valor en la ubicación del depósito como un objeto Map.Entry .

Como se mencionó anteriormente, todas las interfaces del marco de colecciones de Java amplían la interfaz de la colección , pero Map no. Compare la declaración de la interfaz Map que vimos anteriormente con la de la interfaz Set :

public interface Set extends Collection

La razón es que los mapas no almacenan exactamente elementos individuales como lo hacen otras colecciones, sino más bien una colección de pares clave-valor.

Entonces, los métodos genéricos de la interfaz de Colección , como add , toArray , no tienen sentido cuando se trata de Map .

El concepto que hemos cubierto en los últimos tres párrafos constituye una de las preguntas de entrevista más populares de Java Collections Framework . Entonces, vale la pena entenderlo.

Un atributo especial con el mapa hash es que acepta nulos valores y claves nulas:

@Test public void givenNullKeyAndVal_whenAccepts_thenCorrect(){ Map map = new HashMap(); map.put(null, null); }

Cuando se encuentra una clave nula durante una operación de colocación , se le asigna automáticamente un valor hash final de 0 , lo que significa que se convierte en el primer elemento de la matriz subyacente.

Esto también significa que cuando la clave es nula, no hay operación de hash y, por lo tanto, no se invoca la API hashCode de la clave, evitando finalmente una excepción de puntero nulo.

Durante una operación put , cuando usamos una clave que ya se usó anteriormente para almacenar un valor, devuelve el valor anterior asociado con la clave:

@Test public void givenExistingKey_whenPutReturnsPrevValue_thenCorrect() { Map map = new HashMap(); map.put("key1", "val1"); String rtnVal = map.put("key1", "val2"); assertEquals("val1", rtnVal); }

de lo contrario, devuelve nulo:

@Test public void givenNewKey_whenPutReturnsNull_thenCorrect() { Map map = new HashMap(); String rtnVal = map.put("key1", "val1"); assertNull(rtnVal); }

Cuando se pone devuelve nulo, también podría significar que el valor anterior asociado con la clave es nulo, no necesariamente que sea una nueva asignación de clave-valor:

@Test public void givenNullVal_whenPutReturnsNull_thenCorrect() { Map map = new HashMap(); String rtnVal = map.put("key1", null); assertNull(rtnVal); }

La API containsKey se puede utilizar para distinguir entre estos escenarios, como veremos en la siguiente subsección.

3. La API get

Para recuperar un objeto ya almacenado en el mapa hash, debemos conocer la clave bajo la cual se almacenó. Llamamos a la API get y le pasamos el objeto clave:

@Test public void whenGetWorks_thenCorrect() { Map map = new HashMap(); map.put("key", "val"); String val = map.get("key"); assertEquals("val", val); }

Internamente, se utiliza el mismo principio de hash. Se llama a la API hashCode () del objeto clave para obtener el valor hash inicial:

@Test public void whenHashCodeIsCalledOnGet_thenCorrect() { MyKey key = new MyKey(1); Map map = new HashMap(); map.put(key, "val"); map.get(key); }

Esta vez, se llama dos veces a la API hashCode de MyKey ; una vez para poner y una vez para conseguir :

Calling hashCode() Calling hashCode()

Luego, este valor se repite llamando a la API interna de hash () para obtener el valor hash final.

As we saw in the previous section, this final hash value ultimately boils down to a bucket location or an index of the internal array.

The value object stored in that location is then retrieved and returned to the calling function.

When the returned value is null, it could mean that the key object is not associated with any value in the hash map:

@Test public void givenUnmappedKey_whenGetReturnsNull_thenCorrect() { Map map = new HashMap(); String rtnVal = map.get("key1"); assertNull(rtnVal); }

Or it could simply mean that the key was explicitly mapped to a null instance:

@Test public void givenNullVal_whenRetrieves_thenCorrect() { Map map = new HashMap(); map.put("key", null); String val=map.get("key"); assertNull(val); }

To distinguish between the two scenarios, we can use the containsKey API, to which we pass the key and it returns true if and only if a mapping was created for the specified key in the hash map:

@Test public void whenContainsDistinguishesNullValues_thenCorrect() { Map map = new HashMap(); String val1 = map.get("key"); boolean valPresent = map.containsKey("key"); assertNull(val1); assertFalse(valPresent); map.put("key", null); String val = map.get("key"); valPresent = map.containsKey("key"); assertNull(val); assertTrue(valPresent); }

For both cases in the above test, the return value of the get API call is null but we are able to distinguish which one is which.

4. Collection Views in HashMap

HashMap offers three views that enable us to treat its keys and values as another collection. We can get a set of all keys of the map:

@Test public void givenHashMap_whenRetrievesKeyset_thenCorrect() { Map map = new HashMap(); map.put("name", "baeldung"); map.put("type", "blog"); Set keys = map.keySet(); assertEquals(2, keys.size()); assertTrue(keys.contains("name")); assertTrue(keys.contains("type")); }

The set is backed by the map itself. So any change made to the set is reflected in the map:

@Test public void givenKeySet_whenChangeReflectsInMap_thenCorrect() { Map map = new HashMap(); map.put("name", "baeldung"); map.put("type", "blog"); assertEquals(2, map.size()); Set keys = map.keySet(); keys.remove("name"); assertEquals(1, map.size()); }

We can also obtain a collection view of the values:

@Test public void givenHashMap_whenRetrievesValues_thenCorrect() { Map map = new HashMap(); map.put("name", "baeldung"); map.put("type", "blog"); Collection values = map.values(); assertEquals(2, values.size()); assertTrue(values.contains("baeldung")); assertTrue(values.contains("blog")); }

Just like the key set, any changes made in this collection will be reflected in the underlying map.

Finally, we can obtain a set view of all entries in the map:

@Test public void givenHashMap_whenRetrievesEntries_thenCorrect() { Map map = new HashMap(); map.put("name", "baeldung"); map.put("type", "blog"); Set
    
      entries = map.entrySet(); assertEquals(2, entries.size()); for (Entry e : entries) }
    

Remember that a hash map specifically contains unordered elements, therefore we assume any order when testing the keys and values of entries in the for each loop.

Many times, you will use the collection views in a loop as in the last example, and more specifically using their iterators.

Just remember that the iterators for all the above views are fail-fast.

If any structural modification is made on the map, after the iterator has been created, a concurrent modification exception will be thrown:

@Test(expected = ConcurrentModificationException.class) public void givenIterator_whenFailsFastOnModification_thenCorrect() { Map map = new HashMap(); map.put("name", "baeldung"); map.put("type", "blog"); Set keys = map.keySet(); Iterator it = keys.iterator(); map.remove("type"); while (it.hasNext()) { String key = it.next(); } }

The only allowed structural modification is a remove operation performed through the iterator itself:

public void givenIterator_whenRemoveWorks_thenCorrect() { Map map = new HashMap(); map.put("name", "baeldung"); map.put("type", "blog"); Set keys = map.keySet(); Iterator it = keys.iterator(); while (it.hasNext()) { it.next(); it.remove(); } assertEquals(0, map.size()); }

The final thing to remember about these collection views is the performance of iterations. This is where a hash map performs quite poorly compared with its counterparts linked hash map and tree map.

Iteration over a hash map happens in worst case O(n) where n is the sum of its capacity and the number of entries.

5. HashMap Performance

The performance of a hash map is affected by two parameters: Initial Capacity and Load Factor. The capacity is the number of buckets or the underlying array length and the initial capacity is simply the capacity during creation.

The load factor or LF, in short, is a measure of how full the hash map should be after adding some values before it is resized.

The default initial capacity is 16 and default load factor is 0.75. We can create a hash map with custom values for initial capacity and LF:

Map hashMapWithCapacity=new HashMap(32); Map hashMapWithCapacityAndLF=new HashMap(32, 0.5f);

The default values set by the Java team are well optimized for most cases. However, if you need to use your own values, which is very okay, you need to understand the performance implications so that you know what you are doing.

When the number of hash map entries exceeds the product of LF and capacity, then rehashing occurs i.e. another internal array is created with twice the size of the initial one and all entries are moved over to new bucket locations in the new array.

A low initial capacity reduces space cost but increases the frequency of rehashing. Rehashing is obviously a very expensive process. So as a rule, if you anticipate many entries, you should set a considerably high initial capacity.

On the flip side, if you set the initial capacity too high, you will pay the cost in iteration time. As we saw in the previous section.

So a high initial capacity is good for a large number of entries coupled with little to no iteration.

A low initial capacity is good for few entries with a lot of iteration.

6. Collisions in the HashMap

A collision, or more specifically, a hash code collision in a HashMap, is a situation where two or more key objects produce the same final hash value and hence point to the same bucket location or array index.

This scenario can occur because according to the equals and hashCode contract, two unequal objects in Java can have the same hash code.

It can also happen because of the finite size of the underlying array, that is, before resizing. The smaller this array, the higher the chances of collision.

That said, it's worth mentioning that Java implements a hash code collision resolution technique which we will see using an example.

Keep in mind that it's the hash value of the key that determines the bucket the object will be stored in. And so, if the hash codes of any two keys collide, their entries will still be stored in the same bucket.

And by default, the implementation uses a linked list as the bucket implementation.

The initially constant time O(1)put and get operations will occur in linear time O(n) in the case of a collision. This is because after finding the bucket location with the final hash value, each of the keys at this location will be compared with the provided key object using the equals API.

To simulate this collision resolution technique, let's modify our earlier key object a little:

public class MyKey { private String name; private int id; public MyKey(int id, String name) { this.id = id; this.name = name; } // standard getters and setters @Override public int hashCode() { System.out.println("Calling hashCode()"); return id; } // toString override for pretty logging @Override public boolean equals(Object obj) { System.out.println("Calling equals() for key: " + obj); // generated implementation } }

Notice how we're simply returning the id attribute as the hash code – and thus force a collision to occur.

Also, note that we've added log statements in our equals and hashCode implementations – so that we know exactly when the logic is called.

Let's now go ahead to store and retrieve some objects that collide at some point:

@Test public void whenCallsEqualsOnCollision_thenCorrect() { HashMap map = new HashMap(); MyKey k1 = new MyKey(1, "firstKey"); MyKey k2 = new MyKey(2, "secondKey"); MyKey k3 = new MyKey(2, "thirdKey"); System.out.println("storing value for k1"); map.put(k1, "firstValue"); System.out.println("storing value for k2"); map.put(k2, "secondValue"); System.out.println("storing value for k3"); map.put(k3, "thirdValue"); System.out.println("retrieving value for k1"); String v1 = map.get(k1); System.out.println("retrieving value for k2"); String v2 = map.get(k2); System.out.println("retrieving value for k3"); String v3 = map.get(k3); assertEquals("firstValue", v1); assertEquals("secondValue", v2); assertEquals("thirdValue", v3); }

In the above test, we create three different keys – one has a unique id and the other two have the same id. Since we use id as the initial hash value, there will definitely be a collision during both storage and retrieval of data with these keys.

In addition to that, thanks to the collision resolution technique we saw earlier, we expect each of our stored values to be retrieved correctly, hence the assertions in the last three lines.

When we run the test, it should pass, indicating that collisions were resolved and we will use the logging produced to confirm that the collisions indeed occurred:

storing value for k1 Calling hashCode() storing value for k2 Calling hashCode() storing value for k3 Calling hashCode() Calling equals() for key: MyKey [name=secondKey, id=2] retrieving value for k1 Calling hashCode() retrieving value for k2 Calling hashCode() retrieving value for k3 Calling hashCode() Calling equals() for key: MyKey [name=secondKey, id=2]

Notice that during storage operations, k1 and k2 were successfully mapped to their values using only the hash code.

However, storage of k3 was not so simple, the system detected that its bucket location already contained a mapping for k2. Therefore, equals comparison was used to distinguish them and a linked list was created to contain both mappings.

Any other subsequent mapping whose key hashes to the same bucket location will follow the same route and end up replacing one of the nodes in the linked list or be added to the head of the list if equals comparison returns false for all existing nodes.

Likewise, during retrieval, k3 and k2 were equals-compared to identify the correct key whose value should be retrieved.

On a final note, from Java 8, the linked lists are dynamically replaced with balanced binary search trees in collision resolution after the number of collisions in a given bucket location exceed a certain threshold.

This change offers a performance boost, since, in the case of a collision, storage and retrieval happen in O(log n).

This section is very common in technical interviews, especially after the basic storage and retrieval questions.

7. Conclusion

In this article, we have explored HashMap implementation of Java Map interface.

El código fuente completo de todos los ejemplos utilizados en este artículo se puede encontrar en el proyecto GitHub.