¿Por qué java.util.Set no tiene get (int index)?

237

Estoy seguro de que hay una buena razón, pero ¿alguien podría explicar por qué java.util.Setfalta la interfaz get(int Index)o algún get()método similar ?

Parece que los conjuntos son geniales para poner cosas, pero no puedo encontrar una manera elegante de recuperar un solo elemento.

Si sé que quiero el primer elemento, puedo usarlo set.iterator().next(), pero de lo contrario parece que tengo que enviarlo a una matriz para recuperar un elemento en un índice específico.

¿Cuáles son las formas apropiadas de recuperar datos de un conjunto? (aparte de usar un iterador)

Estoy seguro de que el hecho de que esté excluido de la API significa que hay una buena razón para no hacerlo: ¿podría alguien aclararme?

EDITAR: Algunas respuestas extremadamente buenas aquí, y algunas que dicen "más contexto". El escenario específico era una prueba dbUnit, donde razonablemente podía afirmar que el conjunto devuelto de una consulta tenía solo 1 elemento, y estaba tratando de acceder a ese elemento.

Sin embargo, la pregunta es más válida sin el escenario, ya que permanece más enfocada:

¿Cuál es la diferencia entre set y list ?

Gracias a todos por las fantásticas respuestas a continuación.

Marty Pitt
fuente
1
¿Por qué obtendrías un elemento de un conjunto por índice? ¿Estás tratando de usar un conjunto como una matriz ordenada?
MSN
La instancia particular aquí es una prueba dbUnit contra un conjunto devuelto por una llamada de hibernación. En mi prueba, es razonable suponer (porque lo afirmo) que el objeto devuelto está en un orden específico, debido a mi IDataSet que solía configurarlo. Es un caso no típico, pero me lleva a mi curiosidad sobre la API.
Marty Pitt el
1
Agregar cosas en un orden específico no significa que se mantendrán así, a menos que esté usando una implementación de Set personalizada.
Michael Myers
1
"Si sé que quiero el primer elemento, puedo usar set.iterator (). Next ()" - Esta línea en realidad no tiene sentido. Realmente estás diciendo "Si sé que quiero el primer elemento, según la definición de implementación del primer elemento, entonces puedo ...". El conjunto en sí no está ordenado, por lo que el acceso indexado no tiene sentido. Ahora, si hubiera un ArrayListSet, eso tendría más sentido (solo eche a "Lista" y sea feliz). ¿Quizás podría dar más contexto para la pregunta?
jsight
¡El conjunto no está desordenado! Ciertas implementaciones son, pero algunas implementaciones están ordenadas explícitamente de una manera particular.
reinierpost

Respuestas:

176

Porque los conjuntos no tienen orden. Algunas implementaciones sí (particularmente aquellas que implementan la java.util.SortedSetinterfaz), pero esa no es una propiedad general de los conjuntos.

Si está tratando de usar conjuntos de esta manera, debería considerar usar una lista en su lugar.

Michael Myers
fuente
10
@matt b: No, creo que debería considerarlo. Pensar es bueno. ;)
Michael Myers
10
Considéralo, luego hazlo.
Joe Phillips el
21
"Considerar" es la redacción correcta. Hay dos problemas posibles (a) Está usando un conjunto cuando debería estar usando otra cosa, o (b) Está tratando de hacer cosas con Conjuntos que no admiten pero que podría hacer de otra manera. Es bueno considerar cuál de estos es el caso.
kenj0418
66
Puede ser la respuesta más simple es usar un conjunto ordenado. (Asumo que la singularidad jugó un papel al elegir el set). Pero tengo una pregunta, ya que SortedSet está ordenado, ¿por qué es que no hay un método get en la API?
uncaught_exceptions
55
@HDave: No, el hecho de que múltiples implementaciones de una estructura de datos compartan una propiedad no la convierte en una propiedad de la estructura de datos en sí. Dos de las tres implementaciones comúnmente utilizadas de List (ArrayList y Vector) son de acceso aleatorio, pero eso no hace que el acceso aleatorio sea una propiedad de las Listas.
Michael Myers
74

En realidad, esta es una pregunta recurrente cuando se escriben aplicaciones JavaEE que utilizan el mapeo relacional de objetos (por ejemplo, con Hibernate); y de todas las personas que respondieron aquí, Andreas Petersson es el único que entendió el problema real y ofreció la respuesta correcta: ¡Java no tiene una lista única! (o también puede llamarlo OrderedSet o IndexedSet).

Maxwing mencionó este caso de uso (en el que necesita datos ordenados Y únicos) y sugirió el SortedSet, pero esto no es lo que realmente necesitaba Marty Pitt.

Este "IndexedSet" NO es lo mismo que un SortedSet: en un SortedSet los elementos se ordenan usando un Comparador (o usando su orden "natural").

Pero, en cambio, está más cerca de un LinkedHashSet (que otros también sugirieron), o más aún de un (también inexistente) "ArrayListSet", porque garantiza que los elementos se devuelven en el mismo orden en que se insertaron.

¡Pero LinkedHashSet es una implementación, no una interfaz! ¡Lo que se necesita es una interfaz IndexedSet (o ListSet, OrderedSet o UniqueList)! Esto permitirá al programador especificar que necesita una colección de elementos que tengan un orden específico y sin duplicados, y luego crear una instancia con cualquier implementación (por ejemplo, una implementación proporcionada por Hibernate).

Como JDK es de código abierto, tal vez esta interfaz finalmente se incluirá en Java 7 ...

Sorin Postelnicu
fuente
3
Gran respuesta en lo que va, pero ¿qué hacemos mientras tanto?
HDave
claro que lo es. Utilicé list como manytomany y onetomany ORM en hibernate antes. Me encontré con un problema (o defecto) cuando una consulta de unión izquierda que involucraba más de 3 entidades relacionadas, se lanzó una excepción. mira aquí para más detalles ( jroller.com/eyallupu/entry/… ). Para evitar este problema, es necesario usar la colección de mapeo set as ORM. pero honestamente decir, establecer no es conveniente para acceder en la programación, y también cuando necesita una colección de pedidos. lo que realmente necesitamos es "indexedset" como lo que dijo Sorin Postelnicu, SORT y UNIQUE
horaceman
2
Apache Commons Collections tiene ListOrderedSetlo que el OP necesitaba hace 7 años (y yo necesitaba hoy).
Paul
@Paul: Eso es realmente algo que se ve muy bien. Desafortunadamente, todavía tiene 3 inconvenientes: 1) Es una clase, no una interfaz. 2) No está en el JDK. 3) No es lo que están devolviendo las consultas de Hibernate.
Sorin Postelnicu
Sí, pero aparte de esos 3 inconvenientes principales, ¡es perfecto! :) En retrospectiva, debería haber publicado mi comentario a la pregunta y no su respuesta: desconecté What is needed is an IndexedSet (or ListSet, or OrderedSet, or UniqueList)...e ignoré ...interface. ¡Lo siento por eso!
Paul
29

Solo agrego un punto que no fue mencionado en la respuesta de mmyers .

Si sé que quiero el primer elemento, puedo usar set.iterator (). Next (), pero de lo contrario, parece que tengo que enviar a una matriz para recuperar un elemento en un índice específico.

¿Cuáles son las formas apropiadas de recuperar datos de un conjunto? (aparte de usar un iterador)

También debe familiarizarse con la SortedSetinterfaz (cuya implementación más común es TreeSet).

Un conjunto ordenado es un conjunto (es decir, los elementos son únicos) que se mantiene ordenado por el orden natural de los elementos o por el uso de algunos Comparator. Puede acceder fácilmente al primer y último elemento utilizando first()y last()métodos. A SortedSetes útil de vez en cuando, cuando necesita mantener su colección libre de duplicados y ordenada de cierta manera.

Editar : si necesita un conjunto cuyos elementos se mantienen en orden de inserción (al igual que una lista), eche un vistazo LinkedHashSet.

Jonik
fuente
Me gusta LinkedHashSet yo mismo. Pero sí, es bueno mencionarlo. +1
Michael Myers
Gracias, modifiqué un poco la respuesta. (Parece que tenía algunos aspectos de TreeSet confundirse con los de LinkedHashSet.)
Jonik
25

Este tipo de pregunta lleva a la pregunta de cuándo debe usar un conjunto y cuándo debe usar una lista. Por lo general, el consejo es:

  1. Si necesita datos ordenados, use una Lista
  2. Si necesita datos únicos, use un conjunto
  3. Si necesita ambos, use: SortedSet (para datos ordenados por comparador) o OrderedSet / UniqueList (para datos ordenados por inserción). Lamentablemente, la API de Java aún no tiene OrderedSet / UniqueList.

Un cuarto caso que aparece a menudo es que no necesita ninguno. En este caso, verá que algunos programadores van con listas y otros con conjuntos. Personalmente, me resulta muy dañino verlo como una lista sin ordenar, porque es realmente una bestia completamente diferente. A menos que necesite cosas como establecer unicidad o establecer igualdad, siempre favorezca las listas.

Waxwing
fuente
2
si no es específico, acepte Colección <T> o incluso Iterable <T> e inicialícelo como una Lista.
Andreas Petersson el
Esto sería una bolsa o un conjunto múltiple. Pero Java no los admite; dicen que solo debes usar Collection <T> directamente.
Caracol mecánico
4. necesita datos no únicos y no le importa el orden. NO PUEDE usar un conjunto. Una lista, bolsa o conjunto múltiple funcionará.
Andrew Gallasch
17

No estoy seguro de si alguien lo ha explicado exactamente de esta manera, pero debe comprender lo siguiente:

No hay un "primer" elemento en un conjunto.

Porque, como han dicho otros, los conjuntos no tienen orden. Un conjunto es un concepto matemático que específicamente no incluye la ordenación.

Por supuesto, su computadora realmente no puede mantener una lista de cosas que no están ordenadas en la memoria. Tiene que tener algunos pedidos. Internamente es una matriz o una lista vinculada o algo así. Pero realmente no sabes lo que es, y realmente no tiene un primer elemento; el elemento que sale "primero" sale de esa manera por casualidad, y podría no ser el primero la próxima vez. Incluso si tomaste medidas para "garantizar" un primer elemento en particular, todavía sale por casualidad, porque acabas de acertar para una implementación particular de un Set; una implementación diferente podría no funcionar de esa manera con lo que hizo. Y, de hecho, es posible que no conozca la implementación que está utilizando tan bien como cree.

La gente se encuentra con este TODO. EL. HORA. con sistemas RDBMS y no entiendo. Una consulta RDBMS devuelve un conjunto de registros. Este es el mismo tipo de conjunto de matemáticas: una colección desordenada de elementos, solo en este caso los elementos son registros. El resultado de una consulta RDBMS no tiene ningún orden garantizado a menos que use la cláusula ORDER BY, pero todo el tiempo la gente asume que sí y luego se tropieza algún día cuando la forma de sus datos o código cambia ligeramente y activa el optimizador de consultas para que funcione de una manera diferente y de repente los resultados no salen en el orden que esperan. Estas son típicamente las personas que no prestaron atención en la clase de base de datos (o al leer la documentación o los tutoriales) cuando se les explicó, por adelantado, que los resultados de la consulta no tienen un pedido garantizado.

skiphoppy
fuente
Je, y por supuesto, el orden generalmente cambia justo después de que el código entra en producción, cuando es demasiado lento, por lo que agregan un índice para acelerar la consulta. Ahora el código se ejecuta rápido, pero da las respuestas incorrectas. Y nadie se da cuenta por tres o cuatro días ... si tienes suerte. Si no tienes suerte, nadie se da cuenta de un mes ...
RGT
No creo que se haya perdido eso (quizás fue descuidado con la notación) No quiere el primer elemento del conjunto, quiere un elemento arbitrario del conjunto. Puedes darle un elemento arbitrario ya que Setes Iterable.
Elazar Leibovich
Estás hablando de obtener (índice) por índice. ¿Qué pasa con un get (Object) por igualdad?
Kumar Manish
10

faltan algunas estructuras de datos en las colecciones estándar de Java.

Bolsa (como conjunto pero puede contener elementos varias veces)

UniqueList (lista ordenada, puede contener cada elemento solo una vez)

parece que necesitarías una lista única en este caso

si necesita estructuras de datos flexibles, puede estar interesado en Google Collections

Andreas Petersson
fuente
1
¿Guva proporciona una "UniqueList"?
Mike Rylander
no, pero puede tener un java.util.LinkedHashSet que tiene propiedades similares.
Andreas Petersson
7

Es cierto, los elementos en Set no están ordenados, por definición de Set Collection. Por lo tanto, no se puede acceder por un índice.

Pero, ¿por qué no tenemos un método get (objeto), no proporcionando el índice como parámetro, sino un objeto que sea igual al que estamos buscando? De esta manera, podemos acceder a los datos del elemento dentro del Conjunto, simplemente conociendo sus atributos utilizados por el método de igualdad.

paredes
fuente
7

Si va a hacer muchos accesos aleatorios por índice en un conjunto, puede obtener una vista de matriz de sus elementos:

Object[] arrayView = mySet.toArray();
//do whatever you need with arrayView[i]

Sin embargo, hay dos inconvenientes principales:

  1. No es eficiente en la memoria, ya que se necesita crear una matriz para todo el conjunto.
  2. Si se modifica el conjunto, la vista se vuelve obsoleta.
fortran
fuente
5

Esto se debe a que Set solo garantiza la unicidad, pero no dice nada sobre el acceso óptimo o los patrones de uso. Es decir, un Conjunto puede ser una Lista o un Mapa, cada uno de los cuales tiene características de recuperación muy diferentes.

jsight
fuente
5

La única razón por la que puedo pensar para usar un índice numérico en un conjunto sería para la iteración. Para eso, usa

for(A a : set) { 
   visit(a); 
}
Hugo
fuente
No es cierto, ¿qué pasa con el acceso a un elemento aleatorio?
Jeremy Salwen
Jaja. buen punto :) pero eso sería muy propenso al mal uso, estoy seguro.
Hugo
3

Me encontré con situaciones en las que realmente quería un Sorted Conjunto con acceso a través de índice (Estoy de acuerdo con otros críticos que se accede a un conjunto sin clasificar con un índice que no tiene sentido). Un ejemplo sería un árbol donde quisiera que se clasificaran los niños y no se permitieran duplicarlos.

Necesitaba el acceso a través del índice para mostrarlos y los atributos establecidos fueron útiles para eliminar eficientemente los duplicados.

Al no encontrar una colección adecuada en java.util o en las colecciones de google, me resultó sencillo implementarla yo mismo. La idea básica es envolver un SortedSet y crear una Lista cuando se requiere acceso a través del índice (y olvidar la lista cuando se cambia el SortedSet). Por supuesto, esto solo funciona de manera eficiente cuando se cambia el SortedSet envuelto y el acceso a la lista se separa durante la vida útil de la Colección. De lo contrario, se comporta como una lista que se ordena a menudo, es decir, demasiado lenta.

Con un gran número de niños, este rendimiento mejoró mucho en una lista que mantuve ordenada a través de Collections.sort.

Buchweizen
fuente
2

Tenga en cuenta que solo se puede acceder a 2 estructuras de datos básicas a través del índice.

  • Se puede acceder a la estructura de datos de la matriz a través de un índice con O(1)complejidad de tiempo para lograr la get(int index)operación.
  • También se puede acceder a la estructura de datos de LinkedList a través del índice, pero con O(n)complejidad de tiempo para lograr la get(int index)operación.

En Java, ArrayListse implementa utilizando la estructura de datos Array .

Si bien la estructura de datos de Set generalmente se puede implementar a través de la estructura de datos HashTable / HashMap o BalancedTree , para detectar rápidamente si un elemento existe y agregar un elemento no existente, generalmente un Set bien implementado puede lograr una operación de O(1)complejidad de tiempo contains. En Java, HashSetes la implementación más utilizada de Set , se implementa llamando a la HashMapAPI y HashMapse implementa mediante un encadenamiento separado con listas vinculadas (una combinación de Array y LinkedList ).

Dado que Set se puede implementar a través de una estructura de datos diferente, no hay ningún get(int index)método para ello.

coderz
fuente
Los árboles de dedos (consulte la Data.Sequence.lookupfunción de Haskell ) también permiten acceder a través del índice ( O(1)cerca de los extremos O(log n)cerca del centro, con mayor precisión O(min(log(k), log(n-k)))), también lo hacen los árboles binarios (consulte la Data.Set.lookupIndexfunción de Haskell ). Por lo tanto, su afirmación inicial de que "Tenga en cuenta que solo se puede acceder a la estructura de datos básica 2 a través del índice" no es correcta.
punto
1

La razón por la cual la interfaz Set no tiene una llamada get index-type o incluso algo aún más básico, como first () o last (), es porque es una operación ambigua y, por lo tanto, una operación potencialmente peligrosa. Si un método devuelve un Set y usted llama, digamos primero el método (), ¿cuál es el resultado esperado, dado que un Set genérico no garantiza el pedido? El objeto resultante bien podría variar entre cada llamada del método, o podría no hacerlo y adormecerlo con una falsa sensación de seguridad, hasta que la biblioteca que está utilizando los cambios cambie la implementación debajo y ahora descubra que todo su código se rompe por ninguna razón en particular.

Las sugerencias sobre soluciones alternativas que se enumeran aquí son buenas. Si necesita acceso indexado, use una lista. Tenga cuidado al usar iteradores o toArray con un conjunto genérico, porque a) no hay garantía en el pedido yb) no hay garantía de que el pedido no cambie con invocaciones posteriores o con diferentes implementaciones subyacentes. Si necesita algo intermedio, un SortedSet o LinkedHashSet es lo que desea.

// Sin embargo, me gustaría que la interfaz Set tuviera un elemento get-random-element.

Dan
fuente
1

java.util.Setes una colección de artículos sin ordenar. No tiene ningún sentido si el Set tiene un get (int index), porque Set no tiene un índice y también solo puedes adivinar el valor.

Si realmente quiere esto, codifique un método para obtener un elemento aleatorio de Set.

Resultados de la búsqueda Resultados web Pi
fuente
0

Tu puedes hacer new ArrayList<T>(set).get(index)

Janus Troelsen
fuente
Esto devuelve una Lista de conjuntos y get (index) devuelve un Conjunto. Por el contrario, solía: new ArrayList<T>(t).get(0) creo que existe una oposición válida a la idea de obtener un elemento particular de un Conjunto por un índice. Pero sería bueno si Set tuviera una función miembro only () que, para Conjuntos de tamaño 1, proporcionara acceso fácil al único elemento en el Set. Esto salvaría lo mencionado new ArrayListofor (Foo foo : foos) { return foo; }
Doug Moscrop
0

Si no le importa ordenar el conjunto, puede interesarle echar un vistazo al proyecto de mapa de árbol indexado .

El TreeSet / TreeMap mejorado proporciona acceso a los elementos por índice u obteniendo el índice de un elemento. Y la implementación se basa en actualizar los pesos de los nodos en el árbol RB. Por lo tanto, no hay iteración o respaldo por una lista aquí.

Vitaly Sazanovich
fuente
0

Set es una interfaz y algunas de sus clases de implementación son HashSet, TreeSet y LinkedHashSet. Utiliza HashMap debajo del capó para almacenar valores. Debido a que HashMap no conserva el orden, no es posible obtener valor por índice.

Ahora debe estar pensando cómo Set está usando HashMap, ya que HashMap almacena un par clave, valor, pero el Set no. pregunta válida cuando agrega un elemento en Set, internamente, mantiene un HashMap donde la clave es el elemento que desea ingresar en Set y el valor es la constante ficticia. A continuación se muestra una implementación interna de la función de agregar. Por lo tanto, todas las claves en el HashMap tendrán el mismo valor constante.

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
magnónimos
fuente
Todas Setlas implementaciones de s se utilizan HashMapbajo el capó para almacenar valores, ¿ puede justificar esa afirmación TreeSet?
barba gris
1
the keys in the HashMap will have the same constant value las teclas en elHashMap mapa se asignarán a una misma e inmutableObject
barba gris
-3

Para obtener un elemento en un conjunto, utilizo el siguiente:

public T getElement(Set<T> set, T element) {
T result = null;
if (set instanceof TreeSet<?>) {
    T floor = ((TreeSet<T>) set).floor(element);
    if (floor != null && floor.equals(element))
    result = floor;
} else {
    boolean found = false;
    for (Iterator<T> it = set.iterator(); !found && it.hasNext();) {
    if (true) {
        T current = it.next();
        if (current.equals(element)) {
        result = current;
        found = true;
        }
    }
    }
}
return result;
}
lala
fuente
la función no es lo que la pregunta solicitó. Necesitamos el índice, no el valor. ¿Cuál es su función de todos modos? parece que solo devuelve el elemento si era igual a un elemento dentro. ¿Qué hace esto que contiene () no?
Janus Troelsen
¿Dónde está lo Tdefinido? ¿Por qué if (true)?
Quantum