metodos - ¿Debería permitirse que un HashSet se agregue a sí mismo en Java?

metodos de hashmap java

Question

Según el contrato para un Conjunto en Java, "no está permitido que un conjunto se contenga a sí mismo como un elemento" ( source ). Sin embargo, esto es posible en el caso de un HashSet of Objects, como se demuestra aquí:

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

Esta afirmación pasa, pero esperaría que el comportamiento sea tener el conjunto resultante en 0 o lanzar una excepción. Me doy cuenta de que la implementación subyacente de un HashSet es un HashMap, pero parece que debería haber una verificación de igualdad antes de agregar un elemento para evitar violar ese contrato, ¿no?

Answer 1

Agregar la colección a sí mismo una vez hace que la prueba pase. Agregarlo dos veces provoca el StackOverflowError que estaba buscando.

Desde el punto de vista del desarrollador personal, no tiene ningún sentido imponer una verificación en el código subyacente para evitar esto. El hecho de que obtenga un StackOverflowError en su código si intenta hacer esto demasiadas veces, o calcula el hashCode , lo que causaría un desbordamiento instantáneo, debería ser suficiente para garantizar que ningún desarrollador cuerdo mantenga este tipo de código en su código base.

Answer 2

Debe leer el documento completo y citarlo por completo:

El comportamiento de un conjunto no se especifica si el valor de un objeto se cambia de una manera que afecta a las comparaciones iguales mientras el objeto es un elemento del conjunto. Un caso especial de esta prohibición es que no está permitido que un conjunto se contenga a sí mismo como elemento.

La restricción real está en la primera oración. El comportamiento no se especifica si un elemento de un conjunto está mutado.

Dado que agregar un conjunto a sí mismo lo muta, y agregarlo nuevamente lo muta nuevamente, el resultado no se especifica.

Tenga en cuenta que la restricción es que el comportamiento no está especificado , y que un caso especial de esa restricción es agregar el conjunto a sí mismo.

Entonces, el documento dice, en otras palabras, que agregar un conjunto a sí mismo da como resultado un comportamiento no especificado, que es lo que está viendo. Depende de la implementación concreta tratar (o no).

Answer 3

Estoy de acuerdo con usted en que, desde una perspectiva matemática, este comportamiento realmente no tiene sentido.

Aquí hay dos preguntas interesantes: primero, ¿en qué medida los diseñadores de la interfaz Set intentaron implementar un conjunto matemático? En segundo lugar, incluso si no lo fueran , ¿hasta qué punto eso los exime de las reglas de la teoría de conjuntos?

Para la primera pregunta, te señalaré la documentation del Conjunto:

Una colección que no contiene elementos duplicados. Más formalmente, los conjuntos no contienen ningún par de elementos e1 y e2, de modo que e1.equals (e2), y como máximo un elemento nulo. Como su nombre lo indica, esta interfaz modela la abstracción del conjunto matemático.

Vale la pena mencionar aquí que las formulaciones actuales de la teoría de conjuntos no permiten que los conjuntos sean miembros de sí mismos. (Ver el Axioma de regularidad ). Esto se debe en parte a la Paradoja de Russell , que expuso una contradicción en la ingenua teoría de conjuntos (que permitía que un conjunto fuera cualquier colección de objetos; no había prohibición contra conjuntos incluidos ellos mismos). La Paradoja del Barbero a menudo ilustra esto: supongamos que, en un pueblo en particular, un barbero afeita a todos los hombres, y solo a los hombres, que no se afeitan. Pregunta: ¿se afeita el barbero? Si lo hace, viola la segunda restricción; si no lo hace, viola la primera restricción. Esto es claramente lógicamente imposible, pero en realidad es perfectamente permisible bajo las reglas de la ingenua teoría de conjuntos (razón por la cual la nueva formulación "estándar" de la teoría de conjuntos prohíbe explícitamente que los conjuntos se contengan a sí mismos).

Hay más discusión en esta pregunta en Math.SE sobre por qué los conjuntos no pueden ser un elemento de sí mismos.

Dicho esto, esto plantea la segunda pregunta: incluso si los diseñadores no hubieran intentado explícitamente modelar un conjunto matemático, ¿estaría esto completamente "exento" de los problemas asociados con la ingenua teoría de conjuntos? Creo que no, creo que muchos de los problemas que plagaron la teoría de conjuntos ingenua plagarían cualquier tipo de colección que no estuviera suficientemente limitada de manera análoga a la teoría de conjuntos ingenua. De hecho, puedo estar leyendo demasiado sobre esto, pero la primera parte de la definición de un Set en la documentación suena sospechosamente como el concepto intuitivo de un conjunto en la ingenua teoría de conjuntos:

Una colección que no contiene elementos duplicados.

Es cierto que (y para su crédito), colocan al menos algunas restricciones sobre esto más adelante (incluyendo la afirmación de que realmente no debería tratar de contener un Set), pero podría preguntarse si realmente es "suficiente" para evitar los problemas. con ingenua teoría de conjuntos. Es por eso que, por ejemplo, tiene un problema de "tortugas hasta el fondo" cuando intenta calcular el código hash de un HashSet que se contiene a sí mismo. Este no es, como han sugerido algunos otros, simplemente un problema práctico: es una ilustración de los problemas teóricos fundamentales con este tipo de formulación.

Como breve digresión, reconozco que existen, por supuesto, algunas limitaciones sobre cuán estrechamente cualquier clase de colección puede realmente modelar un conjunto matemático. Por ejemplo, la documentación de Java advierte contra los peligros de incluir objetos mutables en un conjunto. Algunos otros lenguajes, como Python, al menos intentan prohibir por completo muchos tipos de objetos mutables :

Las clases establecidas se implementan utilizando diccionarios. En consecuencia, los requisitos para los elementos del conjunto son los mismos que para las claves del diccionario; a saber, que el elemento define tanto __eq__() como __hash__() . Como resultado, los conjuntos no pueden contener elementos mutables como listas o diccionarios. Sin embargo, pueden contener colecciones inmutables como tuplas o instancias de ImmutableSet. Para conveniencia en la implementación de conjuntos de conjuntos, los conjuntos internos se convierten automáticamente a una forma inmutable, por ejemplo, Set([Set([''dog''])]) se transforma en Set([ImmutableSet([''dog''])]) .

Otras dos diferencias importantes que otros han señalado son

• Los conjuntos de Java son mutables
• Los conjuntos de Java son finitos. Obviamente, esto será cierto para cualquier clase de colección: aparte de las preocupaciones sobre el infinito real , las computadoras solo tienen una cantidad finita de memoria. (Algunos lenguajes, como Haskell, tienen estructuras de datos infinitos perezosos; sin embargo, en mi opinión, una secuencia de elección legal parece un modelo de forma más natural que la teoría de conjuntos clásica, pero esa es solo mi opinión).

TL; DR No, realmente no debería permitirse (o, al menos, nunca debería hacerlo) porque los conjuntos no pueden ser miembros de sí mismos.

Answer 4

Otros ya han señalado por qué es cuestionable desde un punto de vista matemático, al referirse a la paradoja de Russell .

Sin embargo, esto no responde a su pregunta a nivel técnico .

Entonces diseccionemos esto:

Primero, una vez más la parte relevante del source

Nota: Se debe tener mucho cuidado si se utilizan objetos mutables como elementos establecidos. El comportamiento de un conjunto no se especifica si el valor de un objeto se cambia de una manera que afecta a las comparaciones iguales mientras el objeto es un elemento del conjunto. Un caso especial de esta prohibición es que no está permitido que un conjunto se contenga a sí mismo como elemento.

Curiosamente, la interfaz JavaDoc de la List hace una declaración similar, aunque algo más débil, y al mismo tiempo más técnica:

Si bien es permisible que las listas se contengan a sí mismas como elementos, se recomienda precaución extrema: los métodos equals y hashCode ya no están bien definidos en dicha lista.

Y finalmente, el quid está en el JavaDoc de la interfaz de la Collection , que es el ancestro común tanto de la interfaz Set como de la List :

Algunas operaciones de recopilación que realizan un recorrido recursivo de la recopilación pueden fallar con la excepción de instancias autorreferenciales en las que la recopilación se contiene directa o indirectamente . Esto incluye los métodos clone() , equals() , hashCode() y toString() . Las implementaciones pueden manejar opcionalmente el escenario autorreferencial, sin embargo, la mayoría de las implementaciones actuales no lo hacen.

^{(Énfasis por mí)}

La parte en negrita es una pista de por qué el enfoque que propuso en su pregunta no sería suficiente:

parece que debería haber una verificación de igualdad antes de agregar un elemento para evitar violar ese contrato, ¿no?

Esto no te ayudaría aquí. El punto clave es que siempre se encontrará con problemas cuando la colección se contendrá directa o indirectamente . Imagina este escenario:

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

Obviamente, ninguno de los conjuntos se contiene directamente . Pero cada uno de ellos contiene al otro, y por lo tanto, a sí mismo indirectamente . Esto no podría evitarse con una simple verificación de igualdad de referencia (usando == en el método add ).

Evitar tal "estado inconsistente" es básicamente imposible en la práctica. Por supuesto, es posible en teoría, utilizando cálculos de Reachability referencial. De hecho, el recolector de basura básicamente tiene que hacer exactamente eso.

Pero se vuelve imposible en la práctica cuando hay clases personalizadas involucradas. Imagina una clase como esta:

class Container {

    Set<Object> set;

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

Y jugando con esto y su set :

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

El método add del Set básicamente no tiene forma de detectar si el objeto que se agrega allí tiene alguna referencia (indirecta) al set en sí.

Larga historia corta:

No puede evitar que el programador arruine las cosas.