Следует ли разрешить добавление HashSet к себе в Java?

Question

В соответствии с контрактом для набора в Java "недопустимо, чтобы набор содержал себя как элемент" ( источник). Однако это возможно в случае HashSet объектов, как показано здесь:

Set<Object> mySet = new HashSet<>();
mySet.add(mySet);
assertThat(mySet.size(), equalTo(1));

Это утверждение проходит, но я ожидаю, что поведение будет иметь либо результирующий набор равным 0, либо выдавать исключение. Я понимаю, что базовая реализация HashSet - это HashMap, но кажется, что должна быть проверка на равенство перед добавлением элемента, чтобы избежать нарушения этого контракта, не так ли?

Answer 1

Другие уже указывали, почему это сомнительно с математической точки зрения, ссылаясь на парадокс Рассела.

Это не отвечает на ваш вопрос на техническом уровне, хотя.

Итак, давайте рассмотрим это:

Во-первых, еще раз соответствующая часть из JavaDoc Set интерфейс:

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

Интересно, что JavaDoc List Интерфейс делает похожее, хотя и несколько более слабое, и в то же время более техническое утверждение:

Хотя списки могут содержать себя в качестве элементов, рекомендуется соблюдать крайнюю осторожность: equals а также hashCode методы больше не определены в таком списке.

И, наконец, суть в JavaDoc Collection интерфейс, который является общим предком обоих Set и List интерфейс:

Некоторые операции по сбору, которые выполняют рекурсивный обход коллекции, могут завершаться ошибкой, за исключением случаев, когда ссылки ссылаются на себя непосредственно или косвенно. Это включает в себя clone(), equals(), hashCode() а также toString() методы. Реализации могут опционально обрабатывать сценарий со ссылками на себя, однако большинство современных реализаций этого не делают.

^{(Акцент мной)}

Жирная часть подсказка, почему подход, который вы предложили в вашем вопросе, не будет достаточным:

похоже, перед добавлением элемента должна быть проверка на равенство, чтобы не нарушать этот контракт, не так ли?

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

Set<Object> setA = new HashSet<Object>();
Set<Object> setB = new HashSet<Object>();
setA.add(setB);
setB.add(setA);

Очевидно, что ни один из наборов не содержит себя непосредственно. Но каждый из них содержит другой - и, следовательно, сам косвенно. Этого нельзя избежать простой проверкой ссылочного равенства (используя == в add метод).

---

Избежать такого "противоречивого состояния" практически невозможно на практике. Конечно, это возможно в теории, используя вычисления ссылочной достижимости. На самом деле, сборщик мусора должен делать именно это!

Но это становится невозможным на практике, когда участвуют пользовательские классы. Представьте себе такой класс:

class Container {

    Set<Object> set;

    @Override 
    int hashCode() {
        return set.hashCode(); 
    }
}

И возиться с этим и его set:

Set<Object> set = new HashSet<Object>();
Container container = new Container();
container.set = set;
set.add(container);

add метод Set в основном нет способа определить, имеет ли добавленный там объект некоторую (косвенную) ссылку на сам набор.

Короче:

Вы не можете помешать программисту все испортить.

Answer 2

Добавление коллекции в себя один раз приводит к прохождению теста. Добавление его дважды вызывает StackruError который вы искали.

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

Answer 3

Вы должны прочитать полный документ и процитировать его полностью:

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

Фактическое ограничение в первом предложении. Поведение не определено, если элемент набора видоизменен.

Поскольку добавление набора к самому себе приводит к его мутированию, а добавление его снова приводит к его мутированию, то результат не определен.

Обратите внимание, что ограничение состоит в том, что поведение не определено, и что особый случай этого ограничения добавляет набор к самому себе.

Таким образом, документ говорит, другими словами, что добавление набора к самому себе приводит к неопределенному поведению, которое вы видите. Это зависит от конкретной реализации, чтобы иметь дело (или нет).

Answer 4

Я согласен с вами, что с математической точки зрения такое поведение на самом деле не имеет смысла.

Здесь есть два интересных вопроса: во-первых, в какой степени дизайнеры Set Интерфейс пытается реализовать математический набор? Во-вторых, даже если это не так, в какой степени это освобождает их от правил теории множеств?

По первому вопросу я укажу вам документацию по набору:

Коллекция, которая не содержит повторяющихся элементов. Более формально, множества не содержат пары элементов e1 и e2, таких что e1.equals(e2), и не более одного нулевого элемента. Как следует из его названия, этот интерфейс моделирует абстракцию математического набора.

Здесь стоит упомянуть, что современные формулировки теории множеств не позволяют множествам быть членами самих себя. (См. Аксиома регулярности). Отчасти это связано с Парадоксом Рассела, который выявил противоречие в наивной теории множеств (которая позволяла множеству быть любым набором объектов - не было никакого запрета на множества, включая их самих). Это часто иллюстрируется парадоксом Парикмахера: предположим, что в конкретном городе парикмахер бреет всех мужчин - и только мужчин - которые не бреются сами. Вопрос: парикмахер бреется сам? Если он это делает, это нарушает второе ограничение; если он не делает, это нарушает первое ограничение. Это явно логически невозможно, но на самом деле это совершенно допустимо в соответствии с правилами наивной теории множеств (именно поэтому более новая "стандартная" формулировка теории множеств явно запрещает множествам содержать себя).

В этом вопросе на Math.SE обсуждается, почему наборы не могут быть элементом самих себя.

С учетом сказанного это поднимает второй вопрос: даже если бы дизайнеры не пытались явно моделировать математический набор, это было бы полностью "освобождено" от проблем, связанных с наивной теорией множеств? Я думаю, что нет - я думаю, что многие из проблем, которые преследовали наивную теорию множеств, преследовали бы любой вид коллекции, которая была недостаточно ограничена способами, аналогичными наивной теории множеств. На самом деле, я могу слишком много читать об этом, но первая часть определения Set в документации подозрительно звучит как интуитивное понятие множества в наивной теории множеств:

Коллекция, которая не содержит повторяющихся элементов.

По общему признанию (и к их чести), они действительно накладывают по крайней мере некоторые ограничения на это позже (в том числе заявляют, что вам действительно не следует пытаться содержать Набор в себе), но вы можете задаться вопросом, действительно ли этого "достаточно", чтобы избежать проблем с наивной теорией множеств. Вот почему, например, при попытке вычислить хеш-код HashSet, который содержит сам себя, у вас возникает проблема "все черепахи вниз". Это не, как некоторые другие предполагают, просто практическая проблема - это иллюстрация фундаментальных теоретических проблем с этим типом формулировки.

Как краткое отступление, я признаю, что существуют, конечно, некоторые ограничения на то, насколько близко любой класс коллекции может реально моделировать математический набор. Например, документация Java предупреждает об опасности включения изменяемых объектов в набор. Некоторые другие языки, такие как Python, по крайней мере пытаются полностью запретить многие виды изменяемых объектов:

Заданные классы реализованы с использованием словарей. Соответственно, требования к элементам набора такие же, как для ключей словаря; а именно, что элемент определяет оба __eq__() а также __hash__(), В результате наборы не могут содержать изменяемые элементы, такие как списки или словари. Однако они могут содержать неизменяемые коллекции, такие как кортежи или экземпляры ImmutableSet. Для удобства реализации наборов наборов внутренние наборы автоматически преобразуются в неизменяемую форму, например: Set([Set(['dog'])]) превращается в Set([ImmutableSet(['dog'])]),

Два других существенных различия, на которые указывали другие:

• Наборы Java изменчивы
• Наборы Java конечны. Очевидно, что это будет справедливо для любого класса коллекции: кроме проблем с фактической бесконечностью, компьютеры имеют только ограниченный объем памяти. (Некоторые языки, такие как Haskell, имеют ленивые бесконечные структуры данных; однако, на мой взгляд, правомерная последовательность выбора кажется более естественным способом моделирования, чем классическая теория множеств, но это только мое мнение).

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