Eine Anleitung zu Java HashMap

1. Übersicht

In diesem Artikel erfahren Sie, wie Sie HashMap in Java verwenden und wie es intern funktioniert.

Eine Klasse, die HashMap sehr ähnlich ist, ist Hashtable . In einigen unserer anderen Artikel erfahren Sie mehr über die Klasse java.util.Hashtable selbst und die Unterschiede zwischen HashMap und Hashtable .

2. Grundlegende Verwendung

Schauen wir uns zunächst an, was es bedeutet, dass HashMap eine Karte ist. Eine Zuordnung ist eine Schlüsselwertzuordnung. Dies bedeutet, dass jeder Schlüssel genau einem Wert zugeordnet ist und dass wir den Schlüssel verwenden können, um den entsprechenden Wert aus einer Zuordnung abzurufen.

Man könnte sich fragen, warum man den Wert nicht einfach einer Liste hinzufügt. Warum brauchen wir eine HashMap ? Der einfache Grund ist die Leistung. Wenn wir ein bestimmtes Element in einer Liste finden möchten, ist die Zeitkomplexität O (n), und wenn die Liste sortiert ist, ist es O (log n), indem beispielsweise eine binäre Suche verwendet wird.

Der Vorteil einer HashMap besteht darin, dass die zeitliche Komplexität zum Einfügen und Abrufen eines Werts im Durchschnitt O (1) beträgt. Wir werden uns später ansehen, wie dies erreicht werden kann. Schauen wir uns zunächst an, wie HashMap verwendet wird .

2.1. Konfiguration

Erstellen wir eine einfache Klasse, die wir im gesamten Artikel verwenden werden:

public class Product { private String name; private String description; private List tags; // standard getters/setters/constructors public Product addTagsOfOtherProdcut(Product product) { this.tags.addAll(product.getTags()); return this; } }

2.2. Stellen

Wir können jetzt eine HashMap mit dem Schlüssel vom Typ String und Elementen vom Typ Product erstellen :

Map productsByName = new HashMap(); 

Und fügen Sie unserer HashMap Produkte hinzu :

Product eBike = new Product("E-Bike", "A bike with a battery"); Product roadBike = new Product("Road bike", "A bike for competition"); productsByName.put(eBike.getName(), eBike); productsByName.put(roadBike.getName(), roadBike); 

2.3. Bekommen

Wir können einen Wert von der Karte anhand seines Schlüssels abrufen:

Product nextPurchase = productsByName.get("E-Bike"); assertEquals("A bike with a battery", nextPurchase.getDescription());

Wenn wir versuchen, einen Wert für einen Schlüssel zu finden, der in der Map nicht vorhanden ist, erhalten wir einen Nullwert :

Product nextPurchase = productsByName.get("Car"); assertNull(nextPurchase);

Und wenn wir einen zweiten Wert mit demselben Schlüssel einfügen, erhalten wir nur den zuletzt eingefügten Wert für diesen Schlüssel:

Product newEBike = new Product("E-Bike", "A bike with a better battery"); productsByName.put(newEBike.getName(), newEBike); assertEquals("A bike with a better battery", productsByName.get("E-Bike").getDescription());

2.4. Null als Schlüssel

Mit HashMap können wir auch null als Schlüssel verwenden:

Product defaultProduct = new Product("Chocolate", "At least buy chocolate"); productsByName.put(null, defaultProduct); Product nextPurchase = productsByName.get(null); assertEquals("At least buy chocolate", nextPurchase.getDescription());

2.5. Werte mit demselben Schlüssel

Außerdem können wir dasselbe Objekt zweimal mit einem anderen Schlüssel einfügen:

productsByName.put(defaultProduct.getName(), defaultProduct); assertSame(productsByName.get(null), productsByName.get("Chocolate"));

2.6. Entfernen Sie einen Wert

Wir können eine Schlüsselwertzuordnung aus der HashMap entfernen :

productsByName.remove("E-Bike"); assertNull(productsByName.get("E-Bike"));

2.7. Überprüfen Sie, ob ein Schlüssel oder Wert in der Karte vorhanden ist

Um zu überprüfen, ob ein Schlüssel in der Karte vorhanden ist, können wir die Methode includesKey () verwenden:

productsByName.containsKey("E-Bike");

Um zu überprüfen, ob ein Wert in der Karte vorhanden ist, können Sie die Methode includesValue () verwenden:

productsByName.containsValue(eBike);

Beide Methodenaufrufe geben in unserem Beispiel true zurück. Obwohl sie sehr ähnlich aussehen, gibt es einen wichtigen Leistungsunterschied zwischen diesen beiden Methodenaufrufen. Die Komplexität zum Überprüfen, ob ein Schlüssel vorhanden ist, ist O (1) , während die Komplexität zum Überprüfen für ein Element O (n) ist, da alle Elemente in der Karte durchlaufen werden müssen.

2.8. Iterieren über eine HashMap

Es gibt drei grundlegende Möglichkeiten, um alle Schlüssel-Wert-Paare in einer HashMap zu durchlaufen .

Wir können den Satz aller Schlüssel durchlaufen:

for(String key : productsByName.keySet()) { Product product = productsByName.get(key); }

Oder wir können die Menge aller Einträge durchlaufen:

for(Map.Entry entry : productsByName.entrySet()) { Product product = entry.getValue(); String key = entry.getKey(); //do something with the key and value }

Schließlich können wir alle Werte durchlaufen:

List products = new ArrayList(productsByName.values());

3. Der Schlüssel

Wir können jede Klasse als Schlüssel in unserer HashMap verwenden . Damit die Map ordnungsgemäß funktioniert, müssen wir jedoch eine Implementierung für equals () und hashCode () bereitstellen . Angenommen, wir möchten eine Karte mit dem Produkt als Schlüssel und dem Preis als Wert haben:

HashMap priceByProduct = new HashMap(); priceByProduct.put(eBike, 900);

Implementieren wir die Methoden equals () und hashCode () :

@Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } Product product = (Product) o; return Objects.equals(name, product.name) && Objects.equals(description, product.description); } @Override public int hashCode() { return Objects.hash(name, description); }

Beachten Sie, dass hashCode () und equals () nur für Klassen überschrieben werden müssen, die wir als Zuordnungsschlüssel verwenden möchten, nicht für Klassen, die nur als Werte in einer Zuordnung verwendet werden. Wir werden in Abschnitt 5 dieses Artikels sehen, warum dies notwendig ist.

4. Additional Methods as of Java 8

Java 8 added several functional-style methods to HashMap. In this section, we'll look at some of these methods.

For each method, we'll look at two examples. The first example shows how to use the new method, and the second example shows how to achieve the same in earlier versions of Java.

As these methods are quite straightforward, we won't look at more detailed examples.

4.1. forEach()

The forEach method is the functional-style way to iterate over all elements in the map:

productsByName.forEach( (key, product) -> { System.out.println("Key: " + key + " Product:" + product.getDescription()); //do something with the key and value }); 

Prior to Java 8:

for(Map.Entry entry : productsByName.entrySet()) { Product product = entry.getValue(); String key = entry.getKey(); //do something with the key and value }

Our article Guide to the Java 8 forEach covers the forEach loop in greater detail.

4.2. getOrDefault()

Using the getOrDefault() method, we can get a value from the map or return a default element in case there is no mapping for the given key:

Product chocolate = new Product("chocolate", "something sweet"); Product defaultProduct = productsByName.getOrDefault("horse carriage", chocolate); Product bike = productsByName.getOrDefault("E-Bike", chocolate);

Prior to Java 8:

Product bike2 = productsByName.containsKey("E-Bike") ? productsByName.get("E-Bike") : chocolate; Product defaultProduct2 = productsByName.containsKey("horse carriage") ? productsByName.get("horse carriage") : chocolate; 

4.3. putIfAbsent()

With this method, we can add a new mapping, but only if there is not yet a mapping for the given key:

productsByName.putIfAbsent("E-Bike", chocolate); 

Prior to Java 8:

if(productsByName.containsKey("E-Bike")) { productsByName.put("E-Bike", chocolate); }

Our article Merging Two Maps with Java 8 takes a closer look at this method.

4.4. merge()

And with merge(), we can modify the value for a given key if a mapping exists, or add a new value otherwise:

Product eBike2 = new Product("E-Bike", "A bike with a battery"); eBike2.getTags().add("sport"); productsByName.merge("E-Bike", eBike2, Product::addTagsOfOtherProdcut);

Prior to Java 8:

if(productsByName.containsKey("E-Bike")) { productsByName.get("E-Bike").addTagsOfOtherProdcut(eBike2); } else { productsByName.put("E-Bike", eBike2); } 

4.5. compute()

With the compute() method, we can compute the value for a given key:

productsByName.compute("E-Bike", (k,v) -> { if(v != null) { return v.addTagsOfOtherProdcut(eBike2); } else { return eBike2; } });

Prior to Java 8:

if(productsByName.containsKey("E-Bike")) { productsByName.get("E-Bike").addTagsOfOtherProdcut(eBike2); } else { productsByName.put("E-Bike", eBike2); } 

It's worth noting that the methods merge() and compute() are quite similar. The compute() method accepts two arguments: the key and a BiFunction for the remapping. And merge() accepts three parameters: the key, a default value to add to the map if the key doesn't exist yet, and a BiFunction for the remapping.

5. HashMap Internals

In this section, we'll look at how HashMap works internally and what are the benefits of using HashMap instead of a simple list, for example.

As we've seen, we can retrieve an element from a HashMap by its key. One approach would be to use a list, iterate over all elements, and return when we find an element for which the key matches. Both the time and space complexity of this approach would be O(n).

With HashMap, we can achieve an average time complexity of O(1) for the put and get operations and space complexity of O(n). Let's see how that works.

5.1. The Hash Code and Equals

Instead of iterating over all its elements, HashMap attempts to calculate the position of a value based on its key.

The naive approach would be to have a list that can contain as many elements as there are keys possible. As an example, let's say our key is a lower-case character. Then it's sufficient to have a list of size 26, and if we want to access the element with key ‘c', we'd know that it's the one at position 3, and we can retrieve it directly.

However, this approach would not be very effective if we have a much bigger keyspace. For example, let's say our key was an integer. In this case, the size of the list would have to be 2,147,483,647. In most cases, we would also have far fewer elements, so a big part of the allocated memory would remain unused.

HashMap stores elements in so-called buckets and the number of buckets is called capacity.

When we put a value in the map, the key's hashCode() method is used to determine the bucket in which the value will be stored.

To retrieve the value, HashMap calculates the bucket in the same way – using hashCode(). Then it iterates through the objects found in that bucket and use key's equals() method to find the exact match.

5.2. Keys' Immutability

In most cases, we should use immutable keys. Or at least, we must be aware of the consequences of using mutable keys.

Let's see what happens when our key changes after we used it to store a value in a map.

For this example, we'll create the MutableKey:

public class MutableKey { private String name; // standard constructor, getter and setter @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } MutableKey that = (MutableKey) o; return Objects.equals(name, that.name); } @Override public int hashCode() { return Objects.hash(name); } }

And here goes the test:

MutableKey key = new MutableKey("initial"); Map items = new HashMap(); items.put(key, "success"); key.setName("changed"); assertNull(items.get(key));

As we can see, we're no longer able to get the corresponding value once the key has changed, instead, null is returned. This is because HashMap is searching in the wrong bucket.

The above test case may be surprising if we don't have a good understanding of how HashMap works internally.

5.3. Collisions

For this to work correctly, equal keys must have the same hash, however, different keys can have the same hash. If two different keys have the same hash, the two values belonging to them will be stored in the same bucket. Inside a bucket, values are stored in a list and retrieved by looping over all elements. The cost of this is O(n).

As of Java 8 (see JEP 180), the data structure in which the values inside one bucket are stored is changed from a list to a balanced tree if a bucket contains 8 or more values, and it's changed back to a list if, at some point, only 6 values are left in the bucket. This improves the performance to be O(log n).

5.4. Capacity and Load Factor

To avoid having many buckets with multiple values, the capacity is doubled if 75% (the load factor) of the buckets become non-empty. The default value for the load factor is 75%, and the default initial capacity is 16. Both can be set in the constructor.

5.5. Summary of put and get Operations

Let's summarize how the put and get operations work.

When we add an element to the map,HashMap calculates the bucket. If the bucket already contains a value, the value is added to the list (or tree) belonging to that bucket. If the load factor becomes bigger than the maximum load factor of the map, the capacity is doubled.

When we want to get a value from the map,HashMap calculates the bucket and gets the value with the same key from the list (or tree).

6. Conclusion

In diesem Artikel haben wir gesehen, wie eine HashMap verwendet wird und wie sie intern funktioniert. Zusammen mit ArrayList ist HashMap eine der am häufigsten verwendeten Datenstrukturen in Java. Daher ist es sehr praktisch, gute Kenntnisse über die Verwendung und die Funktionsweise unter der Haube zu haben. Unser Artikel Die Java HashMap unter der Haube behandelt die Interna von HashMap ausführlicher.

Wie üblich ist der vollständige Quellcode auf Github verfügbar.