Что такое хеш-таблица?

Основная идея

Хеш-таблица — это структура данных, которая позволяет хранить пары «ключ-значение» и быстро находить значение по ключу. Вместо линейного поиска по всем элементам, как в массиве или списке, хеш-таблица вычисляет индекс, где должно храниться значение, с помощью хеш-функции. Это даёт среднюю сложность операций O(1), что делает её незаменимой для реализации словарей, кэшей и множеств.

Как это работает

Хеш-функция принимает ключ (например, строку или число) и возвращает целое число — индекс в массиве. Например, для ключа «apple» хеш-функция может вернуть 3, и значение будет помещено в ячейку массива с индексом 3. При поиске ключа «apple» снова вычисляется хеш, и мы сразу попадаем в нужную ячейку.

Однако разные ключи могут давать одинаковый хеш — это называется коллизией. Для разрешения коллизий используют два основных подхода:

• Метод цепочек: в каждой ячейке массива хранится связный список или другая структура, куда добавляются все элементы с одинаковым хешем.
• Открытая адресация: при коллизии ищется следующая свободная ячейка (линейное или квадратичное пробирование).

Пример на JavaScript

class HashTable {
  constructor(size = 10) {
    this.table = new Array(size);
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i)) % this.table.length;
    }
    return hash;
  }

  set(key, value) {
    const index = this.hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    this.table[index].push([key, value]);
  }

  get(key) {
    const index = this.hash(key);
    const bucket = this.table[index];
    if (bucket) {
      for (const [k, v] of bucket) {
        if (k === key) return v;
      }
    }
    return undefined;
  }
}

В этом примере используется метод цепочек: при коллизии элементы добавляются в массив внутри ячейки. Поиск проходит по цепочке, что в худшем случае даёт O(n), но при хорошей хеш-функции и достаточном размере таблицы цепочки короткие.

Где применяется

Хеш-таблицы лежат в основе многих языковых конструкций: объекты в JavaScript, словари в Python, HashMap в Java, ассоциативные массивы в PHP. Они используются для кэширования, индексации в базах данных, реализации множеств и многих других задач, где нужен быстрый доступ по ключу.

Вывод

Хеш-таблица — это мощный инструмент для задач, требующих быстрого поиска, вставки и удаления по ключу. Её стоит применять, когда важна производительность операций с данными и ключи можно эффективно хешировать. Понимание её устройства помогает правильно выбирать структуры данных и избегать проблем с производительностью при большом количестве коллизий.