Java HashMap Examples

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:

Map<String, Integer> map = new HashMap<>();

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 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:

map.put("Key1", 1);
map.put("Key2", 2);
map.put("Key3", 3);

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:

package com.explainjava;
 
import java.util.HashMap;
import java.util.Map;
 
public class HashMapMutableKeyExample {
 
    public static void main(String[] args) {
        Map<Key, Integer> map = new HashMap<>();
        Key key = new Key("1");
 
        map.put(key, 1);
        System.out.println(map.get(key)); // returns 1
 
        key.setS("2");
        System.out.println(map.get(key)); // returns null
    }
 
    public static class Key {
 
        private String s;
 
        public Key(String s) {
            this.s = s;
        }
 
        public void setS(String s) {
            this.s = s;
        }
 
        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Key key = (Key) o;
            return Objects.equals(s, key.s);
        }
 
        @Override
        public int hashCode() {
 
            return Objects.hash(s);
        }
    }
}

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 a key, the 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 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:

map.get("Key1");                         // returns 1
map.get("Not Existing Key");             // returns null
map.getOrDefault("Not Existing Key", 5); // returns 5

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:

map.remove("Key1"); // returns 1
map.remove("Not Existing Key"); // returns null
map.remove("Key2", 10000); // returns false, because values not matches
map.remove("Key3", 3); // returns true

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

map.entrySet().removeIf(entry -> Integer.valueOf(3).equals(entry.getValue()));

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:

map.clear();

Internal Implementation

What data structure is inside of HashMap do you think?

Inside of HashMap is a usual array!

transient Node<K,V>[] table;

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 the 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 (Java HashMap Time Complexity O(n))

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

MethodTime 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 the 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 getting | putting | removing a value from a key in a HashMap? What happens in case of a 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 the purpose of capacity and load factor in HashMap? What are default values? When is HashMap growing?
  • How to safely remove entries by value?

My “325 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.

Leave a Comment