Что такое коллизия в хеш-таблице и как она разрешается?

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

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

Метод цепочек (Chaining)

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

class HashTableChaining {
  constructor(size) {
    this.table = new Array(size).fill(null).map(() => []);
  }
  hash(key) { return key.length % this.table.length; }
  set(key, value) {
    const index = this.hash(key);
    this.table[index].push({ key, value });
  }
  get(key) {
    const index = this.hash(key);
    return this.table[index].find(item => item.key === key)?.value;
  }
}

Открытая адресация (Open Addressing)

Все элементы хранятся непосредственно в массиве. При коллизии ищется другой свободный слот с помощью пробирования: линейное (i+1, i+2...), квадратичное (i+1², i+2²...) или двойное хеширование (используется вторая хеш-функция). Удаление требует осторожности — обычно помечается как 'deleted', чтобы не нарушить цепочку поиска.

class HashTableOpenAddressing {
  constructor(size) {
    this.table = new Array(size);
  }
  hash(key) { return key.length % this.table.length; }
  set(key, value) {
    let index = this.hash(key);
    while (this.table[index] !== undefined) {
      index = (index + 1) % this.table.length; // линейное пробирование
    }
    this.table[index] = { key, value };
  }
  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== undefined) {
      if (this.table[index].key === key) return this.table[index].value;
      index = (index + 1) % this.table.length;
    }
    return undefined;
  }
}

Вывод

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