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

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

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

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

Когда вы добавляете пару ключ-значение, хеш-функция преобразует ключ в целое число, которое затем приводится к индексу массива (обычно через взятие остатка от деления на размер массива). Например, для ключа 'name' хеш-функция может вернуть 123, и если массив имеет размер 10, индекс будет 3. Если два разных ключа дают одинаковый индекс, возникает коллизия.

Разрешение коллизий

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

Пример на 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);
    if (!this.table[index]) return undefined;
    for (const [k, v] of this.table[index]) {
      if (k === key) return v;
    }
    return undefined;
  }
}

Применение

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

Вывод

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