Если вы просто хотите узнать, равны ли наборы, метод equals для 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).
И вы получите производительность, близкую к худшему, если наборы велики и отличаются лишь небольшим процентом элементов.
UPDATE
Если вы готовы тратить время на реализацию пользовательского набора, есть подход, который может улучшить «почти такой же» случай.
Идея состоит в том, что вам нужно предварительно рассчитать и кэшировать хеш для всего набора, чтобы вы могли получить текущее значение хеш-кода набора в O(1). Затем вы можете сравнить хэш-код для двух наборов в качестве ускорения.
Как вы могли бы реализовать такой хэш-код? Хорошо, если установлен хэш-код:
- ноль для пустого набора и
- XOR всех хеш-кодов элементов для непустого набора,
тогда вы можете дешево обновлять кэшированный хэш-код набора каждый раз, когда добавляете или удаляете элемент. В обоих случаях вы просто XOR хеш-кода элемента с текущим установленным хеш-кодом.
Конечно, это предполагает, что хеш-коды элементов являются стабильными, в то время как элементы являются членами наборов. Также предполагается, что функция hashcode классов элементов дает хороший разброс. Это потому, что, когда два набора хеш-кодов совпадают, вам все равно придется вернуться к O(N) сравнению всех элементов.
Вы могли бы развить эту идею немного дальше ... по крайней мере, в теории.
Предположим, что в вашем классе элементов set есть метод для возврата контрольных сумм шифрования для элемента. Теперь реализуйте контрольные суммы набора, XORing контрольные суммы, возвращенные для элементов.
Что это нас покупает?
Хорошо, если мы предположим, что ничего не происходит, вероятность того, что любые два неравных набора элементов имеют одинаковые N-битные контрольные суммы, равна 2 -N . И вероятность того, что 2 неравных набора имеют одинаковые N-битные контрольные суммы, также составляет 2 -N . Так что моя идея заключается в том, что вы можете реализовать equals как:
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 ).
Недостатком является то, что вычисление крипто контрольных сумм для элементов очень дорого, особенно с увеличением количества битов. Таким образом, вам действительно нужен эффективный механизм для запоминания контрольных сумм. И это может быть проблематично.