Как реализовать удаление дубликатов из массива объектов за линейное время O(n) без использования Set (например, через объект-хэш)?

Удаление дубликатов из массива объектов за O(n) через хэш-таблицу

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

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

Алгоритм проходит по массиву один раз. Для каждого объекта проверяется, существует ли ключ в хэш-таблице. Если нет — объект добавляется в результат, а ключ записывается в таблицу. Если ключ уже есть — объект пропускается. Это гарантирует, что каждый уникальный объект будет добавлен только один раз.

Пример кода

const arr = [
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' },
  { id: 1, name: 'Alice' },
  { id: 3, name: 'Charlie' }
];

function removeDuplicates(array, key) {
  const seen = {};
  return array.filter(item => {
    const keyValue = item[key];
    if (seen[keyValue]) {
      return false;
    }
    seen[keyValue] = true;
    return true;
  });
}

const unique = removeDuplicates(arr, 'id');
console.log(unique);
// [{ id: 1, name: 'Alice' }, { id: 2, name: 'Bob' }, { id: 3, name: 'Charlie' }]

Применение и вывод

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