Czy powinienem użyć `HashSet` lub` TreeSet` dla bardzo dużego zestawu danych?

Question

Mam wymóg przechowywania od 2 do 15 milionów kont (które są String o długości 15) w strukturze danych dla celów wyszukiwania i sprawdzania unikalności. Początkowo planowałem przechowywać je w postaci HashSet, ale wątpię, aby szybkość wyszukiwania była wolna z powodu kolizji i ostatecznie będzie wolniejsza niż mapa drzewa (przy użyciu wyszukiwania binarnego).

Nie ma wymogu sortowania danych. Używam Java 7. Mam system 64G z 48G dedykowany dla tej aplikacji.

To pytanie nie jest duplikatem HashSet and TreeSet performance test dlatego, że pytanie jest o wykonywaniu dodawanie elementów do Set i to pytanie jest o wydajności sprawdzenia istniejącego Set dla zduplikowanych wartości.

Answer 1

Kiedy staraliśmy się zapisać 50 milionów płyt w HashMap z odpowiednich parametrów inicjalizacji, wprowadzenie zaczął spowolnienie, szczególnie po 35 milionów płyt. Zmiana na TreeMap dała stałą wydajność wstawiania i pobierania.

Obserwacja: TreeMap zapewni lepszą wydajność niż HashMap dla dużego zestawu danych wejściowych. Dla mniejszego zestawu oczywiście HashMap zapewni lepszą wydajność.

Answer 2

Jeśli masz 48 GB dedykowanej pamięci dla swoich 2 mln do 15 milionów płyt, najlepiej jest prawdopodobnie użyć HashMap<Key, Record>, gdzie klucz jest Integer lub String w zależności od wymagań.

Będziesz w porządku, jeśli dojdzie do kolizji mieszacza, o ile zapewnisz wystarczającą ilość pamięci dla Map i uzyskasz odpowiedni współczynnik obciążenia.

Zalecam użycie następującego konstruktora: new HashMap<>(13_000_000); (30% więcej niż oczekiwana liczba rekordów - które zostanie automatycznie rozszerzone o do implementacji na komórki 2^24). Poinformuj swoją aplikację, że ta Map będzie bardzo duża od samego początku, więc nie będzie automatycznie rosnąć w miarę zapełniania.

HashMap wykorzystuje czas O(1) dostępu dla jego członków, natomiast TreeMap wykorzystuje O(log n) czas odnośnika, ale może być bardziej efektywne z pamięci i nie potrzebuje mądrego funkcję mieszającą. Jeśli jednak używasz kluczy String lub Integer, nie musisz martwić się o zaprojektowanie funkcji mieszania, a stałe sprawdzanie czasu będzie ogromną poprawą. Kolejną zaletą TreeMap/TreeSet jest posortowane uporządkowanie, o którym mówisz, że Cię to nie obchodzi; użyj HashMap.

Jeśli jedynym celem jest sprawdzenie listy unikalnych numerów kont, to wszystko, co powiedziałem powyżej, jest nadal prawdziwe, ale jak stwierdził w swoim pytaniu, należy użyć HashSet<String>, a nie HashMap. Zalecenia dotyczące wydajności i argument konstruktora nadal mają zastosowanie.

Dalsze czytanie: HashSet and TreeSet performance test