re:re:actable
Урок 053 минуты чтения

Что такое 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 существуют, но обычно скрыты.

Документация

Wikipedia: Hash table, VisuAlgo: Hash Table.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам