> Что такое хэш индекс и как он работает (JavaScript)

Хэш-индекс - это структура данных, которая использует хэш-функцию для отображения ключей в фиксированный диапазон индексов (обычно в массив). В контексте баз данных или in-memory хранилищ (например, в Node.js с использованием объектов или Map) он позволяет выполнять поиск, вставку и удаление за O(1) в среднем случае.

Как работает:

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

2. Хэш-код преобразуется в индекс массива (обычно через операцию взятия остатка от деления на размер массива).

3. По этому индексу в массиве хранится значение (или ссылка на запись). Если возникает коллизия (два ключа дают одинаковый индекс), используются методы разрешения коллизий, например, цепочки (связные списки) или открытая адресация.

Пример на JavaScript (Node.js):

JAVASCRIPT
class HashIndex {
  constructor(size = 100) {
    this.table = new Array(size);
    this.size = size;
  }

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

  set(key, value) {
    const index = this._hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    // Разрешение коллизий через цепочки
    for (let pair of this.table[index]) {
      if (pair[0] === key) {
        pair[1] = value;
        return;
      }
    }
    this.table[index].push([key, value]);
  }

  get(key) {
    const index = this._hash(key);
    const bucket = this.table[index];
    if (bucket) {
      for (let pair of bucket) {
        if (pair[0] === key) return pair[1];
      }
    }
    return undefined;
  }
}

В реальных проектах (например, в базах данных MongoDB или Redis) хэш-индексы оптимизируются для работы с большими объёмами данных, но принцип остаётся тем же: быстрый доступ к данным по ключу за счёт хэширования.