Find the hash table in HashMap
When I began to investigate such a phenomenon as a hash table, I realized that it is an array, each cell of which stores a list that is parameterized by two types: key and value.
When I got into the sources HashMap, 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 it wasn't her?
3 answers
The array you present is the basis for storing the hash table.
But in addition, each element of such an array (bucket) contains a reference to the first element linked list (JDK 7 and earlier), or a reference to the first element linked list/a reference to the root node balanced tree (JDK 8).
In the linked list, or in the balanced tree, there are pairs that fell into the same basket.
Example for a messenger the list:
This is how this hash table is stored.
If you looked at what this class is, you would see that it implements, among other things, a singly linked 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 a descendant of Node, so that in complex cases it is possible to implement the storage of a single bucket not as a list, but as a tree.
You are confusing the interface and the implementation. A HashMap is a table where each key has a single value. What you found is not the HashMap itself, but only a special structure for storing data.