What is a Hash Table?
Урок 2 из 14 курса Хеш-таблицы — Серия «Структуры данных» №4 на Coddy.
Хеш-таблица — это структура данных, которая хранит пары «ключ-значение», подобно словарю, который ищет записи по их ключу. Магия заключается в скорости: хорошо построенная хеш-таблица находит, вставляет или удаляет запись в среднем за время O(1), независимо от того, сколько записей она содержит.
Секрет кроется в хеш-функции. Каждый ключ преобразуется в индекс корзины, поэтому мы точно знаем, где искать, не сканируя всю таблицу. Когда два разных ключа попадают в одну и ту же корзину (происходит коллизия), мы храним их вместе в виде списка в этой корзине. Эта стратегия называется методом цепочек (chaining).
Пять основных операций с хеш-таблицей:
- Put: Сохранить пару «ключ-значение» или обновить значение, если ключ уже существует.
- Get: Найти значение для заданного ключа.
- ContainsKey: Проверить, хранится ли ключ в таблице.
- Remove: Удалить пару «ключ-значение».
- Size: Вернуть количество пар, хранящихся в данный момент.
Давайте создадим класс HashMap!
Попробуйте сами
В этом уроке нет задания по программированию.