Найти хэш-таблицу в HashMap

#java #коллекции #java_hashmap

Начав исследовать такое явление как hash-таблица, я понял, что это некий массив,
каждая ячейка которого хранит список, который параметризован двумя типами: ключ и значение. 

Когда я залез в исходники HashMap, то увидел следующее:

transient Node[] table;


Если я все правильно понял, и это и есть хеш-таблица, то почему тогда это одномерный
массив? Или я что-то не то нашел, и это не она?
    

Ответы

Ответ 1

Представленный Вами массив является основой для хранения хэш-таблицы.

Но кроме этого, каждый элемент такого массива (bucket) содержит ссылку на первый
элемент linked list (JDK 7 и ранее), либо ссылку на первый элемент linked list/ссылку
на корневой узел balanced tree (JDK 8).

В linked list, либо в balanced tree находятся пары, которые попали в одну и ту же
корзину.

Пример для связного списка:



Таким образом и хранится эта хэш-таблица.


Ответ 2

Если бы вы посмотрели, что это за класс, то увидели бы, что это он реализует помимо
всего прочего еще и односвязный список

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


Также есть TreeNode, который является наследником Node, чтобы в сложных случаях можно
было реализовать хранение одной корзины не списком, а деревом.


Ответ 3

Вы путаете интерфейс и реализацию. HashMap - это таблица, где каждому ключу соответсвует
одно значение. То что вы нашли это не сама HashMap, а лишь специальная структура для
хранения данных.