Java / Map and its implementations

• Both store the data in the form of key-value pairs.
• Both use Hashing technique to store the key-value pairs.
• Both implement Map interface.
• Both doesn't maintain insertion order for elements.
• Both give constant time performance for insertion and retrieval operations.

A resource bundle is represented by a text file containing keys and a text value for each key.

Hashmap best and average case for Search, Insert and Delete is O(1) and worst case is O(n).

Hash tables are the implementation of associative arrays. Associative arrays, the abstract data structure mapping keys to values. Implementations of associative arrays using self-balancing binary search trees have lookup that is O(log n) in the worst case.

The ArrayList has O(n) performance for every search, so for n searches its performance is O(n^2).

The HashMap has O(1) performance for every search (on average), so for n searches its performance will be O(n).

While the HashMap will be slower at first and take more memory, it will be faster for large values of n.

In multiple threaded environment HashMap is usually faster than ConcurrentHashMap .

ConcurrentHashMap does not allow NULL values as well as key can not be null in ConcurrentHashMap .While In HashMap there can only be one null key .

ConcurrentHashMap is thread-safe while HashMap is not thread-safe .

Yes.

• HashMap,
• TreeMap,
• Hashtable,
• ConcurrentHashMap,
• and LinkedHashMap.

Both maps are thread-safe implementations of the Map interface.

ConcurrentHashMap allows concurrent modification of the Map from several threads without the need to block them while synchronizedMap creates a blocking Map which will degrade performance.

synchronizedMap ensures data consistency and enables every thread to have an up-to-date view of the map.

ConcurrentHashMap is preferred where performance is critical and each thread only inserts data to the map, with reads happening less frequently while use synchronizedMap for data consistency across threads.

Both are thread-safe implementations of the Map interface.

Both provide the same degree of synchronization.

HashTable is part of Java's legacy code.

The Hashtable class has all its methods synchronized i.e. the locking is done at the method level and hence one can say that the mutex is always at the Hashtable object (this) level.

ConcurrentHashMap divides the whole map into different segments and locks only a particular segment during the update operation, instead of Hashtable, which locks whole Map.

The ConcurrentHashMap also provides lock-free read, which is not possible in Hashtable. ConcurrentHashMap is faster than Hashtable, especially when a number of the reader is more than the number of writers.

The different available reference types are WeakReference and softReference (PhantomReference).

These reference types are defined in java.lang.ref package and provided to assist Java Garbage Collector in a case of low memory issues. If you wrap an object with WeakReference then it will be eligible for garbage collected if there are no strong reference. They can later be reclaimed by Garbage collector if JVM is running low on memory.

The java.util.WeakHashMap is a special Map implementation, whose keys are the object of WeakReference, so if only Map contains the reference of any object and no other, those object can be garbage collected if GC needs memory.

To use an object as key in HashMap, it needs to implement equals() and hashCode() method.

Map interface is not compatible with the Collection interface.

Since Map requires key as well as value , for example, if we want to add key-value pair then we will use put(Object key, Object value). So there are two parameters required to add element to the HashMap object . In Collection interface add(Object o) has only one parameter.

Map supports valueSet , keySet as well as other appropriate methods which have just different views from the Collection interface.

HashMap remove method calls removeEntryForKey method internally, which calculate the final hashValue of the key object, and then use that hashValue in the indexFor(int,int) method to find the first entry object in the appropriate bucket.

Since bucket is a LinkedList we start traversing from the first entry object which we retrieved indexFor method in the bucket. For each entry object in the bucket we compare whether hashValue and the key is equal to the calculated hashValue in the first step and the key passed as a parameter in the remove(key) method.

If desired Entry object is found , then we remove that single entry object from the LinkedList. Removing a single Entry object from the LinkedList is implemented just like removing a single object from the LinkedList.

Entry object returned by the removeEntryForKey method is then stored in the local variable e of type Entry in the remove(key) method. Return the removed entry if it is not null else return null.

NavigableMap Map was added in Java 1.6 that provides navigation capability to Map data structure. It provides methods such as lowerKey() to get keys which is less than specified key, floorKey() to retrieve keys which is less than or equal to specified key, ceilingKey() to get keys which is greater than or equal to specified key and higherKey() to return keys which is greater specified key from a Map.

Similarly navigable methods lowerEntry(), floorEntry(), ceilingEntry() and higherEntry() are available to retrieve map entries.

In addition to the navigation methods, it also enables creating sub-Map, for example, creating a Map from entries of an existing Map using tailMap, headMap and subMap. headMap() method returns a NavigableMap whose keys are less than specified, tailMap() returns a NavigableMap whose keys are greater than the specified and subMap() gives a NavigableMap between a range, specified by toKey to fromKey.

If the number of elements in the map exceeds a given threshold defined by load-factor (default .75) it will re-size the map once it is 75% occupied.

Java HashMap re-size itself by creating a new bucket array of it's size twice of the previous size of HashMap and puts every old element into that new bucket array. This process is termed as rehashing because it also applies the hash function to find new bucket location.

The null key is handled specially in HashMap using 2 separate methods putForNullKey(V value) and getForNullKey(). Null key is mapped always to 0th Index. This null key scenario is treated in isolated methods to eliminate null key code check and improve performance of get and put methods. The equals() and hashcode() method are not used in case of null key in HashMap.

HashMap is backed by the Array of LinkedList.

Immutability allows caching the hashcode of different keys which makes the overall retrieval process very fast and suggest that String and various wrapper classes such as Integer provided by Java Collection API are very good HashMap keys.

The reason is that if map.get(key) returns null, you can't detect whether the key explicitly maps to null vs the key isn't mapped. In a non-concurrent map, you can check this via map.contains(key), but in a concurrent one, the map might have changed between calls.

No.

We can remove entries from HashMap using remove(key) or clear() methods. remove method removes the mapping for the key specified in the parameter while clear() method removes all the entries from the HashMap and returns void.

Yes, key object hashcode method is called internally when get or put method is calculated to identify the memory location in hashmap. It is ideal to cache hashcode to avoid calculating every time especially when key is immutable.

Prior to Java8, map implementations such as Hashmap handles collision by chaining using a linked list when multiple elements (key) end up in same bucket location. This may degrade the performance from O(1) (one bucket location one key) to O(n) for that particular bucket.

In Java8, to address the performance degrade due to frequent collision, Java8 has started using a balanced tree instead of linked list for storing collided entries to improve performance from O(n) to O(log n).

Java8 still uses Linked list for collision however it converts to balanced tree when number of elements in the same bucket exceeds the TREEIFY_THRESHOLD constant defined by Hashmap. The TREEIFY_THRESHOLD value is 8 so when number of elements exceed 8 linked list switches to balanced tree.

TreeMap implements,

• NavigableMap is a subtype of java.util.SortedMap has navigation methods such as ceilingKey(), floorKey(), higherKey() and lowerKey().
• AbstractMap provides a skeletal implementation of the Map interface, to minimize the effort required to implement this interface.
• SortedMap provides a total ordering on its keys.
• Cloneable and Serializable.

HashMap implements Serializable, Cloneable and Map interfaces.

It also extends java.util.AbstractMap.

TreeMap guarantees log(n) time cost for operatons like containsKey, get, put and remove.

TreeMap is not synchronized, so to achieve thread safety, we may make it synchronized by Collections.synchronizedSortedMap method.

No. TreeMap doesn't allow null keys.

The key object need to implement Comparable interface otherwise provide explicit comparator while constructing TreeMap object.

No. IdentityHashMap does not use hashCode method instead it uses System.identityHashCode() method. It neither use equals method instead uses == reference equality operator.

IdentityHashMap class is not a general-purpose Map implementation; it intentionally violates Map's general contract to use equals method when comparing objects.

This class is designed for use only in the rare case scenario where reference-equality semantics are required.

Decorator design pattern.

No, it does not allow null key however allow null values.

ConcurrentSkipListMap is a TreeMap equivalent concurrent collection.

ConcurrentSkipListMap Implements ConcurrentNavigableMap that keep its key elements sorted in a natural order. The order can also be defined by a custom comparator set while initializing the Map object (using constructor).

This map implementation is introduced in JDK 1.6.

ConcurrentSkipListMap guarantees O(log n) for a wide range of operations.

You can't have the TreeMap itself sort on the values, since that defies the SortedMap specification, "A Map that further provides a total ordering on its keys". However, using an external collection, you can always sort Map.entrySet() either by key, values, or other sorting as needed.

package net.javapedia.algorithms;

import java.util.*;
import java.util.stream.Collectors;

public class SortMapByValueForlowestToHighest {

    public static void main(String[] args) {
        usingLinkedHashMap();
    }

    public static void usingLinkedHashMap() {
            Map<String, Integer> monthToExpense = new HashMap<>();
            monthToExpense.put("Jan",3);
            monthToExpense.put("Feb",5);
            monthToExpense.put("Mar",1);
            monthToExpense.put("Apr",0);
            monthToExpense.put("May",11);
            System.out.println(monthToExpense);
            monthToExpense= monthToExpense.entrySet().stream().sorted(Map.Entry.comparingByValue()).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1,e2)->e1, LinkedHashMap::new));
            System.out.println(monthToExpense);
    }

}

Default size is 16.

Map is not an Iterable object, since it doesn't implement the Iterable Interface. We have to use keys() method to get access to an Iterable object, which will be used to iterate over the keys.