Hash table

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

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

Почему она так называется?

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

Что такое хеш-функция?

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

Хеш-функция должна обладать следующими свойствами:

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

Напишем свою хеш-функцию

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

function simpleHash(key, tableSize) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * 31 + key.charCodeAt(i)) % tableSize;
  }
  return hash;
}

Объяснение хеш-функции

• Инициализация хеша
  Начинаем с начального значения хеша, равного 0.
• Цикл по символам ключа
  Проходим по каждому символу строки и вычисляем его код с помощью charCodeAt.
• Обновление хеша
  Обновляем значение хеша, умножая текущее значение на 31 и добавляя код текущего символа, затем берем остаток от деления на размер таблицы, чтобы гарантировать, что хеш-код находится в пределах допустимых индексов массива.

Создание хеш-таблицы

Теперь создадим простую хеш-таблицу с методами для вставки, поиска и удаления элементов.

class HashTable {
  constructor(size) {
    this.table = new Array(size);
    this.size = size;
  }

  // Вставка ключ-значение
  set(key, value) {
    const index = simpleHash(key, this.size);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    // Обновление значения, если ключ уже существует
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index][i][1] = value;
        return;
      }
    }
    this.table[index].push([key, value]);
  }

  // Поиск значения по ключу
  get(key) {
    const index = simpleHash(key, this.size);
    if (!this.table[index]) return undefined;
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        return this.table[index][i][1];
      }
    }
    return undefined;
  }

  // Удаление ключ-значения
  delete(key) {
    const index = simpleHash(key, this.size);
    if (!this.table[index]) return;
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index].splice(i, 1);
        return;
      }
    }
  }
}

// Пример использования:
const hashTable = new HashTable(10);

// Вставка ключ-значение
hashTable.set("key1", "value1");
hashTable.set("key2", "value2");

// Поиск значения по ключу
console.log(hashTable.get("key1")); // Output: value1

// Удаление ключ-значения
hashTable.delete("key2");

// Проверка существования ключа
console.log(hashTable.get("key2")); // Output: undefined

Объяснение работы хеш-таблицы

• Инициализация
  Создаем массив заданного размера.
• Метод set
  Вычисляем индекс для ключа с помощью хеш-функции. Если индекс пуст, создаем пустой массив. Если ключ уже существует, обновляем его значение. В противном случае добавляем новую пару ключ-значение.
• Метод get
  Вычисляем индекс для ключа. Если индекс пуст, возвращаем undefined. Иначе ищем ключ в массиве и возвращаем значение, если находим его.
• Метод delete
  Вычисляем индекс для ключа. Если индекс пуст, ничего не делаем. Иначе ищем ключ в массиве и удаляем его, если находим.

Почему у нее такое время доступа к элементам?

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

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

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

Что такое коллизии?

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

Пример

function simpleHash(key, tableSize) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * 31 + key.charCodeAt(i)) % tableSize;
  }
  return hash;
}

const tableSize = 10;
console.log(simpleHash("key1", tableSize)); // Допустим, выводит 5
console.log(simpleHash("key2", tableSize)); // Допустим, тоже выводит 5 (коллизия)

Для решения коллизий используются методы цепочек или открытой адресации.

Реализация в JS

В JavaScript хеш-таблицы обычно не реализуются напрямую на уровне самого языка.
Вместо этого, для работы с хеш-таблицами используются встроенные объекты, такие как Object и Map, которые под капотом могут использовать хеширование для эффективного доступа к элементам.
Внутренняя реализация таких объектов в движках JavaScript, как V8 (используемый в Google Chrome и Node.js), может использовать массивы в комбинации с другими структурами данных для достижения быстрого доступа.