Дедупликация с использованием набора Java

Question

У меня есть коллекция объектов, давайте назовем их A, B, C, D, ... и некоторые из них равны другим. Если A и C равны, то я хочу заменить каждую ссылку на C ссылкой на A. Это означает, что (a) объект C можно собирать мусором, освобождая память, и (b) я могу позже использовать «==» сравнивать объекты вместо дорогостоящей операции equals(). (Эти объекты большие, а операция equals() медленная.)

Мой инстинкт был использовать java.util.Set. Когда я сталкиваюсь с C, я легко могу видеть, есть ли запись в Set, равная C. Но если она есть, то, похоже, нет простого способа узнать, что это за запись, и заменить мою ссылку на существующую запись. Я ошибаюсь? Перебор всех записей, чтобы найти ту, которая соответствует, очевидно, не является началом.

В настоящее время вместо Set я использую Map, в котором значение всегда совпадает с ключом. Вызов map.get(C) затем находит А. Это работает, но кажется невероятно запутанным. Есть ли более элегантный способ сделать это?

Answer 1

Эта проблема не просто дедупликация: это форма канонизации.

Стандартный подход заключается в использовании Map вместо Set. Вот эскиз, как это сделать:

public <T> List<T> canonicalizeList(List<T> input) {
    HashMap<T, T> map = new HashMap<>();
    List<T> output = new ArrayList<>();
    for (T element: input) {
        T canonical = map.get(element);
        if (canonical == null) {
            element = canonical;
            map.put(canonical, canonical);
        }
        output.add(canonical);
    }
    return output;
}

Обратите внимание, что это O(N). Если вы можете с уверенностью предположить, что процент дубликатов в input, вероятно, будет небольшим, тогда вы можете установить емкость map и output равной input.

---

Теперь вы, кажется, говорите, что делаете это уже так (последний абзац), и вы спрашиваете, есть ли лучший способ. Насколько я знаю, нет ни одного. (API HashSet позволяет вам проверять, содержит ли набор значение, равное element, но не позволяет вам выяснить, что это за O(1).)

Для чего это стоит, под капотом класс HashSet<T> реализован как HashMap<T, T>. Таким образом, вы бы не экономили время и пространство, используя HashSet напрямую ...