Por que java.util.Set não tem get (int index)?

237

Tenho certeza de que há uma boa razão, mas alguém poderia explicar por que java.util.Setfalta a interface get(int Index)ou algum get()método semelhante ?

Parece que os conjuntos são ótimos para colocar as coisas, mas não consigo encontrar uma maneira elegante de recuperar um único item.

Se eu sei que quero o primeiro item, posso usá-lo set.iterator().next(), mas, caso contrário, parece que tenho que converter em uma matriz para recuperar um item em um índice específico?

Quais são as maneiras apropriadas de recuperar dados de um conjunto? (além de usar um iterador)

Tenho certeza de que o fato de ser excluído da API significa que há um bom motivo para não fazer isso - alguém poderia me esclarecer?

Edição: Algumas respostas extremamente ótimas aqui, e alguns dizendo "mais contexto". O cenário específico era um teste dbUnit, no qual eu podia afirmar razoavelmente que o conjunto retornado de uma consulta tinha apenas 1 item e estava tentando acessar esse item.

No entanto, a questão é mais válida sem o cenário, pois permanece mais focada:

Qual é a diferença entre set e list .

Obrigado a todos pelas respostas fantásticas abaixo.

Marty Pitt
fonte
1
Por que você obteria um elemento de um conjunto por índice? Você está tentando usar um conjunto como uma matriz classificada?
MSN
A instância específica aqui é um teste do dbUnit em relação a um conjunto retornado de uma chamada de hibernação. No meu teste, é razoável supor (porque afirmo) que o objeto retornado está em uma ordem específica, por causa do meu IDataSet que usei para configurá-lo. É um caso não típico, mas me levou a curiosidade sobre a API.
28711 Marty Pitt
1
Adicionar itens em uma ordem específica não significa que eles permanecerão assim, a menos que você esteja usando uma implementação Set personalizada.
Michael Myers
1
"Se eu sei que quero o primeiro item, posso usar set.iterator (). Next ()" - Esta linha não faz sentido. Você está realmente dizendo "Se eu sei que quero o primeiro item, pela definição de implementação do primeiro item, posso ...". O conjunto em si é desordenado, portanto, o acesso indexado não faz sentido. Agora, se houvesse um ArrayListSet, isso faria mais sentido (basta converter para "List" e ser feliz). Talvez você possa dar mais contexto para a pergunta?
jsight
Conjunto não é desordenado! Certas implementações são, mas algumas são explicitamente ordenadas de uma maneira específica.
Reinierpost

Respostas:

176

Porque os conjuntos não têm pedidos. Algumas implementações (principalmente as que implementam a java.util.SortedSetinterface), mas isso não é uma propriedade geral dos conjuntos.

Se você estiver tentando usar conjuntos dessa maneira, considere usar uma lista.

Michael Myers
fonte
10
@matt b: Não, acho que ele deveria considerar. Pensar é bom. ;)
Michael Myers
10
Considere, então faça.
21410 Joe Phillips
21
"Considerar" é o fraseado correto. Existem dois problemas possíveis: (a) ele está usando um conjunto quando deveria estar usando outra coisa; ou (b) ele está tentando fazer coisas com os conjuntos que eles não suportam, mas que ele poderia fazer de uma maneira diferente. É bom considerar qual desses é o caso.
kenj0418
6
Pode ser que a resposta mais simples seja usar um conjunto classificado. (Presumo que a singularidade tenha desempenhado um papel ao escolher o conjunto). Mas eu tenho uma pergunta que, como SortedSet é ordenada, por que não existe um método get na API.
Uncaught_exceptions
5
@ HDave: Não, o fato de várias implementações de uma estrutura de dados compartilharem uma propriedade não a torna uma propriedade da própria estrutura de dados. Duas das três implementações comumente usadas da List (ArrayList e Vector) são de acesso aleatório, mas isso não torna o acesso aleatório uma propriedade de Lists.
Michael Myers
74

Na verdade, essa é uma pergunta recorrente ao escrever aplicativos JavaEE que usam o Mapeamento Relacional a Objetos (por exemplo, com o Hibernate); e de todas as pessoas que responderam aqui, Andreas Petersson é o único que entendeu o problema real e ofereceu a resposta correta: Java está faltando uma UniqueList! (ou você também pode chamá-lo de OrderedSet ou IndexedSet).

Maxwing mencionou esse caso de uso (no qual você precisa ordenar E dados exclusivos) e sugeriu o SortedSet, mas não é disso que Marty Pitt realmente precisava.

Esse "IndexedSet" NÃO é o mesmo que um SortedSet - em um SortedSet, os elementos são classificados usando um Comparador (ou usando sua ordem "natural").

Mas, em vez disso, está mais perto de um LinkedHashSet (que outros também sugeriram), ou ainda mais de um (também inexistente) "ArrayListSet", porque garante que os elementos sejam retornados na mesma ordem em que foram inseridos.

Mas o LinkedHashSet é uma implementação, não uma interface! O que é necessário é uma interface IndexedSet (ou ListSet, ou OrderedSet ou UniqueList)! Isso permitirá que o programador especifique que ele precisa de uma coleção de elementos que tenham uma ordem específica e sem duplicatas e instancie-a com qualquer implementação (por exemplo, uma implementação fornecida pelo Hibernate).

Como o JDK é de código aberto, talvez essa interface seja finalmente incluída no Java 7 ...

Sorin Postelnicu
fonte
3
Ótima resposta até o momento, mas o que fazemos enquanto isso?
HDave
claro que é. Eu usei listar muitos e muitos ORM em hibernação antes. Encontrei um problema (ou defeito) quando uma consulta de junção esquerda envolvendo mais de três entidades relacionadas, uma exceção foi lançada. veja aqui para mais detalhes ( jroller.com/eyallupu/entry/… ). Para contornar esse problema, é necessário usar set como coleção de mapeamento ORM. mas honestamente, o set não é conveniente para acessar na programação e também quando você precisa de uma coleção de pedidos. O que realmente precisamos é "indexedset" como o que Sorin Postelnicu disse, SORT e UNIQUE
horaceman
2
O Apache Commons Collections possui o ListOrderedSetque o OP precisava há 7 anos (e eu precisava hoje).
Paul Paul
@Paul: Isso é realmente algo que parece muito bom. Infelizmente, ainda possui três desvantagens: 1) É uma classe, não uma interface. 2) Não está no JDK. 3) Não é o que as consultas do Hibernate estão retornando.
Sorin Postelnicu
Sim, mas além das três principais desvantagens, é perfeito! :) Em retrospecto, eu deveria ter postado meu comentário na pergunta e não na sua resposta - eu encerrei What is needed is an IndexedSet (or ListSet, or OrderedSet, or UniqueList)...e ignorei ...interface. Me desculpe por isso!
Paul
29

Apenas adicionando um ponto que não foi mencionado na resposta de mmyers .

Se eu sei que quero o primeiro item, posso usar set.iterator (). Next (), mas, caso contrário, parece que tenho que converter em uma matriz para recuperar um item em um índice específico?

Quais são as maneiras apropriadas de recuperar dados de um conjunto? (além de usar um iterador)

Você também deve se familiarizar com a SortedSetinterface (cuja implementação mais comum éTreeSet ).

Um SortedSet é um conjunto (ou seja, os elementos são únicos) que é mantido ordenado pela ordem natural dos elementos ou por alguns Comparator. Você pode acessar facilmente o primeiro e o último itens usando first()e last()métodos. UMASortedSet é útil de vez em quando, quando você precisa manter sua coleção livre de duplicados e solicitada de uma certa maneira.

Editar : se você precisar de um conjunto cujos elementos sejam mantidos em ordem de inserção (como uma lista), dê uma olhada LinkedHashSet.

Jonik
fonte
Eu gosto do LinkedHashSet. Mas sim, isso é bom de mencionar. +1
Michael Myers
Obrigado, ajustei a resposta um pouco. (Parece que eu tinha alguns aspectos da TreeSet confundidos com os de LinkedHashSet.)
Jonik
25

Isso leva à questão de quando você deve usar um conjunto e quando deve usar uma lista. Geralmente, o conselho segue:

  1. Se você precisar de dados solicitados, use uma Lista
  2. Se você precisar de dados exclusivos, use um conjunto
  3. Se você precisar dos dois, use: um SortedSet (para dados solicitados pelo comparador) ou um OrderedSet / UniqueList (para dados solicitados por inserção). Infelizmente, a API Java ainda não possui OrderedSet / UniqueList.

Um quarto caso que aparece com frequência é que você não precisa de nenhum. Nesse caso, você vê alguns programadores usando listas e outros com conjuntos. Pessoalmente, acho muito prejudicial ver o conjunto como uma lista sem ordenar - porque é realmente um animal totalmente diferente. A menos que você precise de coisas como exclusividade ou igualdade, defina sempre as listas.

waxwing
fonte
2
se você não for específico, aceite Coleção <T> ou até Iterable <T> e inicialize como uma Lista.
Andreas Petersson
Isso seria um saco ou multiset. Mas o Java não suporta isso; eles dizem que você deve usar a coleção <T> diretamente.
Caracol mecânico
4. você precisa de dados não exclusivos e não se preocupa com o pedido. Você NÃO PODE usar um conjunto. Uma Lista, Bolsa ou Multiset funcionará.
Andrew Gallasch
17

Não tenho certeza se alguém escreveu exatamente dessa maneira, mas você precisa entender o seguinte:

Não há "primeiro" elemento em um conjunto.

Porque, como outros já disseram, os aparelhos não têm ordem. Um conjunto é um conceito matemático que especificamente não inclui pedidos.

Obviamente, seu computador não pode realmente manter uma lista de coisas que não foram encomendadas na memória. Tem que ter algum pedido. Internamente, é uma matriz ou uma lista vinculada ou algo assim. Mas você realmente não sabe o que é e realmente não tem um primeiro elemento; o elemento que sai "primeiro" sai dessa maneira por acaso e pode não ser o primeiro da próxima vez. Mesmo que você tenha tomado medidas para "garantir" um primeiro elemento em particular, ele ainda será lançado por acaso, porque você acertou em uma implementação específica de um conjunto; uma implementação diferente pode não funcionar dessa maneira com o que você fez. E, de fato, você pode não conhecer a implementação que está usando tão bem quanto pensa.

As pessoas se deparam com esse ALL. A. TEMPO. com sistemas RDBMS e não entendo. Uma consulta RDBMS retorna um conjunto de registros. Este é o mesmo tipo de conjunto da matemática: uma coleção não ordenada de itens, apenas nesse caso os itens são registros. Um resultado da consulta RDBMS não tem ordem garantida, a menos que você use a cláusula ORDER BY, mas o tempo todo as pessoas assumem que o fazem e, em seguida, se ativam algum dia quando o formato de seus dados ou código muda ligeiramente e aciona o otimizador de consulta para funcionar. de uma maneira diferente e de repente os resultados não saem na ordem que esperam. Normalmente, são as pessoas que não prestaram atenção na classe do banco de dados (ou ao ler a documentação ou os tutoriais) quando lhes foi explicado antecipadamente que os resultados da consulta não têm um pedido garantido.

skiphoppy
fonte
Heh, e é claro que a ordem geralmente muda logo após o código entrar em produção, quando é muito lento, então eles adicionam um índice para acelerar a consulta. Agora o código roda rápido, mas fornece as respostas erradas. E ninguém percebe por três ou quatro dias ... se você tiver sorte. Se você não tiver sorte, ninguém percebe por um mês ...
TMN
Eu não acho que ele perdeu isso (talvez ele tenha sido desleixado com a notação). Ele não quer o primeiro elemento do conjunto, ele quer um elemento arbitrário do conjunto. Você pode dar a ele um elemento arbitrário, uma vez que Seté Iterable.
Elazar Leibovich
Você está falando de get (index) por index. Que tal um get (Object) por igualdade?
Kumar Manish
10

algumas estruturas de dados estão ausentes nas coleções java padrão.

Bag (como definido, mas pode conter elementos várias vezes)

UniqueList (lista ordenada, pode conter cada elemento apenas uma vez)

parece que você precisaria de uma lista exclusiva neste caso

se você precisar de estruturas de dados flexíveis, poderá estar interessado nas Coleções do Google

Andreas Petersson
fonte
1
O Guva fornece uma "UniqueList"?
Mike Rylander
não, mas você pode ter um java.util.LinkedHashSet que possui propriedades semelhantes.
22613 Andreas Petersson
7

Isso é verdade, o elemento no conjunto não é ordenado, por definição da coleção de conjuntos. Portanto, eles não podem ter acesso por um índice.

Mas por que não temos um método get (objeto), não fornecendo o índice como parâmetro, mas um objeto que é igual ao que estamos procurando? Dessa forma, podemos acessar os dados do elemento dentro do conjunto, apenas conhecendo seus atributos usados ​​pelo método equal.

paredes
fonte
7

Se você quiser fazer muitos acessos aleatórios por índice em um conjunto, poderá obter uma visualização em matriz de seus elementos:

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

Existem duas desvantagens principais:

  1. Não é eficiente em termos de memória, pois é necessário criar uma matriz para todo o conjunto.
  2. Se o conjunto for modificado, a visualização se tornará obsoleta.
fortran
fonte
5

Isso ocorre porque o Set apenas garante exclusividade, mas não diz nada sobre os padrões ideais de acesso ou uso. Ou seja, um conjunto pode ser uma lista ou um mapa, cada um com características de recuperação muito diferentes.

jsight
fonte
5

A única razão pela qual posso pensar em usar um índice numérico em um conjunto seria a iteração. Para isso, use

for(A a : set) { 
   visit(a); 
}
Hugo
fonte
Não é verdade, que tal acessar um elemento aleatório?
Jeremy Salwen 25/08/09
Ha, ha. bom ponto :) mas isso seria altamente propenso a uso indevido, tenho certeza.
247 Hugo Hugo
3

Corri para situações em que eu realmente queria um Ordenado conjunto com acesso via índice (concordo com outros pôsteres de que acessar um conjunto não classificado com um índice não faz sentido). Um exemplo seria uma árvore na qual eu queria que os filhos fossem classificados e filhos duplicados não fossem permitidos.

Eu precisava do acesso via índice para exibi-los e os atributos definidos foram úteis para eliminar com eficiência as duplicatas.

Não encontrando nenhuma coleção adequada nas coleções java.util ou google, achei fácil implementá-la. A idéia básica é agrupar um SortedSet e criar uma lista quando o acesso via índice for necessário (e esquecer a lista quando o SortedSet for alterado). Obviamente, isso só funciona eficientemente quando a alteração do SortedSet agrupado e o acesso à lista são separados durante a vida útil da coleção. Caso contrário, ele se comporta como uma lista que é classificada com frequência, ou seja, muito lenta.

Com um grande número de filhos, esse desempenho melhorou bastante uma lista que eu mantinha classificada através de Collections.sort.

buchweizen
fonte
2

Observe que apenas 2 estruturas básicas de dados podem ser acessadas via índice.

  • A estrutura de dados da matriz pode ser acessada via índice com O(1)complexidade de tempo para alcançar a get(int index)operação.
  • A estrutura de dados do LinkedList também pode ser acessada via índice, mas com O(n)complexidade de tempo para alcançar a get(int index)operação.

Em Java, ArrayListé implementado usando Array a estrutura de dados .

Enquanto Set estrutura de dados normalmente pode ser implementado via HashTable / HashMap ou BalancedTree estrutura de dados, para uma rápida detectar se um elemento existe e adicionar elemento não-existente, normalmente um bem implementado Set pode alcançar O(1)complexidade de tempo containsde operação. Em Java,HashSet é a implementação mais comum usada do Set , é implementada chamando HashMapAPI e HashMapé implementada usando encadeamento separado com listas vinculadas (uma combinação de Array e LinkedList ).

Como o Set pode ser implementado através de uma estrutura de dados diferente, não existe um get(int index)método para isso.

coderz
fonte
As árvores de dedos (consulte a Data.Sequence.lookupfunção de Haskell ) também permitem acessar via índice ( O(1)próximo às extremidades, O(log n)próximo ao meio, com mais precisão O(min(log(k), log(n-k)))), também as árvores binárias também (consulte a Data.Set.lookupIndexfunção de Haskell ). Portanto, sua afirmação inicial de que "Observe que apenas duas estruturas básicas de dados podem ser acessadas via índice" não está correta.
ponto
1

A razão pela qual a interface Set não possui uma chamada do tipo get index ou mesmo algo ainda mais básico, como first () ou last (), é porque é uma operação ambígua e, portanto, potencialmente perigosa. Se um método retornar um conjunto e você chamar, diga o primeiro método (), qual é o resultado esperado, considerando que o conjunto genérico não garante a ordem? O objeto resultante pode muito bem variar entre cada chamada do método, ou pode não levar você a uma falsa sensação de segurança, até que a biblioteca que você está usando altere a implementação e agora você descubra que todo o seu código é interrompido. nenhuma razão particular.

As sugestões sobre soluções alternativas listadas aqui são boas. Se você precisar de acesso indexado, use uma lista. Tenha cuidado ao usar iteradores ou toArray com um conjunto genérico, porque a) não há garantia na ordem eb) não há garantia de que a ordem não será alterada com invocações subsequentes ou com diferentes implementações subjacentes. Se você precisar de algo entre eles, um SortedSet ou LinkedHashSet é o que você deseja.

// Eu gostaria que a interface Set tivesse um elemento get-random-element.

Dan
fonte
1

java.util.Seté uma coleção de itens não pedidos. Não faz sentido se o conjunto tiver um índice get (int), porque o conjunto não possui um índice e você também pode adivinhar o valor.

Se você realmente deseja isso, codifique um método para obter um elemento aleatório de Set.

Resultados da pesquisa Resultados da Web Pi
fonte
0

Você pode fazer new ArrayList<T>(set).get(index)

Janus Troelsen
fonte
Isso retorna uma lista de conjuntos e get (index) retorna um conjunto. Antes, usei: new ArrayList<T>(t).get(0) acho que há uma oposição válida à idéia de obter um elemento específico de um conjunto por um índice. Mas seria bom se o Set tivesse uma função de membro only () que, para Sets do tamanho 1, proporcionasse acesso fácil ao único elemento no Set. Isto salvar o acima mencionado new ArrayListoufor (Foo foo : foos) { return foo; }
Doug Moscrop
0

Se você não se importa com a definição do conjunto, talvez esteja interessado em dar uma olhada no projeto de mapa de árvore indexada .

O reforçada TreeSet / TreeMap fornece o acesso a elementos de índice ou ficando o índice de um elemento. E a implementação é baseada na atualização dos pesos dos nós na árvore RB. Portanto, não há iteração ou backup por uma lista aqui.

Vitaly Sazanovich
fonte
0

Set é uma interface e algumas de suas classes de implementação são HashSet, TreeSet e LinkedHashSet. Ele usa o HashMap sob o capô para armazenar valores. Como o HashMap não preserva o pedido, não é possível obter valor pelo índice.

Agora você deve estar pensando como o Set está usando o HashMap, pois o HashMap armazena um par de chave e valor, mas o Set não. pergunta válida. quando você adiciona um elemento em Set, internamente, ele mantém um HashMap em que a chave é o elemento que você deseja inserir em Set e o valor é a constante dummy. Abaixo está uma implementação interna da função add. Portanto, todas as chaves no HashMap terão o mesmo 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
fonte
Todas Setas implementações estão sendo usadas HashMapsob o capô para armazenar valores. Você pode comprovar essa reivindicação TreeSet?
greybeard 21/03
1
the keys in the HashMap will have the same constant value as chaves na HashMapirá mapear para uma ea mesma coisa imutávelObject
greybeard
-3

Para obter o elemento em um conjunto, eu uso o seguinte:

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
fonte
a função não é o que a pergunta pediu. precisamos do índice, não do valor. qual sua função, afinal? parece que apenas retorna o elemento se fosse igual a um elemento dentro. o que isso faz que contém () não?
Janus Troelsen
Onde está Tdefinido? Por que if (true)?
Quantum