Dlaczego java.util.Set nie ma get (int index)?

237

Jestem pewien, że istnieje dobry powód, ale czy ktoś mógłby wyjaśnić, dlaczego java.util.Setbrakuje interfejsu get(int Index)lub jakąkolwiek podobną get()metodę?

Wygląda na to, że zestawy świetnie nadają się do wkładania rzeczy, ale nie mogę znaleźć eleganckiego sposobu na odzyskanie z nich pojedynczego przedmiotu.

Jeśli wiem, że chcę pierwszy element, mogę go użyć set.iterator().next(), ale w przeciwnym razie wydaje się, że muszę rzucić na tablicę, aby pobrać element o określonym indeksie?

Jakie są odpowiednie sposoby pobierania danych z zestawu? (inne niż użycie iteratora)

Jestem pewien, że fakt wykluczenia go z interfejsu API oznacza, że ​​istnieje dobry powód, aby tego nie robić - czy ktoś mógłby mnie oświecić?

EDYCJA: Niektóre bardzo świetne odpowiedzi tutaj, a kilka mówi „więcej kontekstu”. Konkretnym scenariuszem był test dbUnit, w którym mogłem racjonalnie stwierdzić, że zwrócony zestaw z zapytania zawierał tylko 1 element i próbowałem uzyskać dostęp do tego elementu.

Jednak pytanie jest ważniejsze bez scenariusza, ponieważ pozostaje bardziej skoncentrowane:

Jaka jest różnica między zestawem a listą .

Dziękujemy wszystkim za fantastyczne odpowiedzi poniżej.

Marty Pitt
źródło
1
Dlaczego otrzymujesz element z zestawu według indeksu? Czy próbujesz użyć zestawu jako posortowanej tablicy?
MSN
Szczególnym przypadkiem jest tutaj test dbUnit na Zestaw zwrócony z wywołania hibernacji. W moim teście uzasadnione jest założenie (ponieważ to twierdzę), że zwrócony obiekt jest w określonej kolejności, z powodu mojego IDataSet, którego użyłem, aby go skonfigurować. Jest to nietypowy przypadek, ale prowadzi do mojej ciekawości dotyczącej API.
Marty Pitt,
1
Dodanie rzeczy w określonej kolejności nie oznacza, że ​​tak pozostanie, chyba że używasz niestandardowej implementacji zestawu.
Michael Myers
1
„Jeśli wiem, że chcę pierwszy element, mogę użyć set.iterator (). Next ()” - ten wiersz nie ma sensu. Naprawdę mówisz: „Jeśli wiem, że chcę pierwszy element, zgodnie z definicją implementacji pierwszego elementu, mogę…”. Sam zestaw jest nieuporządkowany, więc indeksowany dostęp nie ma sensu. Teraz, gdyby istniał ArrayListSet, miałoby to większy sens (wystarczy rzutować na „Listę” i być szczęśliwym). Może mógłbyś podać więcej kontekstu dla pytania?
jsight
Zestaw nie jest nieuporządkowany! Niektóre jego implementacje są, ale niektóre implementacje są wyraźnie uporządkowane w określony sposób.
reinierpost

Odpowiedzi:

176

Ponieważ zestawy nie mają kolejności. Niektóre implementacje tak robią (szczególnie te implementujące java.util.SortedSetinterfejs), ale nie jest to ogólna właściwość zestawów.

Jeśli próbujesz używać zestawów w ten sposób, powinieneś rozważyć użycie listy.

Michael Myers
źródło
10
@matt b: Nie, myślę, że powinien to rozważyć. Myślenie jest dobre. ;)
Michael Myers
10
Zastanów się, a następnie zrób to.
Joe Phillips,
21
„Rozważ” to prawidłowe sformułowanie. Istnieją dwa możliwe problemy (a) używa zestawu, kiedy powinien używać czegoś innego, lub (b) próbuje robić rzeczy z zestawami, których nie obsługują, ale które mógłby zrobić inaczej. Warto zastanowić się, który z nich ma miejsce.
kenj0418
6
Prostszą odpowiedzią może być użycie posortowanego zestawu. (Zakładam, że wyjątkowość odgrywała pewną rolę przy wyborze zestawu). Ale mam pytanie, skoro SortedSet jest zamówiony, dlaczego nie ma metody get w API.
uncaught_exceptions
5
@HDave: Nie, fakt, że wielokrotne implementacje struktury danych współużytkują właściwość, nie czyni z niej właściwości samej struktury danych. Dwie z trzech powszechnie używanych implementacji List (ArrayList i Vector) mają dostęp losowy, ale nie czyni losowego dostępu właściwością Lists.
Michael Myers
74

W rzeczywistości jest to powtarzające się pytanie podczas pisania aplikacji JavaEE, które używają mapowania obiektowo-relacyjnego (na przykład przy Hibernacji); a spośród wszystkich osób, które tu odpowiedziały, Andreas Petersson jest jedynym, który zrozumiał prawdziwy problem i zaoferował poprawną odpowiedź: Java nie ma UniqueList! (lub możesz też nazwać to OrDERSet lub IndexedSet).

Maxwing wspomniał o tym przypadku użycia (w którym potrzebujesz uporządkowanych ORAZ unikalnych danych) i zasugerował SortedSet, ale nie tego naprawdę potrzebował Marty Pitt.

Ten „IndexedSet” NIE jest tym samym, co SortedSet - w SortedSet elementy są sortowane za pomocą komparatora (lub przy użyciu ich „naturalnego” uporządkowania).

Zamiast tego jest bliżej LinkedHashSet (który inni też sugerowali), a jeszcze bardziej do (również nieistniejącego) „ArrayListSet”, ponieważ gwarantuje, że elementy są zwracane w tej samej kolejności, w jakiej zostały wstawione.

Ale LinkedHashSet jest implementacją, a nie interfejsem! Potrzebny jest interfejs IndexedSet (lub ListSet, OrdersSet lub UniqueList)! Pozwoli to programiście określić, że potrzebuje kolekcji elementów o określonej kolejności i bez duplikatów, a następnie utworzyć instancję z dowolną implementacją (na przykład implementacją zapewnianą przez Hibernację).

Ponieważ JDK jest oprogramowaniem typu open source, być może ten interfejs zostanie w końcu zawarty w Javie 7 ...

Sorin Postelnicu
źródło
3
Jak na razie świetna odpowiedź, ale co robimy w międzyczasie?
HDave
jasne, że tak. wcześniej używałam listy jako wielu i wielu ORM w hibernacji. napotkałem problem (lub wadę), gdy lewe zapytanie dołączające obejmujące więcej niż 3 powiązane podmioty, został zgłoszony wyjątek. zajrzyj tutaj, aby uzyskać więcej informacji ( jroller.com/eyallupu/entry/… ). aby obejść ten problem, konieczne jest użycie zestawu jako kolekcji mapowania ORM. ale szczerze mówiąc, zestaw nie jest wygodny w dostępie do programowania, a także wtedy, gdy potrzebujesz kolekcji zamówień. tak naprawdę potrzebujemy „zestawu indeksów”, jak powiedział Sorin Postelnicu, SORT i UNIKALNE
horaceman
2
Kolekcje Apache Commons mają ListOrderedSetto, czego OP potrzebował 7 lat temu (a ja potrzebowałem dzisiaj).
Paul
@Paul: To jest naprawdę coś, co wygląda naprawdę dobrze. Niestety nadal ma 3 wady: 1) To klasa, a nie interfejs. 2) Nie ma go w JDK. 3) Nie o to zwracają zapytania Hibernacja.
Sorin Postelnicu,
Tak, ale oprócz tych 3 głównych wad, jest idealny! :) Z perspektywy czasu powinienem opublikować swój komentarz do pytania, a nie twoją odpowiedź - zgodziłem się What is needed is an IndexedSet (or ListSet, or OrderedSet, or UniqueList)...i zignorowałem ...interface. Przepraszam za to!
Paul
29

Wystarczy dodać jeden punkt, który nie został wymieniony w odpowiedzi mmyersa .

Jeśli wiem, że chcę pierwszy element, mogę użyć set.iterator (). Next (), ale w przeciwnym razie wydaje się, że muszę rzucić się na tablicę, aby pobrać element o określonym indeksie?

Jakie są odpowiednie sposoby pobierania danych z zestawu? (inne niż użycie iteratora)

Powinieneś także zapoznać się z SortedSetinterfejsem (którego najczęstszą implementacją jest TreeSet).

SortedSet to zestaw (tzn. Elementy są unikalne), który jest utrzymywany w kolejności przez naturalne uporządkowanie elementów lub za pomocą niektórych Comparator. Możesz łatwo uzyskać dostęp do pierwszego i ostatniego elementu za pomocą first()i last()metod. A SortedSetprzydaje się od czasu do czasu, gdy musisz zachować swoją kolekcję bez duplikatów i zamówić w określony sposób.

Edycja : jeśli potrzebujesz zestawu, którego elementy są przechowywane w kolejności wstawiania (podobnie jak lista), spójrz na LinkedHashSet.

Jonik
źródło
Sam lubię LinkedHashSet. Ale tak, warto o tym wspomnieć. +1
Michael Myers
Dzięki, trochę poprawiłem odpowiedź. (Wydaje się, że miała pewne aspekty TreeSet mylić z tych LinkedHashSet).
Jonik
25

Ten rodzaj prowadzi do pytania, kiedy powinieneś użyć zestawu, a kiedy powinieneś użyć listy. Zwykle rada brzmi:

  1. Jeśli potrzebujesz uporządkowanych danych, skorzystaj z listy
  2. Jeśli potrzebujesz unikalnych danych, użyj zestawu
  3. Jeśli potrzebujesz obu, użyj albo: SortedSet (dla danych uporządkowanych przez komparator) lub OrDERSet / UniqueList (dla danych uporządkowanych przez wstawienie). Niestety interfejs API języka Java nie ma jeszcze klasy OrdersSet / UniqueList.

Czwarty przypadek, który pojawia się często, to, że nie potrzebujesz żadnego. W tym przypadku niektórzy programiści korzystają z list, a niektórzy z zestawami. Osobiście uważam za bardzo szkodliwe widzieć zestaw jako listę bez zamawiania - ponieważ tak naprawdę jest to zupełnie inna bestia. O ile nie potrzebujesz rzeczy takich jak zestaw unikatowości lub zestaw równości, zawsze faworyzuj listy.

jemiołucha
źródło
2
jeśli jesteś nieokreślony, zaakceptuj Collection <T> lub nawet Iterable <T> i zainicjuj jako Listę.
Andreas Petersson
To byłaby torba lub multiset. Ale Java ich nie obsługuje; mówią, że powinieneś po prostu użyć Collection <T> bezpośrednio.
Ślimak mechaniczny
4. potrzebujesz nie unikatowych danych i nie dbasz o porządek. NIE MOŻNA użyć zestawu. Lista, Torba lub Multiset będą działać.
Andrew Gallasch,
17

Nie jestem pewien, czy ktokolwiek napisał to dokładnie w ten sposób, ale musisz zrozumieć, co następuje:

W zestawie nie ma „pierwszego” elementu.

Ponieważ, jak powiedzieli inni, zestawy nie mają kolejności. Zestaw jest matematyczną koncepcją, która w szczególności nie obejmuje zamawiania.

Oczywiście, twój komputer nie może tak naprawdę przechowywać listy rzeczy, które nie są uporządkowane w pamięci. To musi mieć jakieś zamówienie. Wewnętrznie jest to tablica, połączona lista lub coś takiego. Ale tak naprawdę nie wiesz, co to jest, i tak naprawdę nie ma pierwszego elementu; element, który wychodzi „pierwszy”, wychodzi w ten sposób przez przypadek i może nie być pierwszy raz następnym razem. Nawet jeśli podjąłeś kroki w celu „zagwarantowania” określonego pierwszego elementu, nadal pojawia się on przypadkowo, ponieważ akurat udało ci się go poprawnie zastosować do jednej konkretnej implementacji zestawu; inna implementacja może nie działać w ten sposób z tym, co zrobiłeś. W rzeczywistości możesz nie wiedzieć, jakiej implementacji używasz tak dobrze, jak myślisz.

Ludzie wpadają na to WSZYSTKO. THE. CZAS. z systemami RDBMS i nie rozumiem. Zapytanie RDBMS zwraca zestaw rekordów. Jest to ten sam typ zestawu z matematyki: nieuporządkowany zbiór elementów, tylko w tym przypadku elementy są rekordami. Wynik zapytania RDBMS nie ma żadnej gwarantowanej kolejności, chyba że użyjesz klauzuli ORDER BY, ale przez cały czas ludzie to zakładają, a następnie wyzwalają się pewnego dnia, gdy kształt ich danych lub kodu zmienia się nieznacznie i uruchamia optymalizator zapytań do działania w inny sposób i nagle wyniki nie pojawiają się w oczekiwanej kolejności. Są to zazwyczaj ludzie, którzy nie zwracali uwagi w klasie bazy danych (lub podczas czytania dokumentacji lub samouczków), gdy wyjaśniono im z góry, że wyniki zapytania nie mają gwarantowanej kolejności.

skiphoppy
źródło
Heh, i oczywiście kolejność zwykle zmienia się zaraz po uruchomieniu kodu, gdy jest on zbyt wolny, więc dodają indeks, aby przyspieszyć zapytanie. Teraz kod działa szybko, ale podaje błędne odpowiedzi. I nikt nie zauważa przez trzy lub cztery dni ... jeśli masz szczęście. Jeśli nie masz szczęścia, nikt tego nie zauważy przez miesiąc ...
TMN
Nie sądzę, żeby to przegapił (być może był niechlujny z notacją). Nie chce pierwszego elementu ze zbioru, chce dowolnego elementu ze zbioru. Możesz dać mu dowolny element, skoro Setjest Iterable.
Elazar Leibovich,
Mówisz o get (indeks) według indeksu. Co powiesz na uzyskanie (Object) przez równość?
Kumar Manish
10

brakuje niektórych struktur danych w standardowych kolekcjach Java.

Torba (jak zestaw, ale może zawierać elementy wiele razy)

UniqueList (lista uporządkowana, każdy element może zawierać tylko raz)

wygląda na to, że w tym przypadku potrzebujesz unikalnej listy

jeśli potrzebujesz elastycznych struktur danych, możesz być zainteresowany kolekcjami Google

Andreas Petersson
źródło
1
Czy Guva zapewnia „UniqueList”?
Mike Rylander,
nie, ale możesz mieć java.util.LinkedHashSet, który ma podobne właściwości.
Andreas Petersson,
7

To prawda, elementy w zestawie nie są uporządkowane z definicji kolekcji zestawu. Dlatego nie mogą być dostępne za pomocą indeksu.

Ale dlaczego nie mamy metody get (object), nie podając indeksu jako parametru, ale obiekt równy temu, którego szukamy? W ten sposób możemy uzyskać dostęp do danych elementu w zestawie, po prostu znając jego atrybuty używane przez metodę równości.

ściany
źródło
7

Jeśli zamierzasz wykonywać wiele losowych wejść według indeksu w zestawie, możesz uzyskać widok tablicy jego elementów:

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

Istnieją jednak dwie główne wady:

  1. Nie jest efektywny pod względem pamięci, ponieważ należy utworzyć tablicę dla całego zestawu.
  2. Jeśli zestaw zostanie zmodyfikowany, widok stanie się nieaktualny.
fortran
źródło
5

Wynika to z faktu, że Set gwarantuje tylko wyjątkowość, ale nie mówi nic o optymalnych wzorcach dostępu lub użytkowania. Tj. Zestaw może być listą lub mapą, z których każda ma bardzo różne właściwości wyszukiwania.

jsight
źródło
5

Jedynym powodem, dla którego mogę wymyślić użycie indeksu numerycznego w zestawie, jest iteracja. W tym celu użyj

for(A a : set) { 
   visit(a); 
}
Hugo
źródło
Nieprawda, a co z dostępem do losowego elementu?
Jeremy Salwen,
Ha ha. dobra uwaga :) ale na pewno byłoby to bardzo podatne na niewłaściwe użycie, jestem pewien.
Hugo
3

Natrafiłem na sytuacje, w których naprawdę chciałem Posortować zestaw z dostępem przez indeks (zgadzam się z innymi plakatami, że dostęp do nieposortowanego zestawu z indeksem nie ma sensu). Przykładem może być drzewo, w którym chciałem, aby dzieci były sortowane, a duplikowanie dzieci nie było dozwolone.

Potrzebowałem dostępu za pomocą indeksu, aby je wyświetlić, a zestaw atrybutów przydał się, aby skutecznie wyeliminować duplikaty.

Nie znajdując żadnej odpowiedniej kolekcji w kolekcjach java.util lub google, uznałem, że to proste. Podstawowym pomysłem jest zawinięcie SortedSet i utworzenie listy, gdy wymagany jest dostęp za pośrednictwem indeksu (i zapomnienie listy po zmianie SortedSet). Działa to oczywiście tylko efektywnie, gdy zmieni się zawinięty SortedSet i dostęp do listy jest oddzielony w czasie istnienia kolekcji. W przeciwnym razie zachowuje się jak często sortowana lista, tj. Zbyt wolno.

W przypadku dużej liczby dzieci poprawiło się to znacznie w porównaniu z listą, którą posortowałem za pośrednictwem Collections.sort.

Buchweizen
źródło
2

Należy pamiętać, że tylko 2 podstawowe struktury danych są dostępne poprzez indeks.

  • Dostęp do struktury danych macierzy można uzyskać za pomocą indeksu ze O(1)złożonością czasową, aby osiągnąć get(int index)działanie.
  • Dostęp do struktury danych LinkedList można również uzyskać za pośrednictwem indeksu, ale ze O(n)złożonością czasową, aby osiągnąć get(int index)działanie.

W Javie ArrayListjest implementowany przy użyciu struktury danych Array .

Podczas gdy struktura danych zestawu zwykle może być zaimplementowana za pomocą struktury danych HashTable / HashMap lub BalancedTree , w celu szybkiego wykrycia, czy element istnieje i dodania nieistniejącego elementu, zwykle dobrze zaimplementowany zestaw może osiągnąć operację O(1)złożoności czasowej contains. W Javie HashSetjest najczęściej stosowaną implementacją Seta , jest implementowana przez wywołanie HashMapAPI i HashMapjest implementowana za pomocą oddzielnego łączenia z listami połączonymi (kombinacja Array i LinkedList ).

Ponieważ zestaw można zaimplementować za pomocą innej struktury danych, nie ma get(int index)na to metody.

coderz
źródło
Drzewa palcowe (patrz Data.Sequence.lookupfunkcja Haskella ) umożliwiają również dostęp przez indeks ( O(1)bliżej końca w O(log n)pobliżu środka, dokładniej O(min(log(k), log(n-k)))), również drzewa binarne (patrz Data.Set.lookupIndexfunkcja Haskella ). Zatem twoje początkowe stwierdzenie, że „Uwaga: tylko 2 podstawowe struktury danych są dostępne za pośrednictwem indeksu” jest nieprawidłowe.
średnik
1

Powód, dla którego ustawiony jest interfejs nie ma wywołania typu indeks ani nawet czegoś bardziej podstawowego, takiego jak first () lub last (), jest to, że jest to operacja niejednoznaczna, a zatem potencjalnie niebezpieczna. Jeśli metoda zwraca Set, a ty wywołujesz metodę powiedzmy first (), jaki jest oczekiwany wynik, biorąc pod uwagę, że ogólny zestaw nie daje żadnych gwarancji przy zamówieniu? Wynikowy obiekt może bardzo różnić się między poszczególnymi wywołaniami metody, lub może nie wprawić cię w fałszywe poczucie bezpieczeństwa, dopóki biblioteka, której używasz, nie zmieni zmian pod implementacją, a teraz okaże się, że cały kod się psuje Bez szczególnego powodu.

Podane tutaj sugestie dotyczące obejść są dobre. Jeśli potrzebujesz dostępu indeksowanego, skorzystaj z listy. Zachowaj ostrożność przy korzystaniu z iteratorów lub tablicy z ogólnym zestawem, ponieważ a) nie ma gwarancji na zamówienie ib) nie ma gwarancji, że zamówienie nie zmieni się przy kolejnych wywołaniach lub różnych implementacjach bazowych. Jeśli potrzebujesz czegoś pomiędzy, SortedSet lub LinkedHashSet jest tym, czego potrzebujesz.

// Chciałbym, żeby interfejs Set miał element get-random.

Dan
źródło
1

java.util.Setto zbiór niezamówionych przedmiotów. Nie ma sensu, jeśli Set ma get (int index), ponieważ Set nie ma indeksu, a ty tylko możesz odgadnąć wartość.

Jeśli naprawdę tego chcesz, koduj metodę, aby uzyskać losowy element z Seta.

Wyniki wyszukiwania Wyniki sieciowe Pi
źródło
0

Możesz to zrobić new ArrayList<T>(set).get(index)

Janus Troelsen
źródło
Zwraca listę zestawów, a get (indeks) zwraca zestaw. Raczej użyłem: new ArrayList<T>(t).get(0) myślę, że istnieje uzasadniony sprzeciw wobec pomysłu uzyskania określonego elementu z zestawu przez indeks. Byłoby jednak miło, gdyby Set miał funkcję only () członka, która dla zestawów o rozmiarze 1 zapewniała łatwy dostęp do jedynego elementu w zestawie. Pozwoliłoby to zaoszczędzić wspomniana new ArrayListlubfor (Foo foo : foos) { return foo; }
Doug Moscrop
0

Jeśli nie przeszkadza ci sortowanie zestawu, możesz zainteresować się projektem indeksu drzewa indeksowanego .

Ulepszone TreeSet / TreeMap zapewnia dostęp do elementów poprzez indeks lub uzyskanie indeksu elementu. A implementacja opiera się na aktualizacji wag węzłów w drzewie RB. Więc nie ma iteracji ani kopii zapasowej listy tutaj.

Witalij Sazanowicz
źródło
0

Zestaw jest interfejsem, a niektóre z jego klas implementacji to HashSet, TreeSet i LinkedHashSet. Używa HashMap pod maską do przechowywania wartości. Ponieważ HashMap nie zachowuje kolejności, nie można uzyskać wartości według indeksu.

Musisz teraz myśleć o tym, jak Set używa HashMap, ponieważ HashMap przechowuje parę klucz-wartość, ale Set nie. ważne pytanie. gdy dodajesz element do zestawu, wewnętrznie zachowuje on HashMap, gdzie klucz jest elementem, który chcesz wprowadzić w zestawie, a wartość jest stałą manekina. Poniżej znajduje się wewnętrzna implementacja funkcji add. Dlatego wszystkie klucze w HashMap będą miały tę samą stałą wartość.

// 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;
}
magnonimy
źródło
Wszystkie Setimplementacje używają HashMappod maską do przechowywania wartości. Czy możesz uzasadnić to roszczenie TreeSet?
siwobrody
1
the keys in the HashMap will have the same constant value klucze wHashMap mapie zostaną przypisane do tego samego niezmiennegoObject
siwobrody
-3

Aby uzyskać element w zestawie, używam następującego:

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
źródło
funkcja nie jest tym, o co pytano. potrzebujemy indeksu, a nie wartości. jaka jest twoja funkcja? wygląda na to, że po prostu zwraca element, jeśli był równy elementowi wewnątrz. co to robi, że nie zawiera ()?
Janus Troelsen
Gdzie jest Tzdefiniowane? Dlaczego if (true)?
kwantowo,