Java development professionals explain the concept of Hashmaps and the way to use it for java web development. Before coming to the Hashmaps, you will learn about Collections framework as it is important for understanding the Hashmap’s concept. You will also get to know about working of Hashmaps in Java in this article.
What is a Collections framework?
The Java Collections framework is a collection of interfaces and classes which helps in storing and processing the data efficiently. This framework has several useful classes which have tons of useful functions which makes a programmer task super easy.
Prior to Java 2, Java provided ad hoc classes such as Dictionary, Vector, Stack, and Properties to store and manipulate groups of objects. Although these classes were quite useful, they lacked a central, unifying theme. Thus, the way that you used Vector was different from the way that you used Properties.
The collections framework was designed to meet several goals.
1. The framework had to be high-performance. The implementations for the fundamental collections (dynamic arrays, linked lists, trees, and hashtables) are highly efficient.
2. The framework had to allow different types of collections to work in a similar manner and with a high degree of interoperability.
3. Extending and/or adapting a collection had to be easy.
Difference between Collection and Collections
Collection is a root level interface of the Java Collection Framework. Most of the classes in Java Collection Framework inherit from this interface. List, Set and Queue are main sub interfaces of this interface.
Collections is an utility class in java.util package. It consists of only static methods which are used to operate on objects of type Collection.
The entire Collection hierarchy
The entire Collection hierarchy is shown as follows:
We are going to look at Hashmaps in this particular article.
Hashmap is nothing but a key-value pair store. Every entry in a Hashmap is given a key and is asscoiated with a value. Speaking of this, Hashmap seems to be a pretty simple concept, however in reality Hashmap is a complex thing to deal with and in time very powerful tool to use and is used almost everywhere in large scale web application.
The first question that someone might raise is ‘Why does Map not inherit Collection’? Well this was by design. A Collection, when desgined was meant to hold hold values in any order or a fixed order. That was the initial purpose of Collections. Map on the other end, is a store for key and values. This definition of a Map distorts the very meaning of why a Collection was invented in much place. Given theis difference in the meaning, it doesnt make much sense for a Map to extend the Collection interface.
As you can see from the picture above, there are many implementations of the Map interface. Keep in mind, Map is an interface and not a concrete implementation. It just states of how different implmentations should be organised. Of all the listed here, the most popular of them which are used are Hashtable and a Hashmap. We shall discuss them first before moving into further detail.
Both Hashmap and Hashtable store key-value pairs and are almost identical except for certain key differences which are listed below
Hashmap v/s Hashtable
|Synchronized : No||Synchronized : Yes|
|Null key/value: Allows one null key and any number of null values||Null key/value: Do not allow null key or null values|
|Iteration: It uses Iterator for Iteration||Iteration: Uses Enumerator for Iteration|
|Fail fast iterator: The iterator in Hashmap is a fail-fast iterator||Fail fast iterator: The enumerator in Hashtable is fail safe|
|Performance: Hashmaps are much faster and uses lesser memory as they are unsynchronized||Performance: Hashtables are a little slower than hashmaps due to the overhead of synchronization|
From all the differences, the first 2 are the most widely known and frequently asked in interviews
1. Navigable Map – NavigableMap in Java 6 is an extension of SortedMaplike TreeMapwhich provides convenient navigation method like lowerKey, floorKey, ceilingKey and higherKey. NavigableMap is added on Java 1.6 and along with these popular navigation method it also provide ways to create a Sub Map from existing Map in Java
2. LinkedHashMap – This class extends HashMap and maintains a linked list of the entries in the map, in the order in which they were inserted.
This allows insertion-order iteration over the map. That is, when iterating a LinkedHashMap, the elements will be returned in the order in which they were inserted.
You can also create a LinkedHashMap that returns its elements in the order in which they were last accessed.
3. TreeMap – The TreeMap class implements the Map interface by using a tree. A TreeMap provides an efficient means of storing key/value pairs in sorted order, and allows rapid retrieval.
You should note that, unlike a hash map, a tree map guarantees that its elements will be sorted in ascending key order.
How hashmap internally works in Java:
HashMap works on the principle of Hashing. To understand Hashing, we should understand the three terms first i.e Hash Function, Hash Value and Bucket.
The Hash function which returns an integer value is the hasCode() function. Note the point that this function belongs to the Object class (the topmost class in the Java heirarchy)
This is the code for the hash function(also known as hashCode method) in Object Class:
The most important point to note here is that hashCode method returns an int value.
So the Hash value is the int value returned by the hash function.
What is bucket?
A bucket is used to store key value pairs. A bucket can have multiple key-value pairs. In hash map, bucket uses simple linked list to store objects.
Hash map works on the principle of hashing
HashMap get(Key k) method calls hashCode method on the key object and applies returned hashValue to its own static hash function to find a bucket location(backing array) where keys and values are stored in form of a nested class called Entry (Map.Entry) . So you have concluded that from the previous line that Both key and value is stored in the bucket as a form of Entry object.
Whenever we call get( Key k ) method on the HashMap object . First it checks that whether key is null or not.
If key is null , then Null keys always map to hash 0, thus index 0.
If key is not null then, it will call hashfunction on the key object i.e. key.hashCode(), so after key.hashCode() returns hashValue, which is int hash = hash(hashValue) , and now, it applies returned hashValue into its own hashing function.
Now the final hashvalue is used to find the bucket location at which the Entry object is stored.
A question might arise as to what if two different keys have the same hashcode?
The answer is the equals() method. It is important to remember over that each bucket in a hashmap is a simple linked list.
Be aware, it is not java.util.LinkedList. It is just a linked list and much simpler implementation specifically designed for map.
So what we do, is we traverse the list, comparing keys in each entries using key.equals() until it returns true. Then the corresponding Object value is returned.
Hashmap works on the hashing principle in Java web development. Experts are making sound practices for java web development using Hashmaps. You can also learn the trick of using Hashmaps in java by following the steps discussed above.