[java] How does a Java HashMap handle different objects with the same hash code?

HashMap structure diagram

HashMap is an array of Entry objects.

Consider HashMap as just an array of objects.

Have a look at what this Object is:

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

Each Entry object represents a key-value pair. The field next refers to another Entry object if a bucket has more than one Entry.

Sometimes it might happen that hash codes for 2 different objects are the same. In this case, two objects will be saved in one bucket and will be presented as a linked list. The entry point is the more recently added object. This object refers to another object with the next field and so on. The last entry refers to null.

When you create a HashMap with the default constructor

HashMap hashMap = new HashMap();

The array is created with size 16 and default 0.75 load balance.

Adding a new key-value pair

  1. Calculate hashcode for the key
  2. Calculate position hash % (arrayLength-1) where element should be placed (bucket number)
  3. If you try to add a value with a key which has already been saved in HashMap, then value gets overwritten.
  4. Otherwise element is added to the bucket.

If the bucket already has at least one element, a new one gets added and placed in the first position of the bucket. Its next field refers to the old element.

Deletion

  1. Calculate hashcode for the given key
  2. Calculate bucket number hash % (arrayLength-1)
  3. Get a reference to the first Entry object in the bucket and by means of equals method iterate over all entries in the given bucket. Eventually we will find the correct Entry. If a desired element is not found, return null

Examples related to java

Under what circumstances can I call findViewById with an Options Menu / Action Bar item? How much should a function trust another function How to implement a simple scenario the OO way Two constructors How do I get some variable from another class in Java? this in equals method How to split a string in two and store it in a field How to do perspective fixing? String index out of range: 4 My eclipse won't open, i download the bundle pack it keeps saying error log

Examples related to hashmap

How to split a string in two and store it in a field Printing a java map Map<String, Object> - How? Hashmap with Streams in Java 8 Streams to collect value of Map How to convert String into Hashmap in java Convert object array to hash map, indexed by an attribute value of the Object HashMap - getting First Key value The type java.util.Map$Entry cannot be resolved. It is indirectly referenced from required .class files Sort Go map values by keys Print all key/value pairs in a Java ConcurrentHashMap creating Hashmap from a JSON String

Examples related to hashcode

Hashing with SHA1 Algorithm in C# HashMaps and Null values? How to create a HashMap with two keys (Key-Pair, Value)? What is hashCode used for? Is it unique? How does a Java HashMap handle different objects with the same hash code? Hashcode and Equals for Hashset What is the use of hashCode in Java? Good Hash Function for Strings Why do I need to override the equals and hashCode methods in Java? Memory address of variables in Java

Examples related to hash-function

How does a Java HashMap handle different objects with the same hash code? MySQL Check if username and password matches in Database Maximum length for MD5 input/output