TreeMap Flashcards
TreeMap
Why use of TreeMap if we have sorted Map.
Sorted Map is an Interface while Tree Map is its implementation.
How Tree Map works?
ree Map is nothing like HashMap except the fact it has same Map implementation.
Unlike LinkedHashMap and HashMap, TreeMap does not use hashing for storing keys. It uses a data structure called Red-Black tree.
TreeMap
TreeMap is a map implementation that keeps its entries sorted according to the natural ordering of its keys or better still using a comparator if provided by the user at construction time.
TreeMap is 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.
Since TreeMaps are sorted by keys, the object for key has to be able to compare with each other, that’s why it has to implement Comparable interface. For example, you use String as key, because String implements Comparable interface.
Tree Map Time Complexity
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
Tree Map Is Synchronized?
Note that 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.
Tree Map How To Synchronize?
This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be “wrapped” using the Collections.synchronizedSortedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(…));
Tree Map Note
A TreeSet instance performs all element comparisons using its compareTo (or compare) method
equals() and hashCode do not come into the picture when
dealing when TreeSet and TreeMap. However, it is a good
practice to override them properly, should you use this
object as a key for HashMap (for example) in the future.
Tree Map Example
@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() {
TreeMap map = new TreeMap<>();
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString());
}
---------------------------------------------------------------------------
public static void main(String[] args) {
Dog d1 = new Dog("red", 30);
Dog d2 = new Dog("black", 20);
TreeMap treeMap = new TreeMap();
treeMap.put(d1, 10);
treeMap.put(d2, 15);
Tree Map Object should implement Comparable.
class Dog implements Comparable{
String color;
int size;
Dog(String c, int s) {
color = c;
size = s;
}
public String toString(){
return color + " dog";
}
@Override
public int compareTo(Dog o) {
return o.size - this.size;
}
}Custom Sorting in TreeMap
If we’re not satisfied with the natural ordering of TreeMap, we can also define our own rule for ordering by means of a comparator during construction of a tree map.
In the example below, we want the integer keys to be ordered in descending order:
@Test
public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() {
TreeMap map =
new TreeMap<>(Comparator.reverseOrder());
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString()); }
A hash map does not guarantee the order of keys stored and specifically does not guarantee that this order will remain the same over time, but a tree map guarantees that the keys will always be sorted according to the specified order.
Importance of TreeMap Sorting
We now know that TreeMap stores all its entries in sorted order. Because of this attribute of tree maps, we can perform queries like; find “largest”, find “smallest”, find all keys less than or greater than a certain value, etc.
The code below only covers a small percentage of these cases:
@Test
public void givenTreeMap_whenPerformsQueries_thenCorrect() {
TreeMap map = new TreeMap<>();
map.put(3, "val");
map.put(2, "val");
map.put(1, "val");
map.put(5, "val");
map.put(4, "val");
Integer highestKey = map.lastKey(); Integer lowestKey = map.firstKey(); Set keysLessThan3 = map.headMap(3).keySet(); Set keysGreaterThanEqTo3 = map.tailMap(3).keySet();
assertEquals(new Integer(5), highestKey);
assertEquals(new Integer(1), lowestKey);
assertEquals("[1, 2]", keysLessThan3.toString());
assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString());
}
Internal Implementation of TreeMap
public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable
The principle of red-black trees is beyond the scope of this article, however, there are key things to remember in order to understand how they fit into TreeMap.
First of all, a red-black tree is a data structure that consists of nodes; picture an inverted mango tree with its root in the sky and the branches growing downward. The root will contain the first element added to the tree.
The rule is that starting from the root, any element in the left branch of any node is always less than the element in the node itself. Those on the right are always greater. What defines greater or less than is determined by the natural ordering of the elements or the defined comparator at construction as we saw earlier.
This rule guarantees that the entries of a treemap will always be in sorted and predictable order.
Secondly, 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).
Being self-balancing is key here. As we keep inserting and deleting entries, picture the tree growing longer on one edge or shorter on the other.
This would mean that an operation would take a shorter time on the shorter branch and longer time on the branch which is furthest from the root, something we would not want to happen.
Therefore, this is taken care of in the design of red-black trees. For every insertion and deletion, the maximum height of the tree on any edge is maintained at O(log n) i.e. the tree balances itself continuously.
Just like hash map and linked hash map, a tree map is not synchronized and therefore the rules for using it in a multi-threaded environment are similar to those in the other two map implementations.
Choosing the Right Map
Having looked at HashMap and LinkedHashMap implementations previously and now TreeMap, it is important to make a brief comparison between the three to guide us on which one fits where.
A hash map is good as a general purpose map implementation that provides rapid storage and retrieval operations. However, it falls short because of its chaotic and unorderly arrangement of entries.
This causes it to perform poorly in scenarios where there is a lot of iteration as the entire capacity of the underlying array affects traversal other than just the number of entries.
A linked hash map possesses the good attributes of hash maps and adds order to the entries. It performs better where there is a lot of iteration because only the number of entries is taken into account regardless of capacity.
A tree map takes ordering to the next level by providing complete control over how the keys should be sorted. On the flip side, it offers worse general performance than the other two alternatives.
We could say a linked hash map reduces the chaos in the ordering of a hash map without incurring the performance penalty of a tree map.
Tree Map Code
Pending
Useful TreeMap APIs
Pending
