The HashMap class in java

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

As discussed earlier, HashMap doesn't add any new methods to Map interface other than clone() method. So see – Map interface methods.

Example

Creating a HashMap 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.

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
  
  
  
  

Diff. between HashMap and HashTable

HashTable
--------------------
1) is synchronized, thread-safe.
2) each time a thread is required to acquire a lock before using it.
3) does not allow null value as key.

HashMap
--------------------
1) is not synchronized or thread-safe.
2) lock is not required by threads.
3) allows one null value as key
4) it can be made thread-safe by using --> Collections.synchronizedMap() method.
5) better performance in single-threaded applications. -- no lock is required to acquire.
6) better performance in multi-threaded applications. -- you can implement a synchronize block at more broad level, so at each entry point lock is not required.

 

Also, if there is a possibility in future that - there can be a scenario when you may require to retain the order of objects in the Collection with key-value pair then HashMap can be a good choice. As one of HashMap's subclasses is LinkedHashMap, so in the event that you'd want predictable iteration order (which is insertion order by default), you can easily swap out the HashMap for a LinkedHashMap. This wouldn't be as easy if you were using Hashtable.

 

Also if you have multiple thread accessing you HashMap then Collections.synchronizedMap() method can be leveraged. Overall HashMap gives you more flexibility in terms of possible future changes.

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.

// 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", new Integer(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


// Iterate over the keys in the map 
Iterator it = map.keySet().iterator();
while (it.hasNext()) {
// Get key
    Object key = it.next();
} // Iterate over the values in the map
it = map.values().iterator();
while (it.hasNext()) {
    // Get value
     Object value = it.next();
}