Hashmap collision in java

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.

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

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) < Mapmap = 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); >> >

• 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

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

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:

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

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.

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

Источник

Collision in Hashmap in Java

Java collections interface provides the functionality of the hash table data structure using its HashMap class. This class stores the elements in a key-value pair where keys act as identifiers and are unique associated with a value in the map.

In this tutorial, we will discuss collision in Java.

The HashMap key contains a hashcode, and a equals() method. Whenever we insert a new entry to the Map, it checks for the hashcode. It parses through the entire pool of objects, searching for similarity of the hashcode using the equals() method.

If any entry is existent, the new value will then replace the primarily existing value. Otherwise, it will simply create a whole new key-value pair.

Collision happens when multiple keys hash to the same bucket or, say when two or more objects have the same hashcode but are different. When two keys get hashed to the same value, a linked list is formed at the bucket location, where all the information is stored as an entry of the map, which contains the key-value pair.

Accessing any object could turn out to be cumbersome if the entries are present inside the lists. These linked lists were converted to binary trees from Java 8 version.

HashMap handles collision cases very efficiently using a concept known as chaining, which suggests storing the values in a linked list or a binary tree as indicated by the conversion of methodology from Java 8.

Related Article — Java HashMap

Copyright © 2023. All right reserved

Источник