Can you please tell us how collisions are resolved in HashMap in java and what is the difference between the resolution of these collisions?

  • What is meant by collision implementations? Can you open a question and add it with examples (with arrays and LinkedList )? - default locale

1 answer 1

Probably, after all, are not implemented , but allowed ? And not the interface Map<K,V> , but the class HashMap<K,V> ? If so, read below.

There are two main ways to resolve collisions:

  1. Chain method. In this case the basket ( bucket ) can store several items, and they are stored, in most cases, in the form of a linked list .

  2. The method of open addressing. Here, when a collision occurs, a search for some free cell occurs, where the next element is added.

In Java, to resolve collisions, the chaining method is used.

Initially, the basket in the HashMap is a linked list . If a collision occurs, the next pair is added to this list.

In the latest versions of JDK, if the size of the linked list becomes more than 8 ( TREEIFY_THRESHOLD constant), then the TREEIFY_THRESHOLD list is converted into a tree, while in the worst case it is possible to find an element in O(log(n)) , and not for O(n) , as in the linked list.