OK, to może być pytanie superstupid, ale jestem trochę zaniepokojony bankomatem i chętnie usłyszeć, co możesz mi o tym powiedzieć.

Miałem listę array, dodano liście około 5 milionów. Te długie są obliczane skróty dla kluczy podstawowych (ciągłe łańcuchy) z wielkiego pliku CSV.

Teraz chciałem sprawdzić wyjątkowość i zapętlić się przez listę:

for(int i=0;i<hashArrayList.size();i++)
{
   long refValue = hashArrayList.get(i)
   for(int j=i+1;j<hashArrayList.size();j++)
   {
      if(refValue == hashArrayList.get(j))
      --> UNIQUENESS VIOLATION, now EXPLODE!!
   }
}

W ten sposób zajmuje wiele godzin.

Teraz o Hashset, który nie pozwala na siebie duplikatów. Hashset.addall (Hasharraylist) trwa 4 sekundy! Wyeliminując / nie dodawanie duplikatów do tej listy za pomocą elementów 5 Mio.

Jak to robi? I: Czy moja arraylista - zapętla się tak głupio?

-1
Toni Kanoni 5 czerwiec 2018, 13:58

3 odpowiedzi

Najlepsza odpowiedź

Robisz całkowicie inne porównanie.

Z arraylistą masz zagnieżdżoną pętlę dla , co sprawia, że jest O(n^2).

Ale z hashetem nie robisz żadnych zapętlek, ale po prostu dodawanie elementów n, który jest O(n). Wewnętrznie hashet używa HashMap, którego kluczem jest poszczególne elementy listy i wartości jest statyczne obiekt .

Kod źródłowy dla HashSet (Java 8)

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

addAll połączenia add

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

W końcu wszystko przychodzi do wstawienia obiektu (tutaj długi ) do Hashmap, który zapewnia stałą wydajność czasu 1


1 Od Javadoc of Hashmap ( Kopalnia nacisk )

Implementacja ta zapewnia stałą wydajność dla podstawowych operacji (Get and Put), Zakładając funkcję Hash rozprasza elementy prawidłowo wśród wiader

3
user7 5 czerwiec 2018, 11:09

Kolekcja oparta na Hash nie potrzebuje zapętle, aby sprawdzić, czy istnieją elementy z tym samym kluczem.

Wyobraź sobie, że masz 1.000 obiektów X. W twoim przypadku pętla się przez listę za każdym razem, gdy coś dodasz.

Kolekcja oparta na Hash oblicza hash obiektu, patrzy do wewnątrz, czy istnieją inne elementy z tym samym hash, a następnie muszą sprawdzić, czy jeden z nich jest równy nowym elemencie. Jeśli masz dobrą funkcję Hash, która zwraca wyjątkowe hash dla unikalnych elementów, wystarczy obliczyć numer.

Oczywiście, jeśli po prostu powiesz "Jestem leniwy i zastępowałem moją metodę hashcode z powrotem 1", wtedy miałbyś taką samą ilość porównań dodatkowych do obrotu kolekcji Hash.

Przykład: Wyobraź sobie, że masz następujący hashset:

HashSet: [[obj1], [null], [null], [null], [obj2, obj3, obj4]]

Jak widać, podstawowa struktura (może być) taka: tablica zawierająca inne struktury danych z rzeczywistymi wpisami. Teraz, jeśli umieścisz OBJ5 do Hashsetu, zadzwoni na obj5.hashcode (). Na tej podstawie obliczy zewnętrzny indeks tego obj. Powiedzmy o 4:

HashSet: [[obj1], [null], [null], [null], [obj2, obj3, obj4]]
                                                  ^ obj5

Teraz mamy trzy inne obiekty z tym samym indeksem. Tak, potrzebujemy tutaj pętli, aby sprawdzić, czy niektóre z nich są równi nowym obj5, ale jeśli masz większy haszet z milionami wpisów, porównanie z elementami jest znacznie szybsze niż w porównaniu ze wszystkimi elementami. Jest to zaleta kolekcji opartej na Hash.

1
Synth 5 czerwiec 2018, 11:58

Hashmap wewnętrzny pracujący

Ponadto używasz pętli wewnątrz pętli, która tworzy złożoność O (n ^ 2), co jest mniej wydajne, co używa Hashmap.

0
Arnab Dhar 5 czerwiec 2018, 11:07