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

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

Хеширование ключа: ключ пропускается через хеш-функцию, которая возвращает числовой индекс.
Размещение значения: значение сохраняется в массиве по вычисленному индексу.
Обработка коллизий: если два ключа дают одинаковый индекс (коллизия), используется метод разрешения коллизий, например, цепочки (linked list) или открытая адресация.

Это позволяет получить доступ к элементам примерно за O(1) время.

Пример упрощённой реализации на JavaScript:

class SimpleMap {
  constructor() {
    this.buckets = [];
  }

  _hash(key) {
    let hash = 0;
    for (let char of key) {
      hash += char.charCodeAt(0);
    }
    return hash % 100;
  }

  set(key, value) {
    const index = this._hash(key);
    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }
    // Обновление или добавление
    const bucket = this.buckets[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][1] = value;
        return;
      }
    }
    bucket.push([key, value]);
  }

  get(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    if (!bucket) return undefined;
    for (let [k, v] of bucket) {
      if (k === key) return v;
    }
    return undefined;
  }
}

Таким образом, Map обеспечивает эффективное хранение и поиск данных за счёт хеширования ключей и разрешения коллизий.

Как под капотом работает Map? Как работают хеш-таблицы?