Wednesday, July 31, 2019

TreeMap


public interface NavigableMap<K,V> extends SortedMap<K,V>

public class TreeMap<K,V> extends AbstractMap<K,V>
       implements NavigableMap<K,V>, Cloneable, Serializable

Type Parameters:
K - the type of keys maintained by this map
V - the type of mapped values

All Implemented Interfaces:
Serializable, Cloneable, Map, NavigableMap, SortedMap


TreeMap is a part of collection framework and is present in java.util package.
TreeMap use Red-Black tree to store it's elements.
TreeMap is the implementation of NavigableMap interface which extends SortedMap interface that means we can say that TreeMap is the implementation of SortedMap interface.
TreeMap is sorted according to the natural ordering of its keys, or by a custom Comparator that you can provide at the time of creation of the TreeMap, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
The main difference between TreeMap and HashMap is that, HashMap is an unordered collection while TreeMap is sorted in the ascending order of its keys.
TreeMap is not synchronized.

To use in multithreading, We can use Collections.synchronizedSortedMap method to get synchronized TreeMap.

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

Note about Red-Black Tree.

  • A red-black tree is a data structure that consists of nodes.
  • A red-black tree is a self-balancing binary search tree. This attribute and the above guarantee that basic operations like search, get, put and remove take logarithmic time O(log n).

Summary of TreeMap:-

  • TreeMap is the implementation of SortedMap interface.
  • TreeMap use Red-Black tree to store it's elements.
  • TreeMap is sorted in the ascending order of its keys i.e. TreeMap maintains ascending order.
  • We can also provide a custom Comparator to the TreeMap at the time of creation TreeMap.
  • TreeMap is not synchronized.
  • TreeMap cannot contain duplicate keys.
  • TreeMap cannot contain the null key. But It can have multiple null values.
  • TreeMap is not synchronized. To Access TreeMap in multi-threaded environment, We must be synchronized explicitly. using Collections.synchronizedSortedMap().
  • TreeMap is slower than HashMap for most operations like add(), remove() and contains() because TreeMap has to adjust their element after each operation.
  • The First element of TreeMap is always lowest key and last value is Highest key.
  • Note:- TreeMap and HashMap don’t support duplicate keys. If added, it overrides the previous element (without an error or an exception)
TreeMap Constructors:-
  • TreeMap( )
  • TreeMap(Comparator comp)
  • TreeMap(Map m): Initializes a tree map with the entries from Map, which will be sorted using the natural order of the keys.
  • TreeMap(SortedMap sm)
Note: while using TreeMap with custom class. It should be implements comparator or comparable interface.

No comments:

Post a Comment