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

266
28 января 2017, 09:26

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

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

transient Node<K,V>[] table;

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

Answer 1

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

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

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

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

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

Answer 2

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

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?

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

Answer 3

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

READ ALSO
Размещение сцены в Tab

Размещение сцены в Tab

Есть ряд окон, которые я перевожу на вкладкиНо при простом переносе, они не хотят растягиваться

269
Как реализовать добавление новостей в Android приложение?

Как реализовать добавление новостей в Android приложение?

Добрый день! Имеется некое приложение в котором необходимо реализовать добавление новостейНовости хранятся на сервере

294
Android переводчик online/offline

Android переводчик online/offline

Всем привет, есть задача написать переводчик, который будет работать как с интернетом, так и без негоС интернетом тут проблемы нет: любое...

296
Возможно ли задать Expandable Listview иерархию вложенности в виде линий?

Возможно ли задать Expandable Listview иерархию вложенности в виде линий?

те как я понял у системы андройд нет элемента Treeview с возможностью отображения линий вложенности , для создания вложенности мы можешь использовать...

282