Make delicious recipes!

TreeMap


TreeMap is a map which keeps its keys in a sorted order.
Internally TreeMap maintains a red-black binary tree of Map.Entry objects.


Following code shows a TreeMap usage:
public class Address implements Comparable<Address>
{
    int aptNo;
    String streetName;

    @Override
    public int compareTo(Address other)
    {
        return (aptNo - other.aptNo);
    }

    @Override
    public String toString() 
    {
        return "[" + aptNo + ", " + streetName + "]";    
    }

    public Address(int aptNo, String streetName)
    {
        this.aptNo = aptNo;
        this.streetName = streetName;
    }
}


import java.util.Arrays;
import java.util.TreeSet;



public class TreeMapTest
{
    public static void main(String[] args)
    {
        Address addr[] = new Address[4];
        addr[0] = new Address(4, "Baker Avenue");
        addr[1] = new Address(1, "Hollywood Street");
        addr[2] = new Address(2, "Baker Avenue");
        addr[3] = new Address(2, "Almonds Ave");

        TreeSet<Address> treeSet = new TreeSet<Address>();   
        treeSet.addAll(Arrays.asList(addr));
        System.out.println(treeSet.toString());
    }
}


Output for the above is:
[[1, Hollywood Street], [2, Baker Avenue], [4, Baker Avenue]]


Experts' Corner
TreeSet/TreeMap is very much unlike a HashMap/HashSet as far as the internal implementation is concerned.
TreeSet internally uses a TreeMap which does not have a table of Map.Entry as found in HashMap.
Rather a TreeSet creates a Red-Black Binary Tree of Map.Entry objects as shown below:


An interesting corollary from the above analysis is that TreeMap does not use hashCode() or equals() at all!
It solely relies on the compareTo() method and if your equals() does not comply with compareTo(), TreeMap does not care.
This could result in a serious application error where two objects considered equal by equals() return different values from TreeMap.

The TreeMap is so different from HashMap in implementation that its performance is also widely different.
For objects with good hashCode() methods, HashMap is blazing fast with O(1) time for inserts and lookups
While TreeMap cannot be faster than O(log N) even with the best compareTo() methods







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal