Введение

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

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

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

Реализация простой хэш-карты в JavaScript

let hashMap = {};
hashMap['key1'] = 'value1';
hashMap['key2'] = 'value2';
console.log(hashMap['key1']); // Outputs: value1

Обработка столкновений

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

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

Вот простая реализация хэш-карты с использованием отдельной цепочки в JavaScript:

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null).map(() => []);
  }

  put(key, value) {
    const index = this.hash(key);
    const chain = this.table[index];
    const existingPair = chain.find(([existingKey]) => existingKey === key);

    if (existingPair) {
      existingPair[1] = value;
    } else {
      chain.push([key, value]);
    }
  }

  get(key) {
    const index = this.hash(key);
    const chain = this.table[index];
    const pair = chain.find(([existingKey]) => existingKey === key);

    if (pair) {
      return pair[1];
    }

    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i 



Линейное зондирование: при линейном зондировании, когда происходит столкновение, хеш-карта проверяет следующий слот в массиве (и переходит к следующему, если он также заполнен, и т. д.), пока не найдет пустой слот, в котором можно хранить новую пару ключ-значение.

Вот простая реализация хэш-карты с использованием линейного зондирования в JavaScript:


class HashMap {
  constructor() {
    this.table = new Array(100).fill(null);
  }

  put(key, value) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      index = (index   1) % this.table.length;
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index   1) % this.table.length;
    }
    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i 



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