Что самый быстрый путь состоит в том, чтобы сравнить два набора в Java?

Если вы просто хотите узнать, равны ли наборы, метод равно в AbstractSet реализован примерно так, как показано ниже:

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        Collection c = (Collection) o;
        if (c.size() != size())
            return false;
        return containsAll(c);
    }

Обратите внимание, как он оптимизирует общие случаи, когда:

• два объекта одинаковы
• другой объект вообще не является набором, и
• размеры этих двух наборов различаются.

После этого containsAll (...) вернет false , как только найдет элемент в другом наборе, которого также нет в этом наборе. Но если все элементы присутствуют в обоих наборах, необходимо будет протестировать их все.

Следовательно, наихудший случай производительности возникает, когда два набора равны, но не являются одними и теми же объектами. Эта стоимость обычно составляет O (N) или O (NlogN) в зависимости от реализации this.containsAll (c) .

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

ОБНОВЛЕНИЕ

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

Идея состоит в том, что вам необходимо предварительно вычислить и кэшировать хэш для всего набора, чтобы вы могли получить текущее значение хэш-кода набора в O (1) . Затем вы можете сравнить хэш-код для двух наборов в качестве ускорения.

Как вы могли реализовать такой хэш-код? Хорошо, если бы хэш-код набора был:

• ноль для пустого набора и
• XOR всех хэш-кодов элементов для непустого набора,

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

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

Вы могли бы развить эту идею немного дальше ... по крайней мере, теоретически.

ПРЕДУПРЕЖДЕНИЕ - Это очень умозрительно. «Мысленный эксперимент», если хотите.

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

Что это нам дает?

Что ж, если мы предположим, что ничего скрытого не происходит, вероятность того, что любые два неравных элемента набора имеют одинаковые N-битные контрольные суммы, равна 2 ^-N . И вероятность того, что 2 неравных набора имеют одинаковые N-битные контрольные суммы, также равна 2 ^-N . Итак, моя идея состоит в том, что вы можете реализовать равно как:

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        Collection c = (Collection) o;
        if (c.size() != size())
            return false;
        return checksums.equals(c.checksums);
    }

В предположениях выше, это даст вам неправильный ответ только один раз за 2 ^-N раз. Если вы сделаете N достаточно большим (например, 512 бит), вероятность неправильного ответа станет незначительной (например,примерно 10 ^-150 ).

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

И другой недостаток заключается в том, что ненулевая вероятность ошибки может быть неприемлемой, независимо от того, насколько мала вероятность. (Но если это так ... как поступить со случаем, когда космический луч меняет критический бит? Или если он одновременно меняет один и тот же бит в двух экземплярах избыточной системы?)

firstSet.equals(secondSet)

Это действительно зависит от того, что вы хотите сделать в логике сравнения... т.е. что произойдет, если вы найдете элемент в одном наборе, но не в другом? Ваш метод имеет тип возврата void, поэтому я предполагаю, что вы сделаете необходимую работу в этом методе.

Более тонкий контроль, если он вам нужен:

if (!firstSet.containsAll(secondSet)) {
  // do something if needs be
}
if (!secondSet.containsAll(firstSet)) {
  // do something if needs be
}

Если вам нужно получить элементы, которые находятся в одном множестве, но не в другом.
EDIT: set.removeAll(otherSet) возвращает булево значение, а не набор. Чтобы использовать removeAll(), вам придется скопировать набор, а затем использовать его.

Set one = new HashSet<>(firstSet);
Set two = new HashSet<>(secondSet);
one.removeAll(secondSet);
two.removeAll(firstSet);

Если содержимое one и two пусто, то вы знаете, что два множества были равны. Если нет, значит, у вас есть элементы, которые сделали эти множества неравными.

Вы упомянули, что количество записей может быть большим. Если базовой реализацией является HashSet, то выборка каждой записи выполняется за O(1) время, так что вы не можете получить намного лучше, чем это. TreeSet - O(log n).