Maps

Introduction#

The java.util.Map interface represents a mapping between keys and their values. A map cannot contain duplicate keys; and each key can map to at most one value.

Since Map is an interface, then you need to instantiate a concrete implementation of that interface in order to use it; there are several Map implementations, and mostly used are the java.util.HashMap and java.util.TreeMap

Remarks#

A map is an object which store keys with an associated value for each key. A key and its value are sometimes called a key/value pair or an entry. Maps typically provide these features:

Data is stored into the map in key/value pairs.
The map may contain only one entry for a particular key. If a map contains an entry with a particular key, and you try to store a second entry with the same key, then the second entry will replace the first. In other words, this will change the value associated with the key.
Maps provide fast operations to test whether a key exists in the map, to fetch the value associated with a key, and to remove a key/value pair.

The most commonly used map implementation is HashMap. It works well with keys that are strings or numbers.

Plain maps such as HashMap are unordered. Iterating through key/value pairs may return individual entries in any order. If you need to iterate through map entries in a controlled fashion, you should look at the following:

Sorted maps such as TreeMap will iterate through keys in their natural order (or in an order that you can specify, by providing a Comparator). For example, a sorted map using numbers as keys would be expected to iterate through its entries in numeric order.
LinkedHashMap permits iterating through entries in the same order that they were inserted into the map, or by the order of most recently accessed.

Add an element

Addition

Map<Integer, String> map = new HashMap<>(); map.put(1, “First element.”); System.out.println(map.get(1));

Output: First element.

Override

Map<Integer, String> map = new HashMap<>(); map.put(1, “First element.”); map.put(1, “New element.”); System.out.println(map.get(1));

Output: New element.

HashMap is used as an example. Other implementations that implement the Map interface may be used as well.

Add multiple items

We can use V put(K key,V value):

Associates the specified value with the specified key in this map (optional operation). If the map previously contained a mapping for the key, the old value is replaced by the specified value.

String currentVal;
Map<Integer, String> map = new TreeMap<>();
currentVal = map.put(1, "First element.");
System.out.println(currentVal);// Will print null
currentVal = map.put(2, "Second element.");
System.out.println(currentVal); // Will print null yet again    
currentVal = map.put(2, "This will replace 'Second element'");
System.out.println(currentVal); // will print Second element.
System.out.println(map.size()); // Will print 2 as key having
// value 2 was replaced.

Map<Integer, String> map2 = new HashMap<>();
map2.put(2, "Element 2");
map2.put(3, "Element 3");

map.putAll(map2);

System.out.println(map.size());

Output:

3

To add many items you can use an inner classes like this:

Map<Integer, String> map = new HashMap<>() {{
    // This is now an anonymous inner class with an unnamed instance constructor
    put(5, "high");
    put(4, "low");
    put(1, "too slow");
}};

Keep in mind that creating an anonymous inner class is not always efficient and can lead to memory leaks so when possible, use an initializer block instead:

static Map<Integer, String> map = new HashMap<>();

static {
    // Now no inner classes are created so we can avoid memory leaks
    put(5, "high");
    put(4, "low");
    put(1, "too slow");
}

The example above makes the map static. It can also be used in a non-static context by removing all occurences of static.

In addition to that most implementations support putAll, which can add all entries in one map to another like this:

another.putAll(one);

Using Default Methods of Map from Java 8

Examples of using Default Methods introduced in Java 8 in Map interface

Using getOrDefault

Returns the value mapped to the key, or if the key is not present, returns the default value

Map<Integer, String> map = new HashMap<>();
map.put(1, "First element");
map.get(1);                                 // => First element
map.get(2);                                 // => null
map.getOrDefault(2, "Default element");     // => Default element

Using forEach

Allows to perform the operation specified in the ‘action’ on each Map Entry

  Map<Integer, String> map = new HashMap<Integer, String>();
  map.put(1, "one");
  map.put(2, "two");
  map.put(3, "three");
  map.forEach((key, value) -> System.out.println("Key: "+key+ " :: Value: "+value));

   // Key: 1 :: Value: one
   // Key: 2 :: Value: two
   // Key: 3 :: Value: three

Using replaceAll

Will replace with new-value only if key is present

 Map<String, Integer> map = new HashMap<String, Integer>();
 map.put("john", 20);
 map.put("paul", 30);
 map.put("peter", 40);
 map.replaceAll((key,value)->value+10);   //{john=30, paul=40, peter=50}

Using putIfAbsent

Key-Value pair is added to the map, if the key is not present or mapped to null

    Map<String, Integer> map = new HashMap<String, Integer>();
    map.put("john", 20);
    map.put("paul", 30);
    map.put("peter", 40);
    map.putIfAbsent("kelly", 50);     //{john=20, paul=30, peter=40, kelly=50}

Using remove

Removes the key only if its associated with the given value

 Map<String, Integer> map = new HashMap<String, Integer>();
 map.put("john", 20);
 map.put("paul", 30);
 map.put("peter", 40);
 map.remove("peter",40); //{john=30, paul=40}

Using replace

If the key is present then the value is replaced by new-value. If the key is not present, does nothing.

Map<String, Integer> map = new HashMap<String, Integer>(); map.put(“john”, 20); map.put(“paul”, 30); map.put(“peter”, 40); map.replace(“peter”,50); //{john=20, paul=30, peter=50} map.replace(“jack”,60); //{john=20, paul=30, peter=50}
Using computeIfAbsent

This method adds an entry in the Map. the key is specified in the function and the value is the result of the application of the mapping function

    Map<String, Integer> map = new HashMap<String, Integer>();
    map.put("john", 20);
    map.put("paul", 30);
    map.put("peter", 40);
    map.computeIfAbsent("kelly", k->map.get("john")+10); //{john=20, paul=30, peter=40, kelly=30}
    map.computeIfAbsent("peter", k->map.get("john")+10); //{john=20, paul=30, peter=40, kelly=30} //peter already present

Using computeIfPresent

This method adds an entry or modifies an existing entry in the Map. Does nothing if an entry with that key is not present

    Map<String, Integer> map = new HashMap<String, Integer>();
    map.put("john", 20);
    map.put("paul", 30);
    map.put("peter", 40);
    map.computeIfPresent("kelly", (k,v)->v+10); //{john=20, paul=30, peter=40} //kelly not present
    map.computeIfPresent("peter", (k,v)->v+10); //{john=20, paul=30, peter=50} // peter present, so increase the value

Using compute

This method replaces the value of a key by the newly computed value

    Map<String, Integer> map = new HashMap<String, Integer>();
    map.put("john", 20);
    map.put("paul", 30);
    map.put("peter", 40);
    map.compute("peter", (k,v)->v+50); //{john=20, paul=30, peter=90} //Increase the value

Using merge

Adds the key-value pair to the map, if key is not present or value for the key is null Replaces the value with the newly computed value, if the key is present Key is removed from the map , if new value computed is null

    Map<String, Integer> map = new HashMap<String, Integer>();
    map.put("john", 20);
    map.put("paul", 30);
    map.put("peter", 40);
    
    //Adds the key-value pair to the map, if key is not present or value for the key is null
    map.merge("kelly", 50 , (k,v)->map.get("john")+10); // {john=20, paul=30, peter=40, kelly=50}
    
    //Replaces the value with the newly computed value, if the key is present
    map.merge("peter", 50 , (k,v)->map.get("john")+10); //{john=20, paul=30, peter=30, kelly=50}
   
    //Key is removed from the map , if new value computed is null
    map.merge("peter", 30 , (k,v)->map.get("nancy")); //{john=20, paul=30, kelly=50}

Clear the map

Map<Integer, String> map = new HashMap<>();

map.put(1, "First element.");
map.put(2, "Second element.");
map.put(3, "Third element.");

map.clear();

System.out.println(map.size());   // => 0

Iterating through the contents of a Map

Maps provide methods which let you access the keys, values, or key-value pairs of the map as collections. You can iterate through these collections. Given the following map for example:

Map<String, Integer> repMap = new HashMap<>();
repMap.put("Jon Skeet", 927_654);
repMap.put("BalusC", 708_826);
repMap.put("Darin Dimitrov", 715_567);

Iterating through map keys:

for (String key : repMap.keySet()) {
    System.out.println(key);
}

Prints:

Darin Dimitrov

Jon Skeet
BalusC

keySet() provides the keys of the map as a Set. Set is used as the keys cannot contain duplicate values. Iterating through the set yields each key in turn. HashMaps are not ordered, so in this example the keys may be returned in any order.

Iterating through map values:

for (Integer value : repMap.values()) {
    System.out.println(value);
}

Prints:

715567

927654
708826

values() returns the values of the map as a Collection. Iterating through the collection yields each value in turn. Again, the values may be returned in any order.

Iterating through keys and values together

for (Map.Entry<String, Integer> entry : repMap.entrySet()) {
    System.out.printf("%s = %d\n", entry.getKey(), entry.getValue());
}

Prints:

Darin Dimitrov = 715567

Jon Skeet = 927654
BalusC = 708826

entrySet() returns a collection of Map.Entry objects. Map.Entry gives access to the key and value for each entry.

Merging, combine and composing Maps

Use putAll to put every member of one map into another. Keys already present in the map will have their corresponding values overwritten.

Map<String, Integer> numbers = new HashMap<>();
numbers.put("One", 1)
numbers.put("Three", 3)
Map<String, Integer> other_numbers = new HashMap<>();
other_numbers.put("Two", 2)
other_numbers.put("Three", 4)

numbers.putAll(other_numbers)

This yields the following mapping in numbers:

"One" -> 1
"Two" -> 2
"Three" -> 4 //old value 3 was overwritten by new value 4

If you want to combine values instead of overwriting them, you can use Map.merge, added in Java 8, which uses a user-provided BiFunction to merge values for duplicate keys. merge operates on individual keys and values, so you’ll need to use a loop or Map.forEach. Here we concatenate strings for duplicate keys:

for (Map.Entry<String, Integer> e : other_numbers.entrySet())
    numbers.merge(e.getKey(), e.getValue(), Integer::sum);
//or instead of the above loop
other_numbers.forEach((k, v) -> numbers.merge(k, v, Integer::sum));

If you want to enforce the constraint there are no duplicate keys, you can use a merge function that throws an AssertionError:

mapA.forEach((k, v) ->
    mapB.merge(k, v, (v1, v2) ->
        {throw new AssertionError("duplicate values for key: "+k);}));

Composing Map<X,Y> and Map<Y,Z> to get Map<X,Z>

If you want to compose two mappings, you can do it as follows

    Map<String, Integer> map1 = new HashMap<String, Integer>();
    map1.put("key1", 1);
    map1.put("key2", 2);
    map1.put("key3", 3);
    
    Map<Integer, Double> map2 = new HashMap<Integer, Double>();
    map2.put(1, 1.0);
    map2.put(2, 2.0);
    map2.put(3, 3.0);

    Map<String, Double> map3 = new new HashMap<String, Double>();
    map1.forEach((key,value)->map3.put(key,map2.get(value)));

This yields the following mapping

    "key1" -> 1.0
    "key2" -> 2.0
    "key3" -> 3.0

Check if key exists

Map<String, String> num = new HashMap<>();
num.put("one", "first");

if (num.containsKey("one")) {
    System.out.println(num.get("one")); // => first
}

Maps can contain null values

For maps, one has to be carrefull not to confuse “containing a key” with “having a value”. For example, HashMaps can contain null which means the following is perfectly normal behavior :

Map<String, String> map = new HashMap<>();
map.put("one", null);
if (map.containsKey("one")) {
    System.out.println("This prints !"); // This line is reached 
}
if (map.get("one") != null) {
    System.out.println("This is never reached !"); // This line is never reached 
}

More formally, there is no guarantee that map.contains(key) <=> map.get(key)!=null

Iterating Map Entries Efficiently

This section provides code and benchmarks for ten unique example implementations which iterate over the entries of a Map<Integer, Integer> and generate the sum of the Integer values. All of the examples have an algorithmic complexity of Θ(n), however, the benchmarks are still useful for providing insight on which implementations are more efficient in a “real world” environment.

Implementation using Iterator with Map.Entry

Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry<Integer, Integer> pair = it.next(); sum += pair.getKey() + pair.getValue(); }
Implementation using for with Map.Entry

for (Map.Entry<Integer, Integer> pair : map.entrySet()) { sum += pair.getKey() + pair.getValue(); }
Implementation using Map.forEach (Java 8+)

map.forEach((k, v) -> sum[0] += k + v);
Implementation using Map.keySet with for

for (Integer key : map.keySet()) { sum += key + map.get(key); }
Implementation using Map.keySet with Iterator

Iterator it = map.keySet().iterator(); while (it.hasNext()) { Integer key = it.next(); sum += key + map.get(key); }
Implementation using for with Iterator and Map.Entry

for (Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator(); entries.hasNext(); ) { Map.Entry<Integer, Integer> entry = entries.next(); sum += entry.getKey() + entry.getValue(); }
Implementation using Stream.forEach (Java 8+)

map.entrySet().stream().forEach(e -> sum += e.getKey() + e.getValue());
Implementation using Stream.forEach with Stream.parallel (Java 8+)

map.entrySet() .stream() .parallel() .forEach(e -> sum += e.getKey() + e.getValue());
Implementation using IterableMap from Apache Collections

MapIterator<Integer, Integer> mit = iterableMap.mapIterator(); while (mit.hasNext()) { sum += mit.next() + it.getValue(); }
Implementation using MutableMap from Eclipse Collections

mutableMap.forEachKeyValue((key, value) -> { sum += key + value; });

Performance Tests (Code available on Github)
Test Environment: Windows 8.1 64-bit, Intel i7-4790 3.60GHz, 16 GB

Average Performance of 10 Trials (100 elements) Best: 308±21 ns/op

Benchmark                           Score     Error  Units
test3_UsingForEachAndJava8            308  ±     21  ns/op
test10_UsingEclipseMutableMap         309  ±      9  ns/op
test1_UsingWhileAndMapEntry           380  ±     14  ns/op
test6_UsingForAndIterator             387  ±     16  ns/op
test2_UsingForEachAndMapEntry         391  ±     23  ns/op
test7_UsingJava8StreamAPI             510  ±     14  ns/op
test9_UsingApacheIterableMap          524  ±      8  ns/op
test4_UsingKeySetAndForEach           816  ±     26  ns/op
test5_UsingKeySetAndIterator          863  ±     25  ns/op
test8_UsingJava8StreamAPIParallel    5552  ±    185  ns/op

Average Performance of 10 Trials (10000 elements) Best: 37.606±0.790 μs/op

Benchmark                           Score     Error  Units
test10_UsingEclipseMutableMap       37606  ±    790  ns/op
test3_UsingForEachAndJava8          50368  ±    887  ns/op
test6_UsingForAndIterator           50332  ±    507  ns/op
test2_UsingForEachAndMapEntry       51406  ±   1032  ns/op
test1_UsingWhileAndMapEntry         52538  ±   2431  ns/op
test7_UsingJava8StreamAPI           54464  ±    712  ns/op
test4_UsingKeySetAndForEach         79016  ±  25345  ns/op
test5_UsingKeySetAndIterator        91105  ±  10220  ns/op
test8_UsingJava8StreamAPIParallel  112511  ±    365  ns/op
test9_UsingApacheIterableMap       125714  ±   1935  ns/op

Average Performance of 10 Trials (100000 elements) Best: 1184.767±332.968 μs/op

Benchmark                            Score       Error  Units
test1_UsingWhileAndMapEntry       1184.767  ±  332.968  μs/op
test10_UsingEclipseMutableMap     1191.735  ±  304.273  μs/op
test2_UsingForEachAndMapEntry     1205.815  ±  366.043  μs/op
test6_UsingForAndIterator         1206.873  ±  367.272  μs/op
test8_UsingJava8StreamAPIParallel 1485.895  ±  233.143  μs/op
test5_UsingKeySetAndIterator      1540.281  ±  357.497  μs/op
test4_UsingKeySetAndForEach       1593.342  ±  294.417  μs/op
test3_UsingForEachAndJava8        1666.296  ±  126.443  μs/op
test7_UsingJava8StreamAPI         1706.676  ±  436.867  μs/op
test9_UsingApacheIterableMap      3289.866  ± 1445.564  μs/op

A Comparison of Performance Variations Respective to Map Size

       x: Size of Map
    f(x): Benchmark Score (μs/op)

                 100      600     1100     1600     2100
        ---------------------------------------------------
        10  |   0.333    1.631    2.752    5.937    8.024
         3  |   0.309    1.971    4.147    8.147   10.473
         6  |   0.372    2.190    4.470    8.322   10.531
         1  |   0.405    2.237    4.616    8.645   10.707
Tests    2  |   0.376    2.267    4.809    8.403   10.910
 f(x)    7  |   0.473    2.448    5.668    9.790   12.125
         9  |   0.565    2.830    5.952    13.22   16.965
         4  |   0.808    5.012    8.813    13.939  17.407
         5  |   0.81     5.104    8.533    14.064  17.422
         8  |   5.173   12.499   17.351    24.671  30.403

Use custom object as key

Before using your own object as key you must override hashCode() and equals() method of your object.

In simple case you would have something like:

class MyKey {
    private String name;
    MyKey(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {            
        if(obj instanceof MyKey) {
            return this.name.equals(((MyKey)obj).name);
        }
        return false;
    }
    
    @Override
    public int hashCode() {
        return this.name.hashCode();
    }
}

hashCode will decide which hash bucket the key belongs to and equals will decide which object inside that hash bucket.

Without these method, the reference of your object will be used for above comparison which will not work unless you use the same object reference everytime.

Usage of HashMap

HashMap is an implementation of the Map interface that provides a Data Structure to store data in Key-Value pairs.

1. Declaring HashMap

Map<KeyType, ValueType> myMap = new HashMap<KeyType, ValueType>();

KeyType and ValueType must be valid types in Java, such as - String, Integer, Float or any custom class like Employee, Student etc..

For Example : Map<String,Integer> myMap = new HashMap<String,Integer>();

2. Putting values in HashMap.

To put a value in the HashMap, we have to call put method on the HashMap object by passing the Key and the Value as parameters.

myMap.put("key1", 1);
myMap.put("key2", 2);

If you call the put method with the Key that already exists in the Map, the method will override its value and return the old value.

3. Getting values from HashMap.

For getting the value from a HashMap you have to call the get method, by passing the Key as a parameter.

myMap.get("key1");    //return 1 (class Integer)

If you pass a key that does not exists in the HashMap, this method will return null

4. Check whether the Key is in the Map or not.

myMap.containsKey(varKey);

5. Check whether the Value is in the Map or not.

myMap.containsValue(varValue);

The above methods will return a boolean value true or false if key, value exists in the Map or not.

Creating and Initializing Maps

Introduction

Maps stores key/value pairs, where each key has an associated value. Given a particular key, the map can look up the associated value very quickly.

Maps, also known as associate array, is an object that stores the data in form of keys and values. In Java, maps are represented using Map interface which is not an extension of the collection interface.

Way 1 :-

 /*J2SE < 5.0*/
 Map map = new HashMap();
 map.put("name", "A");
 map.put("address", "Malviya-Nagar");
 map.put("city", "Jaipur");
 System.out.println(map);

Way 2 :-

 /*J2SE 5.0+ style (use of generics):*/
 Map<String, Object> map = new HashMap<>();
 map.put("name", "A");
 map.put("address", "Malviya-Nagar");
 map.put("city", "Jaipur");
 System.out.println(map);

Way 3 :-

  Map<String, Object> map = new HashMap<String, Object>(){{
      put("name", "A");
      put("address", "Malviya-Nagar");
      put("city", "Jaipur");
  }};
  System.out.println(map);

Way 4 :-

  Map<String, Object> map = new TreeMap<String, Object>();
      map.put("name", "A");
      map.put("address", "Malviya-Nagar");
      map.put("city", "Jaipur");
  System.out.println(map);

Way 5 :-

  //Java 8
  final Map<String, String> map =
      Arrays.stream(new String[][] {
          { "name", "A" }, 
          { "address", "Malviya-Nagar" }, 
          { "city", "jaipur" },
      }).collect(Collectors.toMap(m -> m[0], m -> m[1]));
  System.out.println(map);

Way 6 :-

  //This way for initial a map in outside the function
  final static Map<String, String> map;
  static
  {
      map = new HashMap<String, String>();
      map.put("a", "b");
      map.put("c", "d");
  }

Way 7 :- Creating an immutable single key-value map.

    //Immutable single key-value map
    Map<String, String> singletonMap = Collections.singletonMap("key", "value");

Please note, that it is impossible to modify such map.

Any attemts to modify the map will result in throwing the UnsupportedOperationException.

    //Immutable single key-value pair
    Map<String, String> singletonMap = Collections.singletonMap("key", "value");
    singletonMap.put("newKey", "newValue"); //will throw UnsupportedOperationException
    singletonMap.putAll(new HashMap<>()); //will throw UnsupportedOperationException
    singletonMap.remove("key"); //will throw UnsupportedOperationException
    singletonMap.replace("key", "value", "newValue"); //will throw UnsupportedOperationException
    //and etc