Java
November 28, 2020

Theory: Map

In some situations, you need to store pairs of associated objects. For example, when counting the number of words in a text, the first one is a word and the second one is the number of its occurrences in the text. There is a special type of collections called map to effectively store such pairs of objects.

A map is a collection of key-value pairs. Keys are always unique while values can repeat.

A good example of a map from the real world is a phone book where keys are names of your friends and values are phones associated with them.

Maps have some similarities with sets and arrays;

  • keys of a map form a set, but each key has an associated value;
  • keys of a map are similar to indexes of an array, but the keys can have any type including integer numbers, strings and so on.

The Map interface

The Collections Framework provides the Map<K,V> interface to represent a map as an abstract data type. Here, K is a type of keys, and V is a type of associated values. The Map interface is not a subtype of the Collection interface, but maps are often considered as collections since they are part of the framework.

The interface declares a lot of methods to work with maps. Some of the methods are similar to methods of Collection, while others are unique to maps.

Collection-like methods:

  • int size() returns the number of elements in the map;
  • boolean isEmpty() returns true if the map does not contain elements and false otherwise;
  • void clear() removes all elements from the map.

Keys and values processing:

  • V put(K key, V value) associates the specified value with the specified key and returns the previously associated value with this key or null;
  • V get(Object key) returns the value associated with the key, or null otherwise;
  • V remove(Object key) removes the mapping for a key from the map;
  • boolean containsKey(Object key) returns true if the map contains the specified key;
  • boolean containsValue(Object value) returns true if the map contains the specified value.

Advanced methods:

  • V putIfAbsent(K key, V value) puts a pair if the specified key is not already associated with a value (or is mapped to null) and return null, otherwise, returns the current value;
  • V getOrDefault(Object key, V defaultValue) returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.

Methods which return other collections:

  • Set<K> keySet() Returns a Set view of the keys contained in this map;
  • Collection<V> values() returns a Collection view of the values contained in this map;
  • Set<Map.Entry<K, V>> entrySet() returns a Set view of the entries (associations) contained in this map.

This is even not a complete list of methods since Map is really a huge interface. The documentation really helps to use it.

To start using a map, you need to instantiate one of its implementations: HashMap, TreeMap, and LinkedHashMap. They use different rules for ordering elements and have some additional methods. There are also immutable maps whose names are not important for programmers.

Immutable maps

The simplest way to create a map is to invoke the of method of the Map interface. The method takes zero or any even number of arguments in the format key1, value1, key2, value2, ... and return an immutable map.

Now let's consider some operations that can be applied to immutable maps using our example with friendPhones.

The size of a map equals to the number of pairs contained in it.

It is possible to get a value from a map by its key:

Note that the getOrDefault method provides a simple way to prevent NPE since it avoids null's.

It is also possible to check whether a map contains a particular key or value by using containsKey and containsValue methods.

We can directly access the set of keys and collection of values from a map:

Since it is immutable, only methods that do not change the elements of this map will work. Others will throw an exception UnsupportedOperationException. If you'd like to put or to remove elements, use one of HashMap, TreeMap or LinkedHashMap.

HashMap

The HashMap class represents a map backed by a hash table. This implementation provides constant-time performance for get and put methods assuming the hash function disperses the elements properly among the buckets.

The following example demonstrates a map of products where key is the product code and value is the name.

This implementation is often used in practice since it is highly-optimized for putting and getting pairs.

LinkedHashMap

The LinkedHashMap stores the order in which elements were inserted.

Let's see a part of the previous example again:

In this code, the order of pairs is always the same and matches the order in which they are inserted into the map.

TreeMap

The TreeMap class represents a map that gives us guarantees on the order of the elements. It is corresponding to the sorting order of the keys determined either by their natural order (if they implement the Comparable interface) or by specific Comparator implementation.

This class implements the SortedMap interface which extends the base Map interface. It provides some new methods, related to comparisons of keys:

  • Comparator<? super K> comparator() returns the comparator used to order elements in the map or null if the map uses the natural ordering of its keys;
  • E firstKey() returns the first (lowest) key in the map;
  • E lastKey() returns the last (highest) key in the map;
  • SortedMap<K, V> headMap(K toKey) returns a submap containing elements whose keys are strictly less than toKey;
  • SortedMap<K, V> tailMap(K fromKey) returns a submap containing elements whose keys are greater than or equal to fromKey;
  • SortedMap<K, V> subMap(K fromKey, E toKey) returns a submap containing elements whose keys are in range fromKey (inclusive) toKey (exclusive);

The example below demonstrates how to create and use an object of TreeMap. This map is filled with events, each of them has a date (key) and title (value).

Use TreeMap only when you really need the sorting order of elements since this implementation is less effective than HashMap.

Iterating over maps

It is impossible to directly iterate over a map since it does not implement the Iterable interface. Fortunately, some methods of maps return other collections which are iterable. The order of elements when iterating depends on the concrete implementation of the Map interface.

The following code shows how to get keys and values in a for-each loop:

If you want to print a key and its associated value at the same iteration, you can get entrySet() and iterate over it.

The same behavior can be achieved by using a lambda expression with two arguments if you prefer this way:

Other collections as values

It is possible to store other collections as values in maps since collections are objects as well.

Here is an example with a map of synonyms:

Storing collections as keys of a map, on the other hand, is not a common case and it has some restrictions. Such keys should be represented by immutable collections. We will not consider this case here.

Map equality

Two maps are considered equal if they contain the same keys and values. Types of maps are not important.

So, the following maps are fully equal:

But the following two maps are different since the second map does not include "Alice":