CodingBison

One of the classes that implements the interface Map is a HashMap class. As we know the basic property of a Map is that it stores Key/Value pairs and each "key" in the Map object, can at most relate/map/correspond to one "value"; more details about Map interface is available here. The HashMap class implements all the methods defined in the Map interface and follows the above constraint.



Figure: Map Interface and Class Hierarchy

This concept of Key/Value pair is similar to HashTable/Hash Functions. The behavior of HashMap is analogous to that of HashSet , that are discussed in detail in the Set interface. It is recommended to go through the Hash Functions/Hash Tables section of data structures modules, before getting into the details of Map interface.

Before we go into the details of the HashMap class, let us take a little detour and understand the following hash-related concepts: hash tables, load factor, collisions, and hashing function.

A hash table is a popular data structure for providing a faster search -- a well-designed hash table can provide an average lookup complexity of O(1). A hash table data structure uses a hashing function that maps a given key to one of the indices (also referred to as slots) in the hash-table. For a hash-table, indices are identified using an integer and the hashing function converts the passed key (which can be string, number, etc) into an integer that points to an index in the hash table. In other words, if the hash-table has size S and if the first index is indexed as 0, then we can find the table index, y, such that y would be greater than or equal to 0 but but less than S. You can find additional details about hash table/hash functions in our data structures module: Understanding Hash Tables.

Things To Remember
The initial default-size/capacity of an HashMap is 16 and the load factor is 0.75. Like the base Map interface, HashMap does not allow duplicate keys.

For hash tables, an important consideration is that they should be able to accommodate collisions. A collision happens when we have two or more elements that are indexed to the same slot. Collisions can potentially increase the search time-complexity for hash tables and so a good hashing function must be designed to reduce these collisions. The average lookup complexity of O(1) cannot be guaranteed if there are collisions in the Hashtable.

It is easy to see that if the size of the hash table (let us say, S) is smaller than the number of entries (let us say, N), then collisions are bound to happen. For an ideal hashing function, if S where to be same as N, then each index would have one entry. In reality, this may not be true. Even if N is smaller than S, collisions can still occur. The ratio of N and S does provide an insight into an average number of collisions. This ratio is often known as load factor of the hash table. Load factor is an important consideration for estimating the amount of collisions in a hash table. In an ideal world, the load factor should be always less than 1.0. In fact, its recommended upper limit is around 0.7. For Instance, if an applications intends to store 700 entries, it is recommended to use an Hash table of size/capacity equal to 1000. so that the load factor will be equal to 700/1000 = 0.70 or 70%.

So, if you are wondering, what is the need to learn all these HashTable concepts now? Well, as we discussed earlier, HashMap like HashSet, uses hash table as its underlying data structure and so these being familiar with these concepts should come in handy! Since we now know that hash tables provide faster lookup, if an application needs to perform a large number of lookup requests for Set elements, then using HashMap would be the way to go.

HashMap Class Constructors

HashList class provides four different Constructors. We list these constructors in the table below.


Table: Constructors provided by HashMap Class
ConstructorDescription
HashMap()Creates an empty HashMap; the default size is 16 and the load factor is 0.75.
HashMap(Map <K,V>)Creates a new HashMap with the elements of HashMap specified as argument; the default size of the HashMap is 16 and its load factor is 0.75.
HashMap(int initialSize)Creates an empty HashMap with a size equal to "initialSize" and load factor equal to 0.75 (default)
HashMap(int initialSize, float loadFactor)Creates an empty HashMap with a size equal to "initialSize" load factor equal to loadFactor.

Here is an Example program, that demonstrates the usage of the above mentioned operations.

 import java.util.HashMap;
 import java.util.Map;

 public class HashMapDemo {
     public static void main(String[] args) {
         Map hmobj1 = new HashMap();
         hmobj1.put(1237,"John");
         hmobj1.put(2013,"Ray");
         hmobj1.put(1024,"Mike");
         System.out.println(" Hash Map 1: " + hmobj1);

         Map hmobj2 = new HashMap(hmobj1);
         System.out.println(" Hash Map 2: " + hmobj2);

         Map hmobj3 = new HashMap(30);
         Map hmobj4 = new HashMap(30, (float) 0.80);
     }
 }

The above example program creates four HashMaps using different constructors. Notice the elements of the HashMap, represented by the object hmobj1. A default constructor is used to create it and thus, it has the default capacity of 16 with the load factor equal to 0.75. A new HashMap represented by "hmobj2" is created by using the second parameterized constructor that takes another HashMap as the argument. "hmap2" is a copy of "hmobj2". HashMap object, hmobj3, and hmobj4 are created with a capacity and load factor different from the default values.

Let us compile/run the program. Here is the output:

  Hash Map 1: {1237=John, 1024=Mike, 2013=Ray}
  Hash Map 2: {1237=John, 1024=Mike, 2013=Ray}

HashMap Class Methods

As we already know, HashMap is one of the Classes that implements the Map interface. So, HashMap class implements all the methods that are defined in the Map interface. HashMap does not define any specific methods. The method list is similar to the one defined in the table Map Interface Methods List.

Here is an Example program, that demonstrates the usage of the methods.

 import java.util.HashMap;
 import java.util.Map;

 public class MapDemo {
     public static void main(String[] args) {
        Map mobj = new HashMap();

        mobj.put(1237,"John");
        mobj.put(2013,"Ray");
        mobj.put(1024,"Mike");
        int key = 1237;
        System.out.println(" Key: " + key + ", Name: " + mobj.get(key));		
        System.out.println(" Value associated with key: " + mobj.put(1237,"John2"));
        System.out.println(" All map keys " + mobj.keySet());
        System.out.println(" All map Elements " + mobj);

        mobj.remove(1237);
        System.out.println(" All map Elements " + mobj);
    }
 }

Notice that in the above example program, a Map stores the Key, Value pairs. In the above example, 1237, 2013, 1024 are all keys and the names "John", "Ray", "Mike" are all Values. For example, the sample set provided above could treated like the information of all employees in an organization. An Employee ID is the Key, and Employee Name is the Value, every employee has an Unique ID and the employee information is retrieved using the ID.

Let us Compile/run the program. Here is the output:

  Key: 1237, Name: John
  Value associated with key: John
  All map keys [1237, 1024, 2013]
  All map Elements {1237=John2, 1024=Mike, 2013=Ray}
  All map Elements {1024=Mike, 2013=Ray}

Clone Operation on the HashMap

Map interface provides another important operation called "clone", where one can make a shallow copy of the HashMap. So, what does a shallow copy mean? It means the elements of the Set are not copied; instead, it just creates an instance of the HashMap. A change made using one object, gets reflected to the other object. If you are familiar with "C" programming, then it is like having two pointers to the same variable, where the pointer points to the address of a variable. Changes made to the variable at that address will be seen by all the pointers pointing to that address.

An example program demonstrating the concept of "Clone" method is provided in the Array List. Since the concept of "Clone" is same, whether it is ArrayList or HashMap, we do not provide an example here due to brevity.





comments powered by Disqus