How does a hash map work internally

Java-Tutorial.org

Maps

A map contains objects in a structured form. This data structure is in the interface java.util.Map describes which is implemented by the individual map classes. A map is structured like a dictionary. Each entry consists of a key and the associated value. Any objects can be added or removed.

Each key may only exist once in a map, which means that each key-value pair is unique. When a key-value pair is inserted into a map, an internal check is carried out beforehand to determine whether this key already exists. If this is the case, the map remains Not unchanged as with sets. The old value for the existing key is replaced by the new value.

Let's take a look at such a map in an example overview at this point.

Key Value
12345 Student {Waldfee, Holla, 12345}
12355 Student {Stilzchen, Humpel, 12355}

In the overview above you can see the key in the first column and the corresponding value in the second column. We have taken a student's matriculation number as the key, as this is unique and never duplicated. The corresponding student should be entered here as the value.

A map offers the following methods, among others

public V put (K key, V value) public V remove (Object key) publicCollection values ​​() public V get (Object key) publicboolean isEmpty ()

The method isEmpty checks whether the map is empty.

With the methods put and remove elements are added to or removed from the map. The method remove returns the value of the deleted key and the method put the value of the key of the object to be inserted, if this is already available in the map. If the key does not yet exist in the map, will zero returned.

About the method get you get the corresponding value for a certain key.

The method values returns a collection with all values ​​of the map. Changes to the collection affect the map and vice versa. The values ​​can then be accessed using an iterator.

Let's look at a small example of a HashMap (java.util.HashMap) at.

publicclass student {// attribute name and first name of a studentString name, first name; // attribute matriculation number (unique number) int matriculation number; // constructor for a student public student (string name, string first name, int matriculation number) {this.name = name; this.first name = first name; this.matriculation number = matriculation number;} // getter method for the matriculation numberpublicint getMatriculation number () {returnthis.matriculation number;}} // import instruction for our HashMapimportjava.util.HashMap; publicclass HashMapTest {// main method publicstaticvoid main (String [] args) {HashMap map = newHashMap (); // Three objects of the Student class are created Student st1 = new Student ("Topf", "Hans", 12345); Student st2 = new Student ("Teller", "Hannes", 12323); Student st3 = new Student ("Cutlery", "Maxi", 12345); // Insertion of the objects into the HashMap // Matriculation number is entered as key map.put (newInteger (st1.getMatriculation number ()), st1); map.put (newInteger (st2.getMatriculation number ()), st2); // Student st1 is replaced by st3, since the // matriculation number is already assigned as a key map.put (newInteger (st3.getMatriculation number ()), st3) ;}}

The third call to the method put leads to an exchange of the student object, since the key (here the matriculation number) is already available. The old value is then returned.

Another map is the so-called TreeMap. Objects are sorted in this map. All classes that are to serve as keys in a TreeMap must have the interface Comparable to implement. This makes objects comparable by using method compareTo implemented for its own class.

Since we have already explained the principle of the TreeList in the Sets chapter, we will forego it here, as the principle is completely transferrable.