• Java
    • JAXB Tutorial
      • What is JAXB
      • JAXB Marshalling Example
      • JAXB UnMarshalling Example
  • Spring Tutorial
    • Spring Core Tutorial
    • Spring MVC Tutorial
      • Quick Start
        • Flow Diagram
        • Hello World Example
        • Form Handling Example
      • Handler Mapping
        • BeanNameUrlHandlerMapping
        • ControllerClassNameHandlerMapping
        • SimpleUrlHandlerMapping
      • Validation & Exception Handling
        • Validation+Annotations
        • Validation+ResourceBundle
        • @ExceptionHandler
        • @ControllerAdvice
        • Custom Exception Handling
      • Form Tag Library
        • Textbox Example
        • TextArea Example
        • Password Example
        • Dropdown Box Example
        • Checkboxes Example
        • Radiobuttons Example
        • HiddenValue Example
      • Misc
        • Change Config file name
    • Spring Boot Tutorial
  • Hibernate Tutorial
  • REST Tutorial
    • JAX-RS REST @PathParam Example
    • JAX-RS REST @QueryParam Example
    • JAX-RS REST @DefaultValue Example
    • JAX-RS REST @Context Example
    • JAX-RS REST @MatrixParam Example
    • JAX-RS REST @FormParam Example
    • JAX-RS REST @Produces Example
    • JAX-RS REST @Consumes Example
    • JAX-RS REST @Produces both XML and JSON Example
    • JAX-RS REST @Consumes both XML and JSON Example
  • Miscellaneous
    • JSON Parser
      • Read a JSON file
      • Write JSON object to File
      • Read / Write JSON using GSON
      • Java Object to JSON using JAXB
    • CSV Parser
      • Read / Write CSV file
      • Read/Parse/Write CSV File – OpenCSV
      • Export data into a CSV File
      • CsvToBean and BeanToCsv – OpenCSV

JavaInterviewPoint

Java Development Tutorials

How HashMap works in Java

April 9, 2014 by javainterviewpoint 1 Comment

How a HashMap Works internally has become a popular question in almost all the interview. As almost everybody knows how to use a HashMap or the difference between HashMap and Hashtable. But many fails when the question is how does a hashmap internally works.

So the answer to the question how does a hashmap works is that is it works based on the hashing principle but it is not as simple as it sounds. Hashing is the mechanism of assigning the unique code to a variable or attribute using some algorithm to enable easy retrieval. A true hashing mechanism should always return the same hashCode() when it is applied to the same object.

Then comes the question how does hashing help in storing and retrieving the value in HashMap. Many answers the value will be stored in the bucket and retrieved using the key if you think that is how it works then you are absolutely wrong.  To prove let’s take a look at the hashmap class.

     /**
     * The table, resized as necessary. Length MUST always be a power of two.
     */
     transient Entry[] table;

So what is the use of Entry[] in a hashmap? Because the HashMap stores the Objects as Entry instances, not as key and value

What is Entry Class?

The HashMap has an inner class called as Entry Class which hold the key, value stuff. And there is something called as next, hash which you will get to know a bit later.

 static class Entry<K,V> implements Map.Entry<K,V> 
 {
     final K key;
     V value;
     Entry<K,V> next;
     final int hash;
     ........
 }

As of now, you know that the hashmap stores the Entry instances in an array and not as a key,value pairs. In order to store a value you will use the put() method of the hashmap, so now let’s dig into that and see how it works.

how put() method works internally ?

The Code implementation of the put method will be like below

public V put(K key, V value) 
{
    if (key == null)
       return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) 
    {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
         {
             V oldValue = e.value;
             e.value = value;
             e.recordAccess(this);
             return oldValue;
          }
     }
     modCount++;
     addEntry(hash, key, value, i);
     return null;
 }
  • First, it checks for the if the key given is null or not, if the given key is null it will be stored in the ‘0’th position as the hashcode of null will be zero.
  • Then it applies the hashcode to the key.hashCode() by calling the hashcode method. In order to get the value within the limits of an array the hash(key.hashCode())is called which does some shifting operations to the hashcode.
  • The indexFor() method is used to get the exact location to store the Entry object.
  • Then comes the most important part what happens if two different object has the same hashcode( eg : Aa,BB will have the same hashcode) and will it be stored in the same bucket. To handle this let’s think of the LinkedList in data structure it will have a next attribute which will always point to the next object . The same way the next attribute in the Entry class points to the next object. Using this different objects with the same hashcode will be placed next to each other.
  • In the case of the Collision , the HashMap checks for the value of the next attribute if it is null it inserts the Entry object in that location , if next attribute is not null then it keeps the loop running till next attribute is null then stores the Entry object there.

How duplicate key is prevented in hashmap ?

As we all know hashmap doesn’t allow duplicates in the key even though we insert the same key with different values the latest value only is returned.

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

public class HashMapEg 
{
	public static void main(String[] args) 
	{
		Map map = new HashMap();
		map.put(1,"sam");   
		map.put(1,"Ian");   
		map.put(1,"Scott");   
		map.put(null,"asdf");

		System.out.println(map);  

	}

}

For the above code, you will get the output as {null=asdf, 1=Scott}  as the values sam,Ian will be replaced by Scott , So how does this happen.

All the Entry Objects in the LinkedList will have the same hashcode but hashmap uses  equals () method checks the equality if key.equals(k) is true then it will replace the value object inside the Entry class and not the key. So this way it prevents the duplicate key being inserted.

how get() method works internally ?

It is almost the same logic as applied in put will be used to retrieve the value.

public V get(Object key) 
{
    if (key == null)
       return getForNullKey();
     int hash = hash(key.hashCode());
     for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) 
     {
         Object k;
         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
             return e.value;
     }
         return null;
 }
  • First, it gets the hashcode of the key object which is passed and finds the bucket location.
  • If the correct bucket is found it returns the value (e.value)
  • If no match is found it returns null.

What happens if two keys have the same hashcode?

The same collision resolution mechanism will be used here  key.equals(k)  will check until it is true, if true it returns the value of it.

Hope this article clarifies the troublesome HashMap internal mechanism. Happy Learning !! 🙂

Other interesting articles which you may like …

  • JVM Architecture – Understanding JVM Internals
  • Object and Object Class in Java
  • Difference between JDK, JRE and JVM
  • Components of Java Development Kit (JDK)
  • What is a Class in Java with Example
  • How to open .class file in Java
  • How to Set Classpath for Java in Windows
  • ClassNotFoundException Vs NoClassDefFoundError
  • How to make a class Immutable in Java
  • Polymorphism in Java – Method Overloading and Overriding
  • Types of polymorphism in Java
  • Types of Inheritance in Java
  • Java does not supports Multiple Inheritance Diamond Problem?
  • Java Method Overloading Example
  • Java Constructor Overloading Example
  • Java this keyword | Core Java Tutorial
  • Java super keyword
  • Abstract Class in Java
  • Interface in Java and Uses of Interface in Java
  • What is Marker Interface

Filed Under: Java, Java Interview Tagged With: collision resolution, hashCode, hashing principle, hashmap, Internal mechanism of hashmap, Working of Hashmap

Comments

  1. Rajesh says

    August 31, 2018 at 11:43 am

    Nice… Very Great explanation. Thanks for you effort .

    Reply

Leave a Reply Cancel reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Java Basics

  • JVM Architecture
  • Object in Java
  • Class in Java
  • How to Set Classpath for Java in Windows
  • Components of JDK
  • Decompiling a class file
  • Use of Class.forName in java
  • Use Class.forName in SQL JDBC

Oops Concepts

  • Inheritance in Java
  • Types of Inheritance in Java
  • Single Inheritance in Java
  • Multiple Inheritance in Java
  • Multilevel Inheritance in Java
  • Hierarchical Inheritance in Java
  • Hybrid Inheritance in Java
  • Polymorphism in Java – Method Overloading and Overriding
  • Types of Polymorphism in java
  • Method Overriding in Java
  • Can we Overload static methods in Java
  • Can we Override static methods in Java
  • Java Constructor Overloading
  • Java Method Overloading Example
  • Encapsulation in Java with Example
  • Constructor in Java
  • Constructor in an Interface?
  • Parameterized Constructor in Java
  • Constructor Chaining with example
  • What is the use of a Private Constructors in Java
  • Interface in Java
  • What is Marker Interface
  • Abstract Class in Java

Java Keywords

  • Java this keyword
  • Java super keyword
  • Final Keyword in Java
  • static Keyword in Java
  • Static Import
  • Transient Keyword

Miscellaneous

  • newInstance() method
  • How does Hashmap works internally in Java
  • Java Ternary operator
  • How System.out.println() really work?
  • Autoboxing and Unboxing Examples
  • Serialization and Deserialization in Java with Example
  • Generate SerialVersionUID in Java
  • How to make a class Immutable in Java
  • Differences betwen HashMap and Hashtable
  • Difference between Enumeration and Iterator ?
  • Difference between fail-fast and fail-safe Iterator
  • Difference Between Interface and Abstract Class in Java
  • Difference between equals() and ==
  • Sort Objects in a ArrayList using Java Comparable Interface
  • Sort Objects in a ArrayList using Java Comparator

Follow

  • Coding Utils

Useful Links

  • Spring 4.1.x Documentation
  • Spring 3.2.x Documentation
  • Spring 2.5.x Documentation
  • Java 6 API
  • Java 7 API
  • Java 8 API
  • Java EE 5 Tutorial
  • Java EE 6 Tutorial
  • Java EE 7 Tutorial
  • Maven Repository
  • Hibernate ORM

About JavaInterviewPoint

javainterviewpoint.com is a tech blog dedicated to all Java/J2EE developers and Web Developers. We publish useful tutorials on Java, J2EE and all latest frameworks.

All examples and tutorials posted here are very well tested in our development environment.

Connect with us on Facebook | Privacy Policy | Sitemap

Copyright ©2023 · Java Interview Point - All Rights Are Reserved ·