TreeMap vs HashMap

TreeMap vs HashMap

Both TreeMap & HashMap are two different implementation 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 callCollections.synchronizedMap( mapName ) . Both supports “fail-fast” iterators. Both of them doesn’t support duplicate keys.

HashMap

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

The performance of HashMap is based on two optional parameter 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 it’s 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, in a TreeMap the elements are stored in a tree.TreeMap allows us to retrieve the elements in some sorted order defined by the user. So we can say thatTreeMap is slower than HashMap. This is the only implementation based on 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.

1	public interface Comparator
2	{
3	public int compare (Object object1, Object object2);
4	public boolean equals (Object object);
5	}

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.

1	public interface Comparable
2	{
3	public int compareTo (Object objectToCompare);
4	}

Classes like Integer, String, Double etc implements 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.

01	public class MyCustomKey implements Comparable
02	{
03	private int value;
04	public MyCustomKey(int value)
05	{
06	this.value = value;
07	}
08
09	public int compareTo (MyCustomKey key)
10	{
11	int comparison = 0;
12
13	// Note:
14	// Return -1 if this.value < key.value
15	// Return 0 if this.value = key.value
16	// Return 1 if this.value > key.value
17
18	return (comparison);
19	}
20	}

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 adviced to override the hashCode() if objects of that class is being used as a key.

01	public class MyCustomKey implements Comparable
02	{
03	private int value;
04	public MyCustomKey(int value)
05	{}
06	public int compareTo (MyCustomKey key)
07	{}
08
09	public int hashCode()
10	{
11	// Note:
12	// If two objects are equal then their corresponding hashCode ()
13	// should return the same value too.
14	return (this.value * 199);
15	}
16	}

HashMap

• HashMap is unordered.
• HashMap allows null keys.
• HashMap allows different type of keys.

TreeMap

• TreeMap elements are in sorted ordered in term of keys.
• TreeMap doesn’t allow null keys.
• TreeMap allows only similar types of keys