In this post series, we are going to talk about a common data structure named Map, and its implementations HashMap and TreeMap, and how to choose when to use each of them.

In this particular post, we are going to introduce the bases regarding Map and its implementations.

TRY IT YOURSELF: You can find the source code of this post here.

Java Collections Map Series

• Part 1: Java Collections: Map (You are here)
• Part 2: HashMap vs TreeMap: Get and Contains key
• Part 3: HashMap vs TreeMap: Put

If you like this post and are interested in hearing more about my journey as a Software Engineer, you can follow me on Twitter and travel together.

What is a Map?

A Map is a collection of values, each of them identified by a key, with the following features:

• The key is unique, and depending on the implementation, could be null.
• One key can map to at most one value.
• To access the value, you need to know exactly which key is associated.
• A value and its key, together, is named Entry.

The following image is an example of how a map is structured at high level:

We can see in the example a Map of classroom and subject for a school. In this case, in the classroom A, we see the Math subject, in the classroom B, we see the Geo subject, and in the classroom C, we see the Art subject.

To know which subject you have in a classroom, you need to know exactly the classroom key (A, B, or C), otherwise, you cannot access the value (Math, Geo, or Art).

NOTE: A Map is usually mutable, this means, some operations against a Map, will change its internal state.

Now, let’s discuss how Java defines a Map.

The Map Java Interface

Well, Java has a Map interface:

NOTE: We are not showing the whole bunch of methods, only the most used.

Something interesting to notice, Map doesn’t inherit from Collection, however, it is part of the Collections framework of Java.

Let’s see the Map methods:

• put(key, value): Insert a value identified by the key.
• get(key): Get the value related with the key.
• remove(key): Remove the key and its associated value
• containsKey(key): Check if the key exists in the Map
• keySet(): Return the whole keys existing in the Map, as a Set.
• values(): Return the collection of values existing in the Map.
• entrySet(): Return the collection of entries, pairs key and value, existing in the Map.

NOTE: containsKey and remove uses the equals method on the key object to compare, you must override it in your classes to get this working correctly.

entrySet(), keySet() and values() allows us to access the elements of the Map as a whole.

Key is a main part of the Map, it is the only way to access the majority of operations. This key could be any object, but, needs to implement equals() and hashCode(), let’s see what that means.

Equals and Hashcode Methods

equals() and hashCode() are two methods inherited from Object class. It is always a good practice to override them on all the classes, and one of the reasons are Collections, and in this case, Maps, which rely on both methods to define the internal distributions of its entries.

Let’s see how they work.

boolean equals(object)

This method receives an object and define if that object is equal to the current one. Usually we compare field by field to decide if they are equal, as the following Person class shows us:

public class Person {
  private final String firstName;
  private final String lastName;
  private final LocalDate birthDate;

.....

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass())
      return false;
    Person person = (Person) o;
    return Objects
            .equals(firstName, person.firstName) &&
            Objects
                    .equals(lastName,
                            person.lastName) &&
            Objects
                    .equals(birthDate,
                            person.birthDate);
  }

.....

}

There, we can see the equals method for the Person class, checking the firstName, lastName and birthDate. If all are equal, the two Person objects are equal.

int hashCode()

This method generates an integer number from the object properties. This number is a “summary”, a numeric representation of the object. Two different object could have the same hash code despite of having different internal state, and that’s okay. To guarantee a unique number for any object on its context, you will need to use a hashing algorithm, however, those are costly and might be unnecessary.

The following is an example of the hash code for the Person class:

public class Person {
  private final String firstName;
  private final String lastName;
  private final LocalDate birthDate;

.....

  @Override
  public int hashCode() {
    return Objects
            .hash(firstName, lastName, birthDate);
  }

.....

}

The code doesn’t say much, as we use Objects.hash to abstract that process, so, let’s see the Objects.hash implementation:

public static int hashCode(Object[] a) {
    if (a == null) {
      return 0;
    } else {
      int result = 1;
      Object[] var2 = a;
      int var3 = a.length;

      for(int var4 = 0; var4 < var3; ++var4) {
        Object element = var2[var4];
        result = 31 * result + (element == null ? 0 : element.hashCode());
      }

      return result;
    }
  }

There, we can see a math operacion, using the 31 prime number, and the hash code of each element it’s being evaluated (firstName, lastName, birthDate).

The distribution of this math operation is usually enough for the typical use cases on enterprise applications. That means, the number generated is distributed through the integer range space in a way that they don’t collide, or generate the same value.

Having defined those two important methods, let’s see how the HashMap and TreeMap implementation work.

The HashMap Implementation

Well, Java has a Map implementation named HashMap. This implementation looks like this:

There, we can see two main components, an array, and a linked list. Each array position has a linked list associated. Those linked list contain entries (key and value pairs), where each entry references to the next entry in the list.

The location of an entry into the array is defined by the hash code of its key, plus some other math operations we will discuss in following posts.

A HashMap has two other important numbers:

• Initial capacity: The initial size of the array.
• Load factor: A factor, telling when the array needs to be resized, due to a lot of entries are being pushed, and the indexes are getting filled, which degrades the performance of the HashMap (This is the density of the HashMap). Ideally, one position should belong to one entry, however, this is costly on space use.

Those two values are used when the use case requires a performance improvement, however, most of the time, the default values are enough. You can define them when you instantiate the HashMap.

The TreeMap Implementation

Java has a Map implementation named TreeMap. This implementation is based on the Red Black algorithm and looks like this:

Red Black tree is a kind of self-balancing binary search tree, that means, each node can only have two children, and they are organized based on a sorting criteria using the entry key. The binary tree could be unbalance in a moment of time, besides, the tree reorganized its entries when you add or remove elements.

By default, a TreeMap uses the natural order of the key (Comparable interface) to sort, however, you can create a TreeMap with a Comparator where you define explicitly how you want the TreeMap to sort the entries.

If the key doesn’t implement one of those interfaces, the TreeMap will throw exceptions.

Map Example

Well, let’s see how those maps work:

NOTE: You will see the TreeMap instantiation commented. If you replace the list from an HashMap to a TreeMap, the code will compile fine and the test will run green. That is the power of Polymorphism….

TRY IT YOURSELF: You can find the source code of this post here.

First, we define the map on the @Before method, and put a entry A -> Math there.

public class MapTest {
  private Map signaturesByClassroom;

  @Before
  public void before() {
    signaturesByClassroom = new HashMap();
//  signaturesByClassroom = new TreeMap();

    signaturesByClassroom.put("A", "Math");
  }

Now, let’s see an example of each of the main methods.

put(key, value)

@Test
  public void put_newElement_mapChanged() {
    signaturesByClassroom.put("C", "Art");

    assertThat(signaturesByClassroom.get("C"))
            .isEqualTo("Art");
  }

get(key)

  @Test
  public void get_oldElement() {
    assertThat(signaturesByClassroom.get("A"))

            .isEqualTo("Math");
  }

remove(key)

  @Test
  public void remove_element_true() {
    assertThat(signaturesByClassroom.remove("A"))
            .isEqualTo("Math");
  }

containsKey(key)

  @Test
  public void containsKey_element_true() {
    boolean result = signaturesByClassroom
            .containsKey("A");

    assertThat(result).isTrue();
  }

keySet()

  @Test
  public void keySet() {
    Set keySet = signaturesByClassroom
            .keySet();

    assertThat(new ArrayList(keySet)).isEqualTo(
            Arrays.asList("A"));
  }

values()

  @Test
  public void values() {
    Collection values = signaturesByClassroom
            .values();

    assertThat(new ArrayList(values)).isEqualTo(
            Arrays.asList("Math"));
  }

entrySet()

  @Test
  public void entries() {
    Set<Map.Entry> entries = signaturesByClassroom
            .entrySet();

    assertThat(new ArrayList(entries)).isEqualTo(
            Arrays.asList(new AbstractMap.SimpleImmutableEntry("A", "Math")));
  }

Final Thought

We always need Maps in our projects, doesn’t matter if the project is huge or small. Understanding how the maps’ implementations work is pretty useful when you need to pay attention to performance or memory issues.

There is not a right or wrong map, there are only some advantages or disadvantages regarding different use cases.

In the following posts, we are going to talk about different uses cases and how an HashMap and TreeMap behave.

If you liked this post and are interested in hearing more about my journey as a Software Engineer, you can follow me on Twitter and travel together.