How HashMap works in java

HashMap

HashMap (also known as HashTable) is a data structure that can map keys to values, used to implement an associative array. A HashMap uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.

Ideally, the hash function will assign each key to a unique bucket, but this situation is rarely achievable in reality and usually some keys will hash to the same bucket. Instead, most HashMap designs assume that hash collisions — different keys that are assigned by the hash function to the same bucket — will occur and must be accommodated in some way.

In most of the situations, HashMap turns out to be more efficient than search tree or any other table lookup structure. For this reason, HashMap is widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches and sets.

Time complexity

Average     Worst case
Space     O(n)         O(n)
Search     O(1)         O(n)
Insert     O(1)         O(n)
Delete     O(1)         O(n)


What is Hashing

The idea of hashing is to distribute the entries (key/value pairs) across an array of buckets or slots. Given a key, the algorithm computes an index that suggests where the entry can be found.

Hash

  •     Use hash value to group elements into slots, control by hash() method of HashMap,

Single LinkedList

  •     Each slot is a singly linked list, their key has the same hash value
  •     The slot index is controlled by indexFor() method of HashMap

More info on Collision resolution can be found at http://en.wikipedia.org/wiki/Hash_table 

Difference between HashMap and Hashtable

Both HashMap and Hashtable implements Map interface but there are some significant differences between them and based on these differences we need to decide where to use HashMap or Hashtable in Java

1. HashMap and HashTable classes are equivalent but HashMap is non-synchronized whereas HashTable is synchronized. So HashTable is thread-safe and can be shared among multiple threads but HashMap cannot be shared among multiple threads without synchronization. HashTable is having a feature like thread-safety, so it’s much slower than HashMap in single threaded environment and it’s recommended that if there is only one thread is accessing the HashMap then we need to use HashMap because it out-performs HashTable in this scenario.

2. HashMap allows null values for both key and value but HashTable does not allow null values for key and value.

3. Another significant difference between HashMap and Hashtable is that Iterator in the HashMap is a fail-fast iterator while the enumerator for the Hashtable is not and throw ConcurrentModificationException if any other Thread modifies the map structurally by adding or removing any element except Iterator’s own remove() method. But this is not a guaranteed behavior and will be done by JVM on best effort.

4. HashMap does not guarantee that over the time the order of the map will remain constant whereas HashTable guarantees.

HashMap works on principle of hashing, we have put() and get() method for storing and retrieving object from HashMap .When we pass both key and value to put() method to store on HashMap, it uses key object hashcode() method to calculate hashcode and then by applying hashing on that hashcode it identifies bucket location for storing value object. While retrieving it uses key object equals method to find out correct key value pair and return value object associated with that key. HashMap uses LinkedList in case of collision and object will be stored in next node of LinkedList. HashMap stores both key/value pair in every node of linked list. Each node is of type ‘Map.Entry’. HashMap will store values as long as different keys are used so if those different keys result in same hash value they will reside at the same index in the bucket, in different nodes of the LinkedList.

Let’s look at the default put and get methods of HashMap in Java.

 

Let’s analyze the code:

 

hashCode() method could be anything that ensures that hash value will be as unique as possible.
You can also implement your own HashMap with your own hash function.
Note that get() and put() have lot of code in common because before putting any key/value pair it checks if it already exists. When you invoke get(key) method,  the key is hashed and then index of the bucket is calculated using this hash value. The LinkedList at this index will be traversed till a ‘key’ with matching hash value and also being ‘equal’ to the input parameter.
Immutable objects make best keys because this ensures that hash value will remain same when putting in the value and when retrieving it. String objects are the best because of this; also they implement equals() and hashCode().

Soumitra

Software Professional, I am passionate to work on web/enterprise application. For more information please go to about me. You can follow on Twitter. You can be a friend on Facebook or Google Plus or Linkedin

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.