Должен ли хеш-набор быть разрешен для добавления к себе в Java?

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

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

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

4 51
javascript subset scala-collections hashset contract

4 ответа:

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

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

Итак, давайте разберем этот:

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

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

интересно, что 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);

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

короче:

вы не можете не позволяйте программисту все испортить.

52

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

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

22

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

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

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

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

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

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

12

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

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

для первого вопроса, я укажу вам на документация из Набор:

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

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

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

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

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

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

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

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

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

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

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

8