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

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

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

Основные операции:

1. Вставка: Вычисляется хэш ключа, и пара "ключ-значение" помещается в соответствующий бакет.
2. Удаление: Вычисляется хэш ключа, находится соответствующий бакет, и пара удаляется.
3. Поиск: Вычисляется хэш ключа, находится соответствующий бакет, и ищется пара с искомым ключом.

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

Существуют различные стратегии разрешения коллизий:

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

Пример концепции (упрощенно):

// Пример упрощенной хэш-функции
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // Преобразование в 32bit-целое
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Метод цепочек
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Проверка на существование ключа для обновления значения
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Ключ не найден
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Успешно удалено
      }
    }
    return false; // Ключ не найден
  }
}

// Использование
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

В JavaScript объекты ({}) и карты (Map) являются примерами реализации хэш-таблиц. Map зачастую предпочтительнее, так как поддерживает ключи любого типа и сохраняет порядок вставки.

Свойства хорошей хэш-функции:

• Быстрое вычисление.
• Равномерное распределение хэшей для разных ключей.
• Минимизация коллизий.