How to implement the "chain method"?

Chaining method

Collision resolution using chains. Each cell of the array H is a pointer to a linked list (chain) of key-value pairs corresponding to the same key hash value. Collisions simply lead to the fact that there are chains with a length of more than one element.

Operations of searching or deleting an element require viewing all the elements of the corresponding chain in order to find an element with a given key in it. To add an element, you need to add an element to the end or the beginning of the corresponding list, and if the fill factor becomes too large, increase the size of the array H and rebuild the table.

Assuming that each element can fall into any position of the table H with equal probability, and regardless of where any other element falls, the average operation time of the element search operation is Θ (1 + α), where α is the table fill factor.

import java.util.Map; import java.util.HashMap; public class hashmap { public static void main(String[] args) { Map<String, String> hashmap = new HashMap<String, String>(); hashmap.put("key1", "value1"); hashmap.put("key1", "value2"); } }

    1 answer 1

    Probably you want to make your HashMap implementation in the HashMap library already and it works. Here is a series of videos where the process of creating a simple HashMap is described in detail: Creating a HashMap part 1

    • I want that when adding records with the same key, the values ​​are not overwritten but added to the list of this key - aaa
    • @aaa for this you have to write your HashMap with library it will not work. The condition is not to add the same keys sewn into the depths of the HashMap class. But this by the way will have nothing to do with resolving the collisions that are mentioned in the article that you quoted in the question. And the method you are talking about is already implemented in HashMap only there it is a question of collisions that are known not to occur often. For this, it is necessary that the same hashCode be calculated for different objects. Decide that you want to store duplicate keys or resolve conflicts, these are different things. - Pavel
    • At the very beginning of this article it is said that the solution of collisions is carried out using the chain method habrahabr.ru/post/128017 - aaa
    • @aaa yes it is. Just solving collisions by adding them to the chain, and simply adding the same values ​​to the chain is not the same thing. In the case of collisions, adding occurs only if the equals method test gives false while the hashcodes are equal. In general, to figure out how the hashtables work, you must first delve into the equals() and hashCode() device. Since all the hash table logic is built on them. That's why I answered you and gave a link to a series of videos, because until you figure out the equals() and hashCode() all the time it will not be clear. - Pavel