Что такое hash table?
На этой странице
Hash table - структура данных для хранения ключ-значение с быстрым доступом по ключу. В JavaScript роль готовой hash table чаще всего выполняют Map, Set и иногда plain object.
Вопрос
Что такое hash table, как она обеспечивает O(1) в среднем и что такое коллизии?
Основная идея
Hash table превращает key в индекс через hash function:
key -> hash -> bucket -> valueТак можно быстро находить значение по ключу.
Игрушечный пример: таблица на 5 ячеек (buckets), хеш-функция - сумма кодов символов по модулю 5.
hash("cat") = (99 + 97 + 116) % 5 = 312 % 5 = 2
hash("dog") = (100 + 111 + 103) % 5 = 314 % 5 = 4
buckets:
0: -
1: -
2: cat -> 3
3: -
4: dog -> 7Чтобы найти "dog", не нужно перебирать все ключи: считаем хеш, получаем 4 и сразу идем в нужную ячейку. Поэтому поиск в среднем O(1), независимо от количества элементов.
Настоящие хеш-функции устроены сложнее, чтобы ключи распределялись равномерно, но идея та же.
В JavaScript
Для алгоритмов обычно не пишут hash table с нуля, а используют:
const map = new Map<string, number>()
const set = new Set<string>()Пример: частоты
function firstUniqueChar(s: string): string | null {
const count = new Map<string, number>()
for (const char of s) {
count.set(char, (count.get(char) ?? 0) + 1)
}
for (const char of s) {
if (count.get(char) === 1) return char
}
return null
}Time O(n), space O(k), где k - число разных символов.
Collisions
Collision - ситуация, когда разные keys попадают в один bucket.
Например, в нашей игрушечной таблице hash("act") = 312 % 5 = 2 - тот же bucket, что у "cat".
Hash table решает это через:
- chaining - в bucket хранится список пар, и при поиске его перебирают;
- open addressing - ищут следующую свободную ячейку;
- другие стратегии.
Отсюда и худший случай O(n): если все ключи попали в один bucket, поиск превращается в перебор списка. Хорошая хеш-функция и расширение таблицы при заполнении делают такое крайне маловероятным, поэтому говорят "O(1) в среднем".
На JS-собеседовании обычно достаточно понимать идею, а не реализацию движка.
Что отвечать на собеседовании?
Hash table хранит пары ключ-значение и использует hash function для быстрого доступа. Средняя сложность get/set/has обычно считается O(1), но в худшем случае может деградировать. В JavaScript для практических задач я использую Map и Set.
Что важно помнить: частые ошибки
- Гарантировать
O(1)как абсолютную истину. - Не учитывать память
O(n). - Использовать
includesвместоSet.has. - Путать hash table с sorted map.
- Забывать про equality object keys по ссылке.
Мини-шпаргалка
- Hash table = key -> value.
Map- hash map-like коллекция.Set- hash set-like коллекция.- Средний доступ -
O(1). - Частоты и индексы - классический кейс.
- Collisions существуют, но обычно скрыты.