Должен ли HashSet быть добавлен к себе в Java?

Ответ 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 основном не имеет способа определить, есть ли добавленный там объект (косвенная) ссылка на сам набор.

Короче:

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

Ответ 2

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

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

Ответ 3

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

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

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

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

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

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

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

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