Maps

Map is collection of the key/value pairs. Keys are unique. Several keys may map to the same value.

All maps in Java implement the Map interface. Java has a ready the Map implementations, including concurrent maps.

The Map.Entry interface describes the key/value pair.

The Collections class has the utility methods such creating sorted or unmodifiable maps.

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

map.put("1", "one");
map.put("2", "two");
map.put("3", "three");

// prints 1 2 3, order may be other
for (String key : map.keySet()) {
    System.out.println(key);
}

// prints one two three, order may be other
for (String val : map.values()) {
    System.out.println(val);
}

// prints strings like "1 - one"
// This code is not optimized
//    for(String key: map.keySet()){
//        System.out.println(key + " - " + map.get(key));
//    }
// better to iterate over entries
for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " - " + entry.getValue());
}

Map interface

// appends msg to the current value
map.compute(key, (k, v) -> (v == null) ? msg : v.concat(msg)) 

SortedMap

The SortedMap interface is extension of Map, that provides sorting entries by keys.

HashMap

This implementation provides all of the optional map operations, and permits null values and the null key. This map is thread unsafe.

How does HashMap work? It has the array of buckets. When user puts a new entry, the HashMap calculates index of bucket. Calculation dependends from the hashCode() method of the key object. Inside bucket entries are stored as linked list. So in the worst case, when the hashCode is bad, the map will work like a LinkedList. Since Java 8, when list too large, list will be transformed to the balanced tree which has O(log n) complexity for add, delete, or get. And when tree too small it will be converted to list. This improves the worst-case performance from O(n) to O(log n).

HashMap dynamically resizes and at this moment it generates hash codes again. So it is costly operation. Good practice is to avoid unnecessary resizing, to specify initial capacity and load factor in the constructor.

For example, by default initial capacity is 16 and load factor is 0.75. Whenever bucket in HashMap reaches its load factor (16 * .75 = 12 element), it recreates a new inner array with double its capacity (32 in our case).

When two or more threads see the need for resizing the same HashMap, they might end up adding the elements of the old bucket to the new bucket simultaneously. As a result, this might lead to infinite loops.

LinkedHashMap

This map is implemented by doubly-linked buckets. Unlike HashMap, the LinkedHashMap maintains order of keys.

LinkedHashMap has two modes of keys ordering: access-order and insertion-order (default). First mode allows to implement the LRU cache, see example.

Note. With a access-order the foreach statement will throw ConcurrentModificationException exception (tested in Java 8).

// replace true to false and code will work
LinkedHashMap<String, String> map = new LinkedHashMap<>(64, 0.75f, true);

for (int i = 0; i < 10; ++i) {
    map.put(String.valueOf(i), "Test");
}

for(String it : map.keySet()){
    System.out.println(map.get(it));
}

assertTrue(true);

// replace true to false and code will work
val map = LinkedHashMap<String, String>(64, 0.75f,true)

for (i in 0..9) {
    map.put(i.toString(), "Test")
}

for(it in map.keys){
    println("item ${map[it]}")
}

TreeMap

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

TreeMap is useful when the information needs to be sorted and when quick random access is necessary. If random access is not needed then rather use sorted set or list.

WeakHashMap

In this implementation keys are stored as the weak references. When a key is no longer referenced outside of the WeakHashMap, the entry with that key will be garbage collected.

EnumMap

A specialized Map implementation for use with enum type keys. This representation is extremely compact and efficient.

Iterators returned by the collection views are weakly consistent: they will never throw ConcurrentModificationException and they may or may not show the effects of any modifications to the map that occur while the iteration is in progress.

IdentityHashMap

Unlike other maps, this implementation using reference-equality when comparing keys and values.

A typical use of this class is topology-preserving object graph transformations, such as serialization or deep-copying. To perform such a transformation, a program must maintain a "node table" that keeps track of all the object references that have already been processed. The node table must not equate distinct objects even if they happen to be equal. Another typical use of this class is to maintain proxy objects. For example, a debugging facility might wish to maintain a proxy object for each object in the program being debugged.