Iterate over hashmap

public static void iterateOverHashmapGeneric(){


 HashMap<String, Integer> hm1 = new HashMap<String, Integer>();
 hm1.put("E", 69);
 hm1.put("A", 65);
 hm1.put("G", 71);
 hm1.put("C", 67);

 Set<String> mySet = hm1.keySet();
 System.out.print("foreach printing: ");
 for(String str : mySet)
 {
  System.out.print(str + ":" + hm1.get(str) + ", ");
 }

 HashMap<String, Integer> hm2 = new HashMap<String, Integer>();
 hm2.putAll(hm1);
 if(hm1.equals(hm2))
 {
  System.out.println("\n\nhm1 and hm2 contain the same elements");
 }

 HashMap<String, Integer> hm3 = (HashMap) hm1.clone();
 System.out.println("\nElements of hm3: " + hm3);   

}

A generics HashMap object hm1 is created that stores keys as strings and values as integers. With put() method elements are added.

Set<String> mySet = hm1.keySet();
     for(String str : mySet)
     {
       System.out.print(str + ":" + hm1.get(str) + ", ");
     }

With HashMap, Iterator cannot be used as Iterator stores elements of single entities but HashMap stores pairs. The new JDK 1.5 enhanced for loop (foreach) cannot be used straight away for the same reason. It is used indirectly. The keySet() returns all the keys of HashMap hm1. As keys are single entities, to iterate them, foreach loop is used. The str refers a key and using the key str, the value associated is retrieved with get() method.

HashMap<String, Integer> hm2 = new HashMap<String, Integer>();
     hm2.putAll(hm1);
     if(hm1.equals(hm2))
     {
       System.out.println("\n\nhm1 and hm2 contain the same elements");
     }

Another generics object hm2 is created and all the elements of hm1 are added at a time with putAll() method. equals() method is used to check both hm1 and hm2 contains the same elements are not. As they have same, the method returns true.

HashMap<String, Integer> hm3 = (HashMap) hm1.clone();
     System.out.println("\nElements of hm3: " + hm3);

Any Collection object including HashMap can be cloned. As the cloned object, hm3 and the hm1 occupy different locations and have their own set of values, they maintain perfect encapsulation.

Sorting keys and values in Hashmap

Example shows how sorting operations on keys and values are done.

public static void sortingHashMapDemo(){
 HashMap hm1 = new HashMap();
 hm1.put("one", 1);
 hm1.put("thousand", 1000);
 hm1.put("ten", 10);
 hm1.put("hundred", 100);
 // SORTING KEYS
 Set mySet = hm1.keySet();
 System.out.println("\nhm1 keys: " + mySet);
 TreeSet ts1 = new TreeSet(mySet);
 System.out.println("hm1 sorted keys: " + ts1);

 // SORTING VALUES
 Collection myCol = hm1.values();
 System.out.println("\nhm1 values: " + myCol);   
 TreeSet ts2 = new TreeSet(myCol);
 System.out.println("hm1 sorted values: " + ts2);

 // GET KEY FROM VALUE
 for(Object obj1 : mySet)
 {
  if(hm1.get(obj1).equals(10))
  {
   System.out.println("10 value key is " + obj1);   
  }
 }
}

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.

Concurrent hashmap in java

ConcurrentHashMap extends the abstract class AbstractMap and implements the ConcurrentMap interface. This class follows the operational specification and the similar functional specification as of Hashtable, for updating a hash table supports the fully concurrency of the recoveries and adjustable expected concurrency. This class allows the variants of methods correspondence to each method of Hashtable and also doesn't permit the 'null' for the 'key' or 'value'. All the operations of this class are thread-safe. Use of ConcurrentHashMap increases the performance because it permits the multiple threads to modify the map concurrently without require to block them however performance may be poor if the single threads access the map at a time.

Syntax

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements ConcurrentMap<K,V>

Constructor's of ConcurrentHashMap

This class provides constructor through which we can create map according to our requirement :
ConcurrentHashMap() : This constructor makes a new vacate map of default size (16), default load factor (0.75) and concurrencyLevel (16).
ConcurrentHashMap(int initialCapacity) : This constructor makes a new vacate map of capacity defined at time of instantiation according to requirement with default load factor (0.75) and concurrencyLevel (16).
ConcurrentHashMap(int initialCapacity, float loadFactor) : This constructor makes a new vacate map of capacity and load factor defined at time of instantiation according to requirement and with default concurrencyLevel (16).
ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) : This constructor makes a new vacate map of capacity, load factor, and with concurrencyLevel defined at the time of instantiation according to requirement.
ConcurrentHashMap(Map<? extends K,? extends V> m) : This constructor makes the similar mappings according to the map given.

Methods of ConcurrentHashMap

This class provides methods some of the commonly used are :

1. put()
                        syntax : public V put(K key,V value)
2. clear()
                        syntax : public void clear()
3. elements()
                        syntax : public Enumeration elements()
4. remove(Object key, Object value)
                        syntax : public boolean remove(Object key,Object value)
5. replace(K key, V value)
                        syntax : public V replace(K key,V value)
6. values()
                        syntax : public Collection values()
7. size()
                        syntax : public int size()

Example :

import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ConcurrentHashMap;
import java.util.Set;
class A implements Runnable {
  String name;
  ConcurrentMap cm;
  public A(ConcurrentMap cm, String name) {
    this.name = name;
    this.cm = cm;
  }
  public void run() {
    try {
      cm.put(1, "A");
      cm.put(2, "B");
      cm.put(3, "C");
      cm.put(4, "D");
      cm.put(5, "E");
      System.out.println(name + " maps the element : " + cm);
      System.out.println(name + " represents the set of keys: "
          + cm.keySet());
      Thread.sleep(500);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
  }
}
class B implements Runnable {
  String name;
  ConcurrentMap cm;
  public B(ConcurrentMap cm, String name) {
    this.name = name;
    this.cm = cm;
  }
 public void run() {
    try {
      boolean j = cm.remove(3, "C");
      System.out.println(name + " removes the element : " + j);
      Thread.sleep(500);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
  }
}
class C implements Runnable {
  String name;
  ConcurrentMap cm;
  public C(ConcurrentMap cm, String name) {
    this.name = name;
    this.cm = cm;
  }
 public void run() {
    try {
      Set s = cm.keySet();
      System.out.println(name + " represents 
                                  the set of keys : " + s);
      Thread.sleep(1000);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
  }
}
public class ConcurrentMapDemo {
  public static void main(String[] args) {
    ConcurrentMap cm = 
                          new ConcurrentHashMap();
    Runnable a = new A(cm, "A");
    Runnable b = new B(cm, "B");
    Runnable c = new C(cm, "C");
    new Thread(a).start();
    try {
      Thread.sleep(300);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
    new Thread(b).start();
    try {
      Thread.sleep(300);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
    new Thread(c).start();
    try {
      Thread.sleep(300);
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
  }
}

Output

A maps the element : {5=E, 4=D, 3=C, 2=B, 1=A}

A represents the set of keys: [5, 4, 3, 2, 1]

B removes the element : true

C represents the set of keys : [5, 4, 2, 1]

Hashmap Tutorial

The HashMap class is the simplest implementation of the Map interface. The HashMap does not add any additional methods (other than clone) beyond those found in the Map interface.

Creating the HashMap in java

In addition to implemented the Map interface methods, HashMap has the following constructors.

Result	Constructor	Description
hmap =	new HashMap()	Creates a new HashMap with default initial capacity 16 and load factor 0.75.
hmap =	new HashMap(initialCapacity)	Creates a new HashMap with the specified initial int capacity.
hmap =	new HashMap(initialCapacity, loadFactor)	Creates a new HashMap with the specified capacity which will not exceed a specified (float) load factor.
hmap =	new HashMap(mp)	Creates a new HashMap with elements from the Map mp

 

Performance of the HashMap

The HashMap achieves good performance by using a hash to store the key in the Map. The hash allows fast lookup which means that the containKey( ) method will perform much better than the containsValue( ) method.
HashMaps will automatically grow when you add too many elements. However, growing requires copying, rehashing and rechaining, which affects its overall performance.
Performance of HashMap depends on two important factors that are

• Initial Capacity and
• Load Factor

Initial Capacity is the capacity at the time the HashMap is created. Load factor determines when to increase the capacity of the HashMap. The default load factor is 0.75.
Important Note: The initial capacity is not the actual number of elements you plan to store in HashMap. Say for example, if you set initial capacity of 100 and the load factor is 0.75, then the capacity of HashMap will be automatically increased when it reaches to 75 not 100.
Any Object used as a key in a HashMap must implement the hashCode( ) and equals( ) methods. See Part 2 of this series for a discussion of this issue.
The HashMap does not guarantee the order of the items in the Map and allows one null key. Duplicates are not permitted. The HashSet offers "constant time" performance for lookups involving the key and linear time for lookups based on value. This means that adding items to the Map will not cause significant performance degradation as long as lookups are done by the key. The performance of basic functions such as put, remove, get, etc is based on two factors which can be specified in the constructor of the HashMap, initial capacity and load factor.

Methods in HashMap

It inherits all the methods from Map and adds following method.

• Object clone(): Returns a copy of the HashMap. The cloned object contains the same key/value pairs.

 So see – Map interface methods.

Example

Creating a HashMap in Java
Iterating over hashmap
Sorting a hashmap

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.

WeakHashMap in java : Soft reference based hashmap

A WeakHashMap stores the keys using WeakReference objects, which means that as soon as the key is not referenced from somewhere else in your program, the entry may be removed and is available for garbage collection. Otherwise it is similar to HashMap.

One of the most common instances of memory leaks in Java is in hash maps, so Sun Microsystems (now Oracle) has provided a WeakHashMap to minimize memory usage in caches implemented with maps. A WeakHashMap stores the keys using WeakReference objects, which means that as soon as the key is not referenced from somewhere else in your program, the entry may be removed and is available for garbage collection. (Have a look at the JavaDocs for the java.util.WeakHashMap and java.lang.ref.WeakReference for more information). It is important to note that the WeakHashMap has a WeakReference to the key—rather than, as we would expect—the value.

Read about type of references here.

 

As the garbage collector may remove keys from the WeakHashMap and garbage collect the object, outputs from methods like size() , isEmpty() may vary with time. The size( ) method may return different values over time. The isEmpty( ) method may return false and then true.

 

Note: Value objects in the WeakHashMap will be garbage collected only if their key is removed and they have no other reference to them. It should be noted that if the value object has a reference to its own key object, the key objetc will not be garbage collected. This situation should be avoided.

WeakHashMap Example:

public class TestWeakHashMap {
   public static void main(String[] args) {
    WeakHashMap map=new WeakHashMap();

     String s1=new String("java");
     map.put(s1, "good");
     String s2=new String("java");
     map.put(s2,"ok");

   //Since s1.equals(s2) is true and hash is same, the earlier value
   //against key s1 ("good") in the map is replaced by the new one. ("ok")

     s1=null;

     System.gc();
     //Verify Full GC with the -verbose:gc option

    System.out.println(map.size());
  }
 }

Here s1 and s2 are two different objects on the heap. So in line 5, a new (key,value) pair with key s1 is put into the map. Later when a (key,value) with key s2 is being put into the map, it checks for equals on s1 and s2 and their hashcode. When it finds the equals returns true and hashCode is same, it replaces the value of the earlier entry with the new value. But the issue here is, WeakHashMap/HashMap does not replace the earlier key while adding a (key, value) pair whose key is actually a duplicate key in the map.
So even after putting an entry with key s2, the WeakHashMap has only one entry whose key refers to the object refered by s1 and not s2.

Now the object on the heap refered by s1, has one strong reference(through s1) and one weak reference through the WeakHashMap.
Later when I say s1=null, the object on the heap refered to by s1 lost the strong reference and when gc happens, the entry is removed from the map.

So thats how it works.

Also note WeakHashMap is only a wrapper over HashMap and the HashMap's put api says " If the map previously contained a mapping for this key, the old value is replaced by the specified value."

Also see -

• 
  
  Using string from literal pool as Key


• 
  
  When value depends on Key
  
  
  
  

HashMap vs HashTable

At the outset, both are similar in functionality (purpose) but for very small difference. Both store data in key/value pairs. There is nothing with HashMap that cannot be done with Hashtable.

Following table gives the differences.

Hashtable	HashMap
Introduced with JDK 1.0 version, the starting version of Java	Introduced with JDK 1.2
Part of legacy classes (the data structures of JDK 1.0 are known as legacy classes)	Part of Collections framework
Methods of Hashtable are synchronized by default	Methods are not synchronized by default
Does not permit null values (trying to add, throws NullPointerException)	Permits null values (either key or value)
Enumeration interface is used for iterating keys	Iterator is used for iterating the keys
Enumerator is not fail-fast	Iterator is fail-fast
Safe for multithreaded applications	Better for non-threaded applications
Low performance due to synchronization	High performance
Hashtable is serialized	HashMap is not serialized

Hashtable can make use of HashMap methods to get the features of collections framework. As of JDK 1.2, the Hashtable implements Map. Following is the class signature of Hashtable.
public class java.util.Hashtable extends java.util.Dictionary implements java.util.Map, java.lang.Cloneable, java.io.Serializable
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.
Even though the HashMap methods are not synchronized, we can obtain a synchronized HashMap optionally as follows.

Map m = Collections.synchronizeMap(HashMap);

Programs on Hashtable and HashMap are available at Hashtable Examples and HashMap Examples.
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.

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);


Creating a Hash Map in java

This example shows how to create hash map and perform some operations on it.

public static Map createMap(){
  // Create a hash table 
  Map map = new HashMap();   // hash table
  //Map map = new TreeMap(); // you can do sorted 
  //map as well


  // Add key/value pairs to the map 
  map.put("a", 1);
  map.put("b", new Integer(2));
  map.put("c", new Integer(3));


  // Get number of entries in map 
  int size = map.size(); // 2

  // Adding an entry whose key exists in the map causes 

  // the new value to replace the old value 
  Object oldValue = map.put("a", new Integer(9)); // 1


// Remove an entry from the map and return the value of the removed entry 
  oldValue = map.remove("c"); // 3

  boolean isempty = map.isEmpty();

  return map;

 }

As putting a duplicate key value, pair changes value, use containsKey() and containsValue(), a programmer can check the existence of a key or value with the HashMap.