Dinesh on Java

Both TreeMap & HashMap are two different implementations of the Map interface. Even though this post is titled “TreeMap vs HashMap” I would like to say how they are connected and how much similar they are.

Both TreeMap & HashMap are not synchronized. To make it synchronized we have to explicitly call Collections.synchronizedMap( mapName). Both supports “fail-fast” iterators. Both of them doesn’t support duplicate keys.

HashMap

1. HashMap allows null as both keys and values.
2. HashMap is useful when we need to access the map without considering how they are added to the map (means, unordered lookup of values using their keys).
3. HashMap is not synchronized while it is being looked up.
4. HashMap doesn’t allow duplicated entries.

The performance of HashMap is based on two optional parameters which we can specify during the creation of the HashMap. Initial capacity & load factor. Initial capacity is the bucket size assigned to a HashMap during its creation. Load factor decides when the HashMap needs to be expanded. If the load factor is 0.75, the size will be increased when the current size of the map crosses 75% of its capacity.

TreeMap

The basic difference between HashMap & TreeMap is that,
1. in a TreeMap the elements are stored in a tree.
2.TreeMap allows us to retrieve the elements in some sorted order defined by the user. So we can say that TreeMap is slower than HashMap. This is the only implementation based on a SortedMap interface.

TreeMap allows us to specify an optional Comparator object during its creation. The keys should be compatible with the comparator specified. This comparator decides the order by which the keys need to be sorted.

public interface Comparator
{
    public int compare (Object object1, Object object2);
    public boolean equals (Object object);
}

If we are not specifying the comparator, TreeMap will try to sort the keys in the natural order. Means will consider them as instances of Comparable interface.

public interface Comparable
{
    public int compareTo (Object objectToCompare);
}

Classes like Integer, String, Double etc implement the Comparable interface. So if we are to use an object of a custom class as the key, ensure that it’ s class implements the Comparable interface.

public class MyCustomKey implements Comparable
{
    private int value;
    public MyCustomKey(int value)
    {
       this.value = value;
    }           
 
    public int compareTo (MyCustomKey key)
    {
       int comparison = 0;           
 
       // Note:
       // Return -1 if this.value < key.value
       // Return  0 if this.value = key.value
       // Return  1 if this.value > key.value           
 
       return (comparison);
    }
}

A common mistake that everyone does is not to override the hashcode(). If we are failing to do so, map.get(new MyCustomKey(<value>)); may not give you what you were expecting. So it is always advisable to override the hashCode() if objects of that class are being used as a key.

public class MyCustomKey implements Comparable
{
    private int value;
    public MyCustomKey(int value)
    {}
    public int compareTo (MyCustomKey key)
    {}        
 
    public int hashCode()
    {
        // Note:
        // If two objects are equal then their corresponding hashCode ()
        // should return the same value too.
        return (this.value * 199);
    }
}