Работает ли HashSet.equals () в постоянное время?

Question

Просто интересно, работает ли HashSet.equals(anotherHashSet) в постоянное время (также с аргументом ConcurrentHashSet), что, я полагаю, происходит из соображений эффективности.Я не вижу ничего, что упоминает об этом, и часть структуры, которую я создаю, опирается на функциональность (не хотел бы, чтобы это заняло слишком много времени!)никоим образом HashSet.equals () не может выполняться за постоянное время, так как элементы могут изменяться, в то время как хэш-код для элементов на карте остается неизменнымСледовательно, лучший способ решить эту проблему - использовать хеш-код.Но пахнет ли он запахом кода?

Answer 1

Глядя на типичную реализацию , видно, что она делает containsAll. Каждая проверка на наличие будет O (1), и N из них должны быть сделаны, поэтому я считаю O (N).

Answer 2

Поскольку контракт equals() для Set требует, чтобы элементы двух объектов Set были идентичными, я не думаю, что это можно правильно реализовать в O ( 1) в общем случае (например, без дополнительных ограничений на типы контента).

Одно очевидное исключение состоит в том, что если входящий набор имеет другой размер, то операция equals() может легко завершиться в O (1) (при условии, что сам size() равен O (1)).

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

Answer 3

Насколько я вижу из кода - он работает за линейное время. Коллекция повторяется, и каждый элемент сравнивается:

equals(..) в AbstractSet вызывает containsAll(..) в AbstractCollection, который получает итератор и вызывает contains(..) для каждого элемента, а это, в свою очередь, вызывает map.containsKey(..), равное O(1). Так что O(n), если я не ошибаюсь.

Answer 4

Как это могло работать в постоянном времени?Единственная разумная реализация (которая также используется, которую вы можете увидеть, проверив документацию по API) - это перебирать один из наборов и для каждого элемента проверять, содержит ли другой его, который в основном является O (n+ м) операция.