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()
returnstrue
if the map does not contain elements andfalse
otherwise;void clear()
removes all elements from the map.
Keys and values processing:
V put(K key, V value)
associates the specifiedvalue
with the specifiedkey
and returns the previously associated value with thiskey
ornull
;V get(Object key)
returns the value associated with the key, ornull
otherwise;V remove(Object key
) removes the mapping for akey
from the map;boolean containsKey(Object key)
returnstrue
if the map contains the specifiedkey
;boolean containsValue(Object value)
returnstrue
if the map contains the specifiedvalue
.
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 tonull
) and returnnull
, otherwise, returns the current value;V getOrDefault(Object key, V defaultValue)
returns the value to which the specified key is mapped, ordefaultValue
if this map contains no mapping for the key.
Methods which return other collections:
Set<K> keySet()
Returns aSet
view of the keys contained in this map;Collection<V> values()
returns aCollection
view of the values contained in this map;Set<Map.Entry<K, V>> entrySet()
returns aSet
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 ornull
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 thantoKey
;SortedMap<K, V> tailMap(K fromKey)
returns a submap containing elements whose keys are greater than or equal tofromKey
;SortedMap<K, V> subMap(K fromKey, E toKey)
returns a submap containing elements whose keys are in rangefromKey
(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":