Mapa/ArrayList: który z nich jest szybszy w wyszukiwaniu elementu

Question

Mam gigantyczny zestaw danych, który muszę przechowywać w kolekcji i muszę znaleźć tam wszystkie duplikaty.

Wielkość danych może być większa niż 1 milion. Wiem, że mogę przechowywać więcej elementów w ArrayList comapre do Map.

Moje pytania są następujące:

1. szuka klucza w Map szybciej niż szukając w posortowanej ArrayList?
2. wyszukuje Klucz w HashMap jest szybszy niż TreeMap?
3. Tylko w kategoriach miejsca wymaganego do przechowywania elementów n, które byłyby bardziej wydajne między implementacją TreeMap i HashMap?

Answer 1

1) Tak. Wyszukiwanie ArrayList wynosi średnio O (n). Wydajność wyszukiwania kluczy w mapie zależy od konkretnej implementacji. Możesz napisać implementację Map, która jest O (n) lub gorsza, jeśli naprawdę chcesz, ale wszystkie implementacje w standardowej bibliotece są szybsze niż O (n).

2) Tak. HashMap to średnio O (1) dla prostych wyszukiwań kluczy. TreeMap to O (log (n)).

Class HashMap<K,V>

Ta implementacja zapewnia wydajność stałą czasową dla podstawowych operacji (get i put), przyjmując funkcję skrótu rozprasza elementów prawidłowo wśród wiader.

Class TreeMap<K,V>

Ta implementacja zapewnia gwarantowane log (n) koszt czasu dla containsKey, get, put i usunąć operacje. Algorytmy są adaptacjami w Cormen, Leiserson i Rivest's Introduction to Algorithms.

3) Wymagania przestrzenne będą w obu przypadkach O (n). Byłoby domysły wymaga nieco więcej miejsca, ale tylko przez stały współczynnik.

Answer 2

1. Zależy to od rodzaju używanego Map.
2. HashMap ma średnią odnośnika stałej czasowej (O (1)), natomiast TreeMap „S średni czas, wyszukiwanie jest oparte na głębokość drzewa (O (log (n))), dzięki czemu a HashMap jest szybszy.
3. Różnica jest prawdopodobnie dyskusyjna. Obie struktury danych wymagają pewnej ilości stałego narzutu w złożoności przestrzennej według projektu (oba wykazują złożoność przestrzeni).