Как устроена хэш-таблица (Map) в JavaScript и почему доступ к элементу по ключу быстрый?

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

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

Почему доступ быстрый

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

Пример реализации простой хэш-таблицы

class SimpleHashTable {
  constructor() {
    this.table = new Array(100);
  }

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

  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 (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          return bucket[i][1];
        }
      }
    }
    return undefined;
  }
}

Применение в JavaScript

Встроенный объект Map использует более сложные алгоритмы для обработки коллизий и динамического расширения. Он также сохраняет порядок вставки элементов и принимает любые типы ключей.

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