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

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

Основные компоненты:

• Ключ: Уникальный идентификатор элемента.
• Значение: Данные, связанные с ключом.
• Хэш-функция: Преобразует ключ в числовое значение (хэш), которое используется для определения индекса корзины.
• Корзины (Buckets): Массив, где хранятся пары ключ-значение.
• Обработка коллизий (Collision Handling): Механизм разрешения ситуаций, когда разные ключи дают один и тот же хэш (и, следовательно, указывают на одну корзину). Распространенные методы:
  • Метод цепочек (Chaining): В каждой корзине хранится список (например, связный список) элементов, хэши которых указывают на эту корзину.
  • Метод открытой адресации (Open Addressing): При коллизии ищется следующая свободная корзина с использованием алгоритмов, таких как линейное, квадратичное или двойное хэширование.

Принцип работы:

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

   // Пример вставки элемента в хэш-таблицу (метод цепочек)
   function insert(key, value) {
     const hash = hashFunction(key); // Вычисляем хэш
     const bucketIndex = hash % tableSize; // Определяем индекс корзины
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Создаем список, если он еще не существует
     }
     buckets[bucketIndex].push({ key, value }); // Добавляем пару в список
   }
   

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

   // Пример поиска элемента в хэш-таблице (метод цепочек)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Вычисляем хэш
     const bucketIndex = hash % tableSize; // Определяем индекс корзины
   
     if (buckets[bucketIndex]) {
       // Ищем элемент в списке корзины
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // Если требуется удаление
           return value; // Возвращаем значение
         }
       }
     }
     return undefined; // Элемент не найден
   }
   

Преимущества:

• Высокая скорость операций вставки, поиска и удаления в среднем случае (O(1)).
• Эффективное использование памяти по сравнению с прямым адресным массивом (если ключи распределены разреженно).

Недостатки:

• Производительность может снизиться в случае большого количества коллизий (в худшем случае O(n)).
• Не сохраняется порядок вставки элементов.
• Требуется хорошая хэш-функция для равномерного распределения ключей.

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