Java Map vs HashMap vs TreeMap vs LinkedHashMap

Tags: , , , ,

Java Map

Java Map is an interface with the following signature. 

public interface Map<K,V>

Here are some properties of Java Map:
  1. It defines an operation to map keys to values.
  2. A map cannot contain duplicate keys; each key can map to at most one value.
  3. The Map interface provides three collection views, which allow a map’s contents to be viewed as a set of keys, collection of values, or set of key-value mappings.

  4. The order of a map is dependent on its implementations. Some map implementations, like the TreeMap class, make specific guarantees as to their order; others, like the HashMap class, do not.

  5. All general-purpose map implementation classes should provide two “standard” constructors: a void (no arguments) constructor which creates an empty map, and a constructor with a single argument of type Map, which creates a new map with the same key-value mappings as its argument.

Java Hashtable

Hashtable implements Java Map interface, so it maps keys to values. Any non-null object can be used as a key or as a value.

The objects used as keys must implement the hashCode method and theequals method.

An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor.

Generally, the default load factor (.75) offers a good tradeoff between time and space costs.

Hashtable is synchronized. If a thread-safe implementation is not needed, it is recommended to use HashMap in place of Hashtable. If a thread-safe highly-concurrent implementation is desired, then it is recommended to use ConcurrentHashMap in place of Hashtable.

Java HashMap

Java HashMap is a Hash table based implementation of the Map interface. It provides all of the optional map operations, and permits null values and the null key, which is different from Java Hashtable. 

The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls. It makes no guarantees as to the order of the map; particularly, there is no guarantee that the order will remain constant over time.

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

Similiar to Hashtable, there are also two parameters that affect java HashMap performance: initial capacity and load factor. The default load factor (.75) offers a good tradeoff between time and space costs.

HashMap is not thread-safe. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.

Java SortedMap

Java SortedMap is a Map that further provides a total ordering on its keys. The map is ordered according to the natural ordering of its keys, or by aComparator typically provided at sorted map creation time.

The keys inserted into a sorted map need to implement the Comparable interface (or be accepted by the specified comparator). In addition, all such keys must be mutually comparable: k1.compareTo(k2) (or comparator.compare(k1, k2)) must not throw aClassCastException for any keys k1 and k2 in the sorted map. 

Please refer to this post on how to use Java HashMap.

Java TreeMap

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by aComparator 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.

This implementation is not synchronized. If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally.

All Map.Entry pairs returned by methods in this class and its views represent snapshots of mappings at the time they were produced. They do not support the Entry.setValue method.

See this post on how to use Java TreeMap

Java LinkedHashMap

Java LinkedHashMap is a Hash table and linked list implementation of the Map interface, with predictable iteration order.

It differs from HashMap as it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

The insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would returntrue immediately prior to the invocation.)

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.

This class provides all of the optional Map operations, and permits null elements. Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. It is also not synchronized

A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered linked hash maps, affects iteration order. In insertion-ordered linked hash maps, merely changing the value associated with a key that is already contained in the map is not a structural modification. In access-ordered linked hash maps, merely querying the map with get is a structural modification. )

synchronized Map

To prevent accidental unsynchronized access to the map, we can use the following technique:

Reference:

https://docs.oracle.com/javase/8/docs/api/java/util/SortedMap.html

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

https://docs.oracle.com/javase/tutorial/collections/interfaces/map.html