hash and indexFor method in HashMap

Java HashMap:

Target AudienceThis post is for the people who already have good understanding of how HashMap works in java and want to understand more about hash and indexFor method.

In this post, we will see how hash and indexFor method works internally in hashmap. hash and indexFor methods belong to HashMap class. Why JDK developers need to have another hash function when  key object’s have there own hashcode method.
Lets see code for hash and indexFor

As java doc says about hash:
Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions. This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower bits. Note: Null keys always map to hash 0, thus index 0.

Lets understand this with the help of example: Lets say key object’s hashcode() returns only 3 values 31,63 and 95. 31,63 and 95 are integers, so all are 32 bits.
Now lets say our hashmap’s lenth is 16(2^4, Hashmap’s length will be always in power of two)

What if we do not use hash function:

Now if we do not use hash function then
indexFor will return :

31=00000000000000000000000000011111 => 1111=15
63=00000000000000000000000000111111  => 1111=15
95=00000000000000000000000001011111 => 1111=15

Why so?
because when we call indexFor function.It will do AND between 31&15 , 63&15 and 95&15.
For ex. 95&15
00000000000000000000000001011111 &00000000000000000000000000001111
so (2^n-1) will always have sequence of 1’s in it.so what matters here it last n bits as 0&1 is always 0.
In above example, all have 1111 in end that is why they are returning same index.
so although we have different hashcode,each Entry object will be stored at 15 index only.

What if we  use hash function:

If we use hash function then :
On each hashcode, first hash will  be applied.

31=00000000000000000000000000011111 => 00000000000000000000000000011110
63=00000000000000000000000000111111  => 00000000000000000000000000111100
95=00000000000000000000000001011111 => 00000000000000000000000001011010

now after passing new hash to indexFor.It will return :
00000000000000000000000000011110 =>1110=14
00000000000000000000000000111100 =>1100=12
00000000000000000000000001011010 =>1010=10

After applying hash function, above hashcodes are returning different index so hash function is redistributing elements in hashmap thus less collisions and better performance.
The main purpose of hash operation is to make the hashcode differences visible in the least significant bits so that the hashmap elements can be distributed evenly across the buckets


  • If two key objects have same hashcode, then they will always go to same index in table array
  • If two key objects do not have same hashcode then they may or may not go to same index in table array.


You may also like:

Related Posts

  • 10 September

    How to remove element from Arraylist in java while iterating

    Table of ContentsIntroductionUsing Collection’s removeIf() methodUsing ListIterator classUsing removeAll() methodUsing Java 8 Stream to filter List itemsConclusion Introduction In this tutorial, you will learn how to remove element from Arraylist in java while iterating using different implementations provided by Java. It is necessary to understand the right way to remove items from a List because […]

  • Print HashMap in java
    30 June

    Print HashMap in Java

    Table of ContentsPrint from the HashMap ReferencePrint HashMap using foreach method with keyset()Print HashMap using Consumer with entrySet()Print HashMap using Arrays’s asList() methodPrint HashMap using Collections’s singletonList()Print HashMap using getkey() and getValue with entrySet()Print HashMap using BiConsumerPrint HashMap using IteratorPrint HashMap using custom ObjectsConclusion In this article, we will see how to print HashMap in […]

  • Print LinkedList in java
    26 June

    Print LinkedList in java

    Table of ContentsJava inbuilt LinkedListPrint LinkedList using a for loopPrint LinkedList using Enhanced for loopPrint LinkedList using streamsPrint LinkedList using toString() methodPrint LinkedList using IteratorPrint LinkedList using custom objectsCustom singly LinkedListHow to print a custom singly LinkedListConclusion Java inbuilt LinkedList Java inbuilt LinkedList class uses doubly linked list as internal data structure to store its […]

  • Java Set to Array
    12 May

    Java Set to Array

    Table of Contents1. Using Java 8’s Stream2. Using toArray()3. Using toArray(IntFunction) [Java 11]4. Using System.arraycopy()5. Using Arrays.copyOf6. Using simple iteration7. Using Guava library7.1 Using FluentIterable7.2 Using Iterables In this post, we will learn java set to array conversion. There are many ways to convert set to an array. 1. Using Java 8’s Stream If you […]

  • Print ArrayList in java
    11 May

    Print ArrayList in Java

    Learn about how to print ArrayList in java in different ways.

  • 15 April

    How to Deep Copy Arraylist in Java

    Learn about how to create deep copy of ArrayList in different ways.

Leave a Reply

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

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.