HashMap in Java: Definitive Guide

Java HashMap is not a thread-safe implementation of key-value storage, it doesn’t guarantee an order of keys as well.

In the scope of this article, I’ll explain:

  • HashMap internal implementation
  • methods and functions and its performance (O(n) time complexity)
  • collisions in HashMap
  • interview questions and best practices

Keep reading and use a table of contents for quick navigation.

HashMap in Java: Methods and Functions

I don’t want to list all methods in HashMap Java API.

I’ll explain the main or the most frequently used methods in HashMap, others you can take a look without my help.

Let’s go.

How to Initialize

Initialize HashMap data structure example:

A string is a type of key in the map, Integer is a type of a value.

How To Put Value

There are 3 methods to put value/values into HashMap:

  • public V put(K key, V value)  – puts a value for a key
  • public void putAll(Map<? extends K, ? extends V> m) – puts all values from another HashMap into the current one
  • public V putIfAbsent(K key, V value)  – if this key is not already associated with a value, puts a given value and returns null, otherwise returns the current value

Example:

Now 1 is associated with “Key1”, 2 with “Key2” and 3 with “Key3”.

HashMap allows nullable keys and values.

I marked that because for example  HashTable and ConcurrentHashMap JavaDocs say: “neither the key nor value can be null”.

It’s a good practice to use immutable objects as a key, further you’ll understand why.

Take a look at an example first:

Let me explain:

  • I’ve created a Key class, that contains string value and I can change this value via a setter. I override  equals() and hashCode() methods as well.
  • I put a value for key, hash code is calculated and bucket found to store the value
  • If I change an internal string in key object hashCode() will return different number, so get() method will try to find a value in another bucket, that’s why a result is null.

How to Get Value by Key

There are 2 methods to retrieve a value from HashMap:

  • public V get(Object key) – returns a value for a specific key
  • public V getOrDefault(Object key, V defaultValue) – if value is null returns default value, otherwise current value

Example:

How to Remove a Value

There are 2 useful methods to remove the value in Java HashMap:

  • public V remove(Object key) – removes a value by key and returns this value
  • public boolean remove(Object key, Object value) – removes an entry only if key and value matches, returns true if entry deleted

Example:

If you want to remove entries by the specific value you can get entrySet() and use removeIf() method:

removeIf() method accepts a Predicate (functional interface) that return true if the entry should be removed.

If you want to remove all entries in HashMap use can use clear() method:

Internal Implementation

What data structure is inside of HashMap do you think?

Inside of HashMap is a usual array!

Each array cell contains a reference to a head Node of a linked list, sometimes this cell is called bucket.

So how HashMap put() method works internally?

First of all, let’s define what is a collision in Java HashMap and how put method resolves it.

The collision is a situation when two objects hashCode() returns the same value, but equals() returns false.

An algorithm is a following:

  • get hashCode() value from the key object.
  • find an index in the array for that hash code (source (length - 1) & hash).
  • get a head node of the linked list by index in the array.
  • iterating through the list and comparing node values and given value using equals() method.
  • if equals() returns false for all values in the list – new node is added to the tail, otherwise node value is replaced with a given value.

If a number of buckets (capacity, a default value is 16) * load factor (0.75 by default) < number of elements – HashMap increases capacity in two times and internal objects are rehashed (internal array is rebuilt).

get() method works in the same way:

  1. find an index
  2. iterate through the list and compare node values using equals()
  3. if equals() return true – returns a value, otherwise returns null

Performance (Time Complexity O(n))

Here we suggest that equals and hashCode methods are implemented well and we almost don’t have collisions.

Method Time Complexity
 get(Object key) O(1)
 remove(Object key) O(1)
 put(K key, V value) O(1)

If we have a lot of collisions before Java 8 time complexity could grow even to O(n) because it’s an array of linked lists inside of HashMap and if all values are associated to the same cell (bucket) you need to iterate through the whole list to find required value.

Since Java 8 if HashMap contains more than 7 elements in the same bucket linked list transforms to a tree and time complexity changes to O(log n).

Interview Questions

I’m not going to write answers here because you can find it above.

This is the most popular interview questions related to the HashMap:

  • What is an internal implementation of HashMap?
  • What are collisions and how HashMap handles it?
  • What kind of object is better to use as a key and why? What happens if I change a field in a key object?
  • What time complexity of get | put | remove operation? What happens in case of big amount of collisions?
  • What was performance improvement made in HashMap in the scope of Java 8 release?
  • What is a difference between HashMap and HashTable (all methods are synchronized in HashTable and it doesn’t allow nullable key and value)
  • What are a purpose of capacity and load factor in HashMap? What are default values? When is HashMap growing?
  • How to safely remove entries by value?

My “225 Java interview questions” post could be useful for you as well, answers could be found in Java tutorials.

That’s all I wanted to tell you about HashMap in Java. If you have any questions – leave a comment.

1 Star2 Stars3 Stars4 Stars5 Stars
Loading...
Scroll Up