Collisions in java hashmap

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

Источник

Performance Improvement for HashMap in Java 8

In our last post, we discussed the top five momentum builders for adoption of Java 8 in enterprises. In this post, we will dive deeper into JDK 8’s new strategy for dealing with HashMap collisions. Hash collision degrades the performance of HashMap significantly. With this new approach, existing applications can expect performance improvements in case they are using HashMaps having large number of elements by simply upgrading to Java 8.

Hash collisions have negative impact on the lookup time of HashMap. When multiple keys end up in the same bucket, then values along with their keys are placed in a linked list. In case of retrieval, linked list has to be traversed to get the entry. In worst case scenario, when all keys are mapped to the same bucket, the lookup time of HashMap increases from O(1) to O(n).

Java 8 has come with the following improvements/changes of HashMap objects in case of high collisions.

• The alternative String hash function added in Java 7 has been removed.
• Buckets containing a large number of colliding keys will store their entries in a balanced tree instead of a linked list after certain threshold is reached.

Above changes ensure performance of O(log(n)) in worst case scenarios (hash function is not distributing keys properly) and O(1) with proper hashCode().

How linked list is replaced with binary tree?

In Java 8, HashMap replaces linked list with a binary tree when the number of elements in a bucket reaches certain threshold. While converting the list to binary tree, hashcode is used as a branching variable. If there are two different hashcodes in the same bucket, one is considered bigger and goes to the right of the tree and other one to the left. But when both the hashcodes are equal, HashMap assumes that the keys are comparable, and compares the key to determine the direction so that some order can be maintained. It is a good practice to make the keys of HashMap comparable.

This JDK 8 change applies only to HashMap, LinkedHashMap and ConcurrentHashMap.

Based on a simple experiment of creating HashMaps of different sizes and performing put and get operations by key, the following results have been recorded.

1. HashMap.get() operation with proper hashCode() logic

Number Of Records	Java 5	Java 6	Java 7	Java 8
10,000	4 ms	3 ms	4 ms	2 ms
100,000	7 ms	6 ms	8 ms	4 ms
1,000,000	99 ms	15 ms	14 ms	13 ms

2. HashMap.get() operation with broken (hashCode is same for all Keys) hashCode() logic

Number Of Records	Java 5	Java 6	Java 7	Java 8
10,000	197 ms	154 ms	132 ms	15 ms
100,000	30346 ms	18967 ms	19131 ms	177 ms
1,000,000	3716886 ms	2518356 ms	2902987 ms	1226 ms
10,000,000	OOM	OOM	OOM	5775 ms

3. HashMap.put() operation with proper hashCode() logic

Number Of Records	Java 5	Java 6	Java 7	Java 8
10,000	17 ms	12 ms	13 ms	10 ms
100,000	45 ms	31 ms	34 ms	46 ms
1,000,000	384 ms	72 ms	66 ms	82 ms
10,000,000	4731 ms	944 ms	1024 ms	99 ms

4. HashMap.put() operation with broken (hashCode is same for all Keys) hashCode() logic

Number Of Records	Java 5	Java 6	Java 7	Java 8
10,000	211 ms	153 ms	162 ms	10 ms
100,000	29759 ms	17981 ms	17653 ms	93 ms
1,000,000	3527633 ms	2509506 ms	2902987 ms	333 ms
10,000,000	OOM	OOM	OOM	3970 ms

The above experiment demonstrates the power of this changed approach in improving the performance of existing Java applications. While this is an internal detail, simply upgrading to JDK 8 from older JDK versions will allow certain applications to see performance improvements if they use HashMaps heavily and have a large amount of entries in the HashMaps.

In our next post, we will discuss the use of lambda expressions in Java 8 for applying functional constructs.

Источник