Starting to explore such a phenomenon as a hash-table, I realized that this is a kind of array, each cell of which stores a list that is parameterized by two types: a key and a value .

When I got into the HashMap source, I saw the following:

 transient Node<K,V>[] table;

If I understood everything correctly, and this is a hash table, then why is it a one-dimensional array? Or did I find something wrong, and this is not it?

    3 answers 3

    The array you present is the basis for storing the hash table.

    But besides this, each element of such an array ( bucket ) contains a link to the first element of the linked list (JDK 7 and earlier), or a link to the first element of the linked list / link to the root node of the balanced tree (JDK 8).

    In the linked list , or in a balanced tree there are pairs that fall into the same basket.

    Example for a linked list:

    enter image description here

    This is how the hash table is stored.

    • Did I understand he was two-dimensional just the second level as linked yes? - Pavel
    • one
      @Pavel, Strictly speaking, this structure cannot be called a two-dimensional array, but yes, you understood correctly. Each element of a given array can be either a linked list or a tree. - post_zeew
    • Well, I haven't done it yet. I have the following topic. Ok thank you very much for explaining. - Pavel

    If you looked at what kind of class, you would see that it implements, among other things, a simply connected list

     static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; // simple, isn't it?

    There is also a TreeNode, which is the heir of Node, so that in difficult cases it was possible to implement storing one basket not with a list, but with a tree.

      You confuse interface and implementation. HashMap is a table where one value corresponds to each key. What you found is not HashMap itself, but only a special structure for storing data.

      • one
        interface is Map - etki
      • well, yes, so I’m talking about the hash table for the HashMap, but I don’t understand about the interface, sorry (( - Pavel
      • one
        @Pavel, as was rightly noted above, the HashMap interface is a Map. And you look at the implementation details. The implementation can be anything. - Mikhail Vaysman
      • @Mikhail Vaysman Yes, I just have the following task: to create my own data structure with a hash table, and this is a completely new topic for me. And I just find out what are the ideas for the implementation of hash tables. And by the way, does the Map interface know something about the hash table? - Pavel
      • one
        @Pavel Map knows nothing about the hash table. I think you should take a simpler implementation of the hash table. - Mikhail Vaysman