32. Как устроена HashMap, сложность основных операций? (Расскажите про принцип корзин)

HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени.

Разрешение коллизий осуществляется с помощью метода цепочек.

Особенности:

• Добавление элемента выполняется за время O(1), потому как новые элементы вставляются в начало цепочки;
• Операции получения и удаления элемента могут выполняться за время O(1), если хэш-функция равномерно распределяет элементы и отсутствуют коллизии. Среднее же время работы будет Θ(1 + α), где α — коэффициент загрузки. В самом худшем случае, время выполнения может составить Θ(n)
• (все элементы в одной цепочке);
• Ключи и значения могут быть любых типов, в том числе и null. Для хранения примитивных типов используются соответствующие классы-оберки;
• Не синхронизирован.

Создание объекта:

Map<String, String> hashmap = new HashMap<String, String>();

Новоявленный объект hashmap, содержит ряд свойств:

• table — Массив типа Entry[], который является хранилищем ссылок на списки (цепочки) значений;
• loadFactor — Коэффициент загрузки. Значение по умолчанию 0.75 является хорошим компромиссом
• между временем доступа и объемом хранимых данных;
• threshold — Предельное количество элементов, при достижении которого, размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor);
• size — Количество элементов HashMap-а;

Добавление элементов в объект HasMap:

• Сначала ключ проверяется на равенство null. Если это проверка вернула true, будет вызван метод putForNullKey(value)
• Далее генерируется хэш на основе ключа. Для генерации используется метод hash(hashCode), в который передается key.hashCode()
• С помощью метода indexFor(hash, tableLength), определяется позиция в массиве, куда будет помещен элемент.
• Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке.
• Хэш и ключ нового элемента поочередно сравниваются с хэшами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается.
• Если же предыдущий шаг не выявил совпадений, будет вызван метод addEntry(hash, key, value, index) для добавления нового элемента.

Разрешение коллизий с помощью метода цепочек:

Когда массив table[] заполняется до предельного значения, его размер увеличивается вдвое и происходит перераспределение элементов с помощью методов resize(capacity) и transfer(newTable).

Метод transfer() перебирает все элементы текущего хранилища, пересчитывает их индексы (с учетом нового размера) и перераспределяет элементы по новому массиву.

У HashMap есть такая же «проблема» как и у ArrayList — при удалении элементов размер массива table[] не уменьшается. И если в ArrayList предусмотрен метод trimToSize(), то в HashMap таких методов нет. HashMap имеет встроенные итераторы, такие, что вы можете получить список всех ключей keySet(), всех значений values() или же все пары ключ/значение entrySet(). Ниже представлены некоторые варианты для перебора элементов:

// 1. все ключи-значения

for (Map.Entry<String, String> entry: hashmap.entrySet())

System.out.println(entry.getKey() + \" =\" + entry.getValue());

// 2. все ключи

for (String key: hashmap.keySet())

System.out.println(hashmap.get(key));

// 3. получить все пары ключ/значений

Iterator<Map.Entry<String, String>> itr = hashmap.entrySet().iterator();

while (itr.hasNext())

System.out.println(itr.next());

Предыдущий вопрос: 31. Какие существуют реализации Map?

Следующий вопрос: 33. Что такое LinkedHashMap?

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку:напишите мне