How Does HashMap Work in Java?

machine code

Java is one of the most commonly used programming languages worldwide.

With the Java Virtual Machine (JVM) incorporated on an impressive array of platforms from enterprise mainframes to smartphones, compiled Java applications can run on nearly any device imaginable.

Java developers remain in high demand. Although estimates vary among sources, there is a population of between 9 and 10 million Java developers in the global application development community.

To fellow Java developers, this means there is essentially an unlimited resource of forums, technical expertise, and experience available to answer questions, share code examples, and discuss challenges and solutions related to coding Java applications.

One subject that generates considerable mention among developers is – how does HashMap work in Java?

What Is HashMap?

hashmap in java

First, you need a good understanding of what HashMap is in Java.

HashMap is a data structure that allows programs to store and retrieve an object in constant time, assuming you have the key available.

Hash functions come into play in linking the value to th associated key in HashMap. Java’s implementation of HashMap stores data with keys such that each object is stored utilizing a pair that includes the key and value.

How Does HashMap Work in Java?

Java Logo

Utilizing HashMap in Java is a fairly simple concept, at least at a high level:

Objects are stored utilizing a HashMap method call: put (key,value). The object can subsequently be retrieved with another method call: get(key)

Calling the put hashcode() method of a key object generates the hash function so that the hash map can assign a location in the hash table for the object, which will then store that value with a corresponding key.

Internally, HashMap retains the mapping in a Map.Entry form, as an object that contains both the key and the accompanying value of the object. Using a hashing algorithm, the key/value combination is assigned a “bucket” location in the hash table, which is actually an internal array with the bucket location being an index into the array.

By calling the get() method with the key, HashMap is then able to return the value stored in that location of the table, again using hashing process to locate the key’s location in the array.

HashMap internally calls hashcode() with the key object to determine the actual hash value that is used to locate a bucket for the object. The hash value will also be utilized to locate the bucket for that key when it is retrieved through a get() method.

Effective Java

Sale
Effective Java
  • Bloch, Joshua (Author)
  • English (Publication Language)
  • 412 Pages - 01/06/2018 (Publication Date) - Addison-Wesley Professional (Publisher)

Head First Java

Sale
Head First Java, 2nd Edition
  • O Reilly Media
  • Sierra, Kathy (Author)
  • English (Publication Language)
  • 688 Pages - 02/22/2005 (Publication Date) - O'Reilly Media (Publisher)

 

 

 

 

HashMap Storage and Collisions

The issue with the HashMap array is that its size is fixed, so there are only so many buckets available in the table. This makes it conceivable that two objects (pairs of key,value) could have the same hashcode value. This is known as a collision. When this occurs, HashMap will generate a linked list, retaining the original bucket location and creating a “next” node for storing the new entry.

HashMap keys are immutable, so updating the bucket assignment is not an option, which is why linked lists are the solution to collisions.

When a get is used that equates to a bucket that includes a linked list, the method can include the equal() operand, which instructs the method to return the object where the key is equal to the requested key. HashMap will follow the linked list and return the correct value (the object in the list where the key matches).

Coding to allow for a linked list is relatively simple, when you’re aware of this phenomenon:

call keys.equals() method will return the correct node using the linked list to find the key that matches the request.

Since linked lists may result in performance issues due to proceeding through the list, Java 8 included an enhancement that replaces linked lists with a balanced tree structure, once the linked list exceeds a certain defined threshold. This improves worst-case performance problems related to HashMap collisions.

HashMap Variations

HashMap in Java includes a number of methods and subclasses that may be useful in certain applications:

ConcurrentHashMap differs from HashMap in several ways:

  • ConcurrentHashMap is thread-safe, where HashMap is not
  • HashMap is a better performer, partly because it is not thread-safe, allowing multiple uses simultaneously. ConcurrentHashMap can require threads to wait, slowing performance
  • ConcurrentHashMap does not allow nulls for key and values, where HashMap does

LinkedHashMap is a subclass of HashMap that provides a method of maintaining insertion-order. This technique utilizes a doubly-linked list to retain sequence of the objects in the data structure.

When to Use HashMap in Java

There are many good reasons to utilize HashMap in Java applications:

  • It is fast – hash methods for put and gets results in high performance
  • Storage and retrieval by key is required
  • Entry sequence is not an issue – this is not retained with a HashMap data structure
  • Reference by index is not needed

When key reference is needed for your application, HashMap is a great solution.

Reasons Not to Use HashMap

There are a variety of storage or application reasons not to utilize HashMap in Java:

  • When keys are not required or present in a data structure, such as sequential data objects that will not incorporate random (key) retrieval, arrays or linked lists would be more appropriate for your application.
  • If values can change after saving, HashMap is not a reasonable choice, since hash values are immutable.
  • Hash table storage can be costly strictly from a size viewpoint.
  • If you’re only storing a list of objects, an ArrayList or array would be a better choice.
  • Where order is critical, HashMap will simply not meet your requirements.
  • Since HashMap is not synchronous, it is not a good choice when there will be multiple concurrent threads reading and writing to the same map.

As a rule, HashMap in Java is not a good choice when sequence is important or keys are not needed.

Java: A Beginner's Guide

Sale
Java: A Beginner's Guide, Eighth Edition
  • Schildt, Herbert (Author)
  • English (Publication Language)
  • 720 Pages - 11/02/2018 (Publication Date) - McGraw-Hill Education (Publisher)

The Insiders' Guide

Sale
Elements of Programming Interviews in Java: The Insiders' Guide
  • Aziz, Adnan (Author)
  • English (Publication Language)
  • 482 Pages - 10/06/2015 (Publication Date) - CreateSpace Independent Publishing Platform (Publisher)

 

 

 

 

Continuing Enhancements for HashMap in Java

Developers can benefit from the continuous improvements in how HashMap works in Java, including updates made in Java Development Kit (JDK) versions 1.7 and 1.8:

Reduction in memory allocation requirements – empty maps formerly consumed memory that was not needed, so improvements have been implemented to limit the unnecessary demands for memory.

Collision handling – to avoid excessive linked lists caused by poor hashing that previously resulted in a performance impact, Java replaced that functionality with a true binary balanced tree that can be interpreted much more efficiently.

Overall performance of HashMap functions has improved on average by 20% in Java 8 as compared with Java 7. Even with poorly-derived hash map keys, HashMap returns the objects for the key specified much more quickly with the most current versions of Java, largely due to the elimination of the adoption of lengthy linked lists (again, where a threshold has been reached for use of a linked list).

Putting Your Knowledge of How HashMap Works in Java to Use

Java Logo

From a practical viewpoint, knowledge of how HashMap works, when to use it in applications, and when it makes more sense to avoid this data structure can play a contributing role in landing a career position as a Java developer. In fact, some of the most frequently asked questions are covered in the preceding material, so use this information to your advantage in responding to interview questions such as:

Q: How does the put() method work with HashMap in Java?

A: Hashcode() is called to generate a location/bucket to store the object, which is a paired value that includes the key and data

Q: What happens when you attempt to store (put) a key that already exists in HashMap?

A: The old value is overridden with the new value – no exception is returned for this condition.

Q: What happens when HashMap creates a second entry in the same bucket?

A: This is a HashMap collision. When it is encountered, HashMap will create a linked list for the duplicate entries, so that subsequent gets with equals() specified will follow the link to return the correct object from the linked list, that matches the key requested. When the linked list exceeds a set threshold, the linked list is converted to a binary balanced tree structure, for better performance.

Q: Does HashMap support duplicate keys?

A: No – duplicate keys are not allowed. If the same key is put() to the table, the value will be replaced.


Hardcore Java 1st Edition

Sale
Hardcore Java
  • Used Book in Good Condition
  • Robert Simmons (Author)
  • English (Publication Language)
  • 400 Pages - 01/01/2004 (Publication Date) - O'Reilly Media (Publisher)

Java for Beginners 2018

Java for Beginners 2018
  • Kotiyana, Mr (Author)
  • English (Publication Language)
  • 369 Pages - 02/03/2018 (Publication Date) - CreateSpace Independent Publishing Platform (Publisher)

 

 

 

 

With a good grasp of how HashMap works in Java, you’re equipped to make an informed decision on the use of this data structure for your Java application development.

What do you think?