TreeMap Program - Special functions

public static void specialFunctions(String args[])
{
 TreeMap<String, Integer> tm1 = new TreeMap<String, Integer>();  
 tm1.put("banana", 20);
 tm1.put("apple", 50);
 tm1.put("melon", 40);
 tm1.put("guava", 20);
 tm1.put("cherry", 30);

 System.out.println("\nElements of tm1: " + tm1);
 Set mySet = tm1.keySet();
 System.out.println("Keys of tm1: " + mySet);

 Collection myCol = tm1.values();
 System.out.println("Values of tm1: " + myCol);

 // USING ITERATOR
 System.out.print("\nPrinting keys with Iterator: ");
 Iterator it1 = mySet.iterator();
 while(it1.hasNext())
 {
  System.out.print(it1.next() + ", ");
 } 
 // TREEMAP SORT BY VALUE
 TreeSet yourSet = new TreeSet();
 yourSet.addAll(myCol);
 System.out.println("\nTreeMap sort by value: " + yourSet);

 // COMPARING TWO TREE MAPS
 TreeMap<String, Integer> tm2 = new TreeMap<String, Integer>();  
 tm2.putAll(tm1);
 System.out.println("\nElements of tm2: " + tm2);
 if(tm1.equals(tm2))
 {
  System.out.println("tm1 and tm2 contain same elements\n");
 } 

 System.out.println("\t\tEXTRACTING TREEMAP ELEMENTS\n");

 SortedMap m1 = tm1.subMap("banana", "guava");
 System.out.println("subMap(\"banana\", \"guava\"): " + m1);

 SortedMap m2 = tm1.headMap("guava");
 System.out.println("headMap(\"guava\"): " + m2);

 SortedMap m3 = tm1.tailMap("guava");
 System.out.println("tailMap(\"guava\"): " + m3);
}

TreeMap Progam - General Functions

public static void generalFunctionsDemo(String args[])
{
 TreeMap tm1 = new TreeMap();
 System.out.println("tm1 isEmpty() before adding elements: " + tm1.isEmpty());
 tm1.put("one", 1);
 tm1.put("apple", "red");
 tm1.put("two", 2);
 tm1.put("three", 3);
 tm1.put("four", 4);

 System.out.println("tm1 isEmpty() after adding elements: " + tm1.isEmpty());
 System.out.println("Key/value pairs of tm1:" +  tm1);

 System.out.println("\napple key exists: " + tm1.containsKey("apple"));
 System.out.println("two key exists: " + tm1.containsKey("two"));
 System.out.println("red value exists: " + tm1.containsValue("red"));
 System.out.println("2 value exists: " + tm1.containsValue(2));

 System.out.println("\nValue of three: " + tm1.get("three"));
 System.out.println("Value of four: " + tm1.get("four"));

 System.out.println("\nNo. of elements before removal: " + tm1.size());
 tm1.remove("one");
 System.out.println("No. of elements after removal: " + tm1.size());
 tm1.clear();
 System.out.println("No. of elements after clear(): " + tm1.size());
}

TreeMap vs HashMap

After knowing Hashtable vs HashMap, now let us see the comparison of HashMap with TreeMap. Basically both are derived from Map interface and meant to store key/value pairs. But TreeMap inherits one more interface SortedMap and for this reason it attains the property of returning the elements in sorting order by default (irrespective of the addition of elements in any order).

By nature, all the classes derived from Map interface allow null values either as keys are values. Null keys are accepted only once because Map classes do not allow duplicate keys.
Similarities:

1. The methods of both are not synchronized. Both are not thread-safe. But we can obtain a synchronized version as follows.
   

   HashMap hm1 = new HashMap();
   Map m1 = Collections.synchronizedMap(hm1);
   

   Now the methods of m1 are synchronized but still the methods of hm1 are not synchronized. So the programmer still has got a choice of using synchronized or unsynchronized map. This is the height of intelligence of Java designers in developing collection framework classes. It is a much matured framework.
2. Both do not support duplicate keys. If added it overrides the earlier (but not error or exception).
3. Iterators of both are fail-fast.
4. Allows null values for both keys and values (null key is allowed only once because no duplicate keys).
5. HashMap is the direct implementation of Map whereas TreeMap comes with an intermittent SortedMap (see the above hierarchy).

Differences:

1. HashMap returns unordered values. TreeMap returns the elements in ascending order (known as natural order) of keys by default (the affect of deriving from SortedMap). TreeMap order can be customized using Comparator and Comparable interfaces.
2. The performance of HapMap is higher than TreeMap because TreeMap requires minimum execution of two method calls to create a tree structure and to print the elements in natural order. The performance of HashMap can still be enhanced by the programmer by choosing optimum initial capacity and load factor, at the time of HashMap object creation itself, as per his requirements.

What is synchronized?
The concept of synchronization comes in multithreading. In multithreaded applications, there is every chance that multiple threads accessing the same source of data at the same time. This results in data corruption and data inconsistency. Synchronization avoids this by allowing only one thread to access the resource of data at a time.
That is, when one thread is modifying the data of Hashtable, the other thread cannot modify. The other thread should wait until the first one completes its job. This is done by acquiring the lock on Hashtable by the first thread. The lock will not be released until the first completes its job.
What is fail-fast?
The concept of fail-fast comes with iterators. When an Iterator object is created and iteration is going on, the HashMap elements cannot be modified (like addition or deletion of elements cannot be done). This is explained programmatically in ConcurrentModificationException.
Programs on HashMap and TreeMap are available at HashMap Tutorial and TreeMap Tutorial.
About Hashing and Hashcode
Comparing two strings letter by letter in a for loop is a time taking process. To make faster, the JVM converts each string into an integer number called hashcode. Different strings with different sequence of characters have different hashcodes. Comparison with integer numbers gives maximum performance. Usage of hashcode numbers for comparison, searching of duplicate elements and identification is faster.
Hashing is process of converting a string or object into a 32-bit integer number. Two objects are said to be equal if their hashcodes are same. hashCode() is used in combination of equals() method. When compared, hashing is done automatically by the JVM. Hashing, in data structures, is done implicitly in the basic operations with add(), contains(), remove() and size() etc. Hashing is more useful to compare the sets of large content.

TreeMap in Java Collections

The TreeMap class guarantees that the keys in the Map will be sorted in ascending order by either the keys natural order or by a Comparator provided to the constructor of the TreeMap. TreeMap implements Map and SortedSet interfaces and extends AbstractMap. TreeMap keeps the balanced binary tree in sorted order by key.

Searching for an item in a TreeMap will be slower than in a HashMap because the hashing algorithm gives better performance than the compareTo() method which is used to locate items in a TreeMap.

 

Creating a TreeMap – Constructors for TreeMap

It has the following constructors. Here comp stands for Comparator, mp stands for Map, smp stands for SortedMap.

Result	Constructor	Description
tmap =	new TreeMap()	Creates new TreeMap. Keys sorted by natural order.
tmap =	new TreeMap(comp)	Creates new TreeMap using Comparator comp to sort keys.
tmap =	new TreeMap(mp)	Creates new TreeMap from Map mp using natural ordering.
tmap =	new TreeMap(smp)	Creates new TreeMap from SortedMap smp using key ordering from smp.

 

Methods in TreeMap

TreeMap adds the methods from Map and SortedMap. See the methods of these interfaces – Methods in Map interface, Methods in SortedMap interface.

So other than Map interface methods it has SortedMap interface Methods:

• Object firstKey() - Gets the first key from the sorted Map.
• Object lastKey() - Gets the last key from the sorted map.
• SortedMap headMap(Object toKey) - Returns a view of the portion of this Map whose keys are less than toKey.
• SortedMap tailMap(Object fromKey) - Returns a view of the portion of this Map whose keys are greater than or equal to fromKey.
• SortedMap subMap(Object fromKey, Object toKey) - Returns a view of the portion of this Map whose starting key is greater than or equal to fromKey and whose ending key is less than toKey.

 

Example

TreeMap Example in java

Performance of Map interface implementations

Hashtable

An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. The initial capacity and load factor parameters are merely hints to the implementation. The exact details as to when and whether the rehash method is invoked are implementation-dependent.

HashMap

This implementation provides constant-time [ Big O Notation is O(1) ] performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.
Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

 

TreeMap

The TreeMap implementation provides guaranteed log(n) [ Big O Notation is O(log N) ] time cost for the containsKey, get, put and remove operations.

 

LinkedHashMap

A linked hash map has two parameters that affect its performance: initial capacity and load factor. They are defined precisely as for HashMap. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashMap, as iteration times for this class are unaffected by capacity.

Get Synchronized Map

By default map is not synchronized in java. To get this we can do following

Getting Synchronized map from hashmap :

HashMap hashMap = new HashMap();
Map map = Collections.synchronizedMap(hashMap);


From TreeMap :

TreeMap treeMap = new TreeMap();
Map map = Collections.synchronizedMap(treeMap);