Jak zachować unikalną listę w Javie?

104

Jak utworzyć listę unikalnych / odrębnych obiektów (bez duplikatów) w Javie?

W tej chwili używam HashMap<String, Integer>do tego, ponieważ klucz jest nadpisywany i dlatego na końcu możemy uzyskać HashMap.getKeySet()unikatowy. Ale jestem pewien, że powinien być lepszy sposób, aby to zrobić, ponieważ część wartości jest tutaj marnowana.

Basil Bourque
źródło

Odpowiedzi:

164

Możesz użyć implementacji Set :

Kilka informacji z JAVADoc:

Kolekcja, która nie zawiera zduplikowanych elementów . Bardziej formalnie, zbiory nie zawierają pary elementów e1 i e2, takich jak e1.equals (e2) i co najwyżej jeden element zerowy. Jak sugeruje jego nazwa, ten interfejs modeluje matematyczną abstrakcję zbioru.

Uwaga: należy zachować dużą ostrożność, jeśli zmienne obiekty są używane jako elementy zestawu. Zachowanie zestawu nie jest określone, jeśli wartość obiektu zostanie zmieniona w sposób, który wpływa na porównania równości, gdy obiekt jest elementem zestawu. Szczególnym przypadkiem tego zakazu jest to, że niedopuszczalne jest, aby zestaw zawierał siebie jako element. "

Oto implementacje:

  • HashSet

    Ta klasa zapewnia stałą wydajność czasową dla podstawowych operacji (dodawanie, usuwanie, zawiera i rozmiar), przy założeniu, że funkcja skrótu prawidłowo rozprasza elementy między zasobnikami. Iterowanie po tym zestawie wymaga czasu proporcjonalnego do sumy rozmiaru instancji HashSet (liczby elementów) plus „pojemność” kopii zapasowej instancji HashMap (liczba zasobników). Dlatego bardzo ważne jest, aby nie ustawiać zbyt dużej początkowej pojemności (lub zbyt niskiego współczynnika obciążenia), jeśli ważna jest wydajność iteracji.

    Podczas iteracji a HashSetkolejność uzyskanych elementów jest niezdefiniowana.

  • LinkedHashSet

    Implementacja tabeli skrótów i połączonych list interfejsu Set z przewidywalną kolejnością iteracji. Ta implementacja różni się od HashSet tym, że utrzymuje podwójnie połączoną listę obejmującą wszystkie jej wpisy. Ta połączona lista definiuje kolejność iteracji, czyli kolejność, w jakiej elementy zostały wstawione do zestawu (kolejność wstawiania). Pamiętaj, że ponowne wstawienie elementu do zestawu nie ma wpływu na kolejność wstawiania. (Element e jest ponownie wstawiany do zbioru s, jeśli s.add (e) zostanie wywołane, gdy s.contains (e) zwróci wartość true bezpośrednio przed wywołaniem).

    Tak więc wynik powyższego kodu ...

     Set<Integer> linkedHashSet = new LinkedHashSet<>();
     linkedHashSet.add(3);
     linkedHashSet.add(1);
     linkedHashSet.add(2);
    
     for (int i : linkedHashSet) {
         System.out.println(i);
     }
    

    ... będzie koniecznie

    3
    1
    2
    
  • TreeSet

    Ta implementacja zapewnia gwarantowany koszt log (n) czasu dla podstawowych operacji (dodawanie, usuwanie i zawiera). Domyślnie elementy zwracane podczas iteracji są sortowane według ich " naturalnego porządku ", więc powyższy kod ...

     Set<Integer> treeSet = new TreeSet<>();
     treeSet.add(3);
     treeSet.add(1);
     treeSet.add(2);
    
     for (int i : treeSet) {
         System.out.println(i);
     }
    

    ... wyświetli to:

    1
    2
    3
    

    (Możesz także przekazać Comparatorinstancję do TreeSetkonstruktora, co spowoduje sortowanie elementów w innej kolejności).

    Zwróć uwagę, że kolejność obsługiwana przez zestaw (niezależnie od tego, czy podano jawny komparator) musi być zgodna z równymi, jeśli ma poprawnie zaimplementować interfejs Set. (Zobacz Comparable lub Comparator, aby uzyskać dokładną definicję zgodności z równymi). Dzieje się tak, ponieważ interfejs Set jest zdefiniowany w kategoriach operacji równości, ale wystąpienie TreeSet wykonuje wszystkie porównania elementów przy użyciu metody compareTo (lub porównaj), więc dwa elementy uważane za równe w tej metodzie są z punktu widzenia zbioru równe. Zachowanie zbioru jest dobrze zdefiniowane, nawet jeśli jego kolejność jest niezgodna z równymi; po prostu nie spełnia warunków umowy ogólnej interfejsu Set.

Szczery
źródło
Teraz jestem zdezorientowany, którego mam użyć? Po prostu muszę mieć listę unikalnych ciągów. Więc w zasadzie nawet jeśli dodany zostanie istniejący ciąg, powinien zostać dodany.
1
Wybór należy do Ciebie ... HashSet jest uniwersalny i szybki, zestaw drzew jest zamawiany, LinkedHashset utrzymuje kolejność reklamową ...
Frank
6
To nie jest LISTA ... więc nie wszystkie metody interfejsu LISTA są dostępne.
marcolopes
2
Zestaw nie jest listą, nie mogę wyszukiwać elementów według indeksu w zestawie w czasie O (1) (dostęp losowy).
wilmol
13

Chcę tutaj wyjaśnić kilka rzeczy dotyczących oryginalnego plakatu, do których inni nawiązywali, ale tak naprawdę nie powiedzieli tego wyraźnie. Kiedy mówisz, że chcesz mieć unikalną listę, jest to definicja uporządkowanego zestawu. Niektóre inne kluczowe różnice między interfejsem Set a interfejsem List polegają na tym, że List umożliwia określenie indeksu wstawiania. Zatem pytanie brzmi, czy naprawdę potrzebujesz interfejsu listy (np. W celu zapewnienia zgodności z biblioteką innej firmy itp.), Czy też możesz przeprojektować swoje oprogramowanie, aby korzystało z interfejsu Set? Musisz także wziąć pod uwagę, co robisz z interfejsem. Czy ważne jest, aby znajdować elementy według ich indeksu? Ile elementów spodziewasz się w swoim zestawie? Jeśli będziesz mieć wiele elementów, czy zamawianie jest ważne?

Jeśli naprawdę potrzebujesz listy, która ma tylko unikalne ograniczenie, istnieje klasa Apache Common Utils org.apache.commons.collections.list.SetUniqueList, która zapewni Ci interfejs List i unikalne ograniczenie. Pamiętaj, że psuje to interfejs List. Uzyskasz jednak lepszą wydajność, jeśli będziesz musiał przeszukiwać listę według indeksu. Jeśli możesz sobie poradzić z interfejsem Set i masz mniejszy zestaw danych, to LinkedHashSet może być dobrym rozwiązaniem. Zależy to tylko od projektu i przeznaczenia oprogramowania.

Znowu każda kolekcja ma pewne zalety i wady. Niektóre szybkie wstawienia, ale powolne odczyty, niektóre mają szybkie odczyty, ale powolne wstawienia, itp. Warto spędzić sporo czasu z dokumentacją kolekcji, aby w pełni poznać szczegóły każdej klasy i interfejsu.

Paul Connolly
źródło
3
To nie daje odpowiedzi na pytanie. Aby skrytykować lub poprosić autora o wyjaśnienie, zostaw komentarz pod jego postem - zawsze możesz komentować własne posty, a gdy zdobędziesz wystarczającą reputację , będziesz mógł komentować każdy post .
Zach Saucier,
1
Właściwie to dostarcza odpowiedzi. Jeśli chce tylko listy, która działa jak zestaw, użyj org.apache.commons.collections.list.SetUniqueList, ale jako programista powinniśmy być bardziej ostrożni i powinniśmy więcej pomyśleć o problemie. Jeśli dzięki temu moja odpowiedź będzie lepsza, „Jak utworzyć unikalną listę w Javie?” List uniqueList = new SetUniqueList () ;, oto jak ....
Paul Connolly,
3
Zach, nie próbuję być dupkiem, ale czy przeczytałeś w ogóle moją odpowiedź przed swoim komentarzem? A może po prostu tego nie rozumiesz? Jeśli tego nie rozumiesz, to ok - daj mi znać, a rozwinę temat. Nie sądzę, żebym musiał pisać traktat o strukturach danych, aby udzielić przyjaznej odpowiedzi na czyjeś pytanie. Nie obchodzi mnie też pokorny sposób budowania reputacji komentarza, kiedy znam odpowiedź i nikt inny jej tak naprawdę nie udzielił.
Paul Connolly,
1
A tak przy okazji, nie krytykowałem ani nie prosiłem autora o wyjaśnienia, po prostu mówiłem, że może albo A) szybko skorzystać z klasy, którą mu dałem, albo B) poświęcić trochę czasu, aby naprawdę zrozumieć różnice między tymi klasami i odnieść się je do jego potrzeb. B oczywiście trwa dłużej, ale w dłuższej perspektywie da lepszy kod.
Paul Connolly,
8

Użyj new HashSet<String> przykładu:

import java.util.HashSet;
import java.util.Set;

public class MainClass {
  public static void main(String args[]) {
    String[] name1 = { "Amy", "Jose", "Jeremy", "Alice", "Patrick" };

    String[] name2 = { "Alan", "Amy", "Jeremy", "Helen", "Alexi" };

    String[] name3 = { "Adel", "Aaron", "Amy", "James", "Alice" };

    Set<String> letter = new HashSet<String>();

    for (int i = 0; i < name1.length; i++)
      letter.add(name1[i]);

    for (int j = 0; j < name2.length; j++)
      letter.add(name2[j]);

    for (int k = 0; k < name3.length; k++)
      letter.add(name3[k]);

    System.out.println(letter.size() + " letters must be sent to: " + letter);

  }
}
tim_a
źródło
2
Wystarczy dodać out put powyższego programu -> 11 liter należy przesyłać na adres: [Aaron, Alice, James, Adel, Jose, Jeremy, Amy, Alan Patrick, Helen, Alexi]
Ammad
4

Możesz po prostu użyć a, HashSet<String>aby zachować kolekcję unikalnych obiektów. Jeśli Integerwartości na mapie są ważne, możesz zamiast tego użyć containsKeymetody map, aby sprawdzić, czy klucz znajduje się już na mapie.

Ted Hopp
źródło
3

HashSet<String>(lub) dowolna Setimplementacja może wykonać zadanie za Ciebie. Setnie zezwalaj na duplikaty.

Oto javadoc dla HashSet.

kosa
źródło
2

Nie wiem, na ile to wydajne, jednak zadziałało dla mnie w prostym kontekście.

List<int> uniqueNumbers = new ArrayList<>();

   public void AddNumberToList(int num)
    {
        if(!uniqueNumbers .contains(num)) {
            uniqueNumbers .add(num);
        }
    }
Zapnologica
źródło
1

Możesz chcieć użyć jednej z klas implementujących java.util.Set<E>Interface, np java.util.HashSet<String> . Klasy kolekcji.

Kolekcja, która nie zawiera zduplikowanych elementów. Bardziej formalnie, zbiory nie zawierają pary elementów e1 i e2, takich jak e1.equals (e2) i co najwyżej jeden element zerowy. Jak sugeruje jego nazwa, ten interfejs modeluje matematyczną abstrakcję zbioru.

Yogendra Singh
źródło