LinkedHashMap vs HashMap! = LinkedList vs ArrayList

Question

Przeczytałem, że LinkedHashMap ma szybszą prędkość iteracji niż HashMap, ponieważ jej elementy są ze sobą podwójnie powiązane. Dodatkowo z tego powodu LinkedHashMap jest wolniejszy podczas wstawiania lub usuwania elementów. Prawdopodobnie dlatego, że te linki również wymagają aktualizacji.

Chociaż można zobaczyć analogię do LinkedList vs ArrayList tym, że elementy LinkedList są podwójnie związane, że odczytać, że iteracje wolniej niż ArrayList i ma krótszy wstawiania i usuwania razy.

Dlaczego tak jest? Być może gdzieś popełniam błąd?

Pozdrawiam!

Answer 1

Analogia nie działa. LinkedList i ArrayList to dwie niepowiązane implementacje Listy. LinkedHashMap jest jednak tą samą strukturą danych co HashMap, ale z wplecioną do niej LinkedList, aby iteracja była szybsza i spójniejsza.

Powodem, że iteracja LinkedHashMap jest szybsza niż iteracja HashMap, jest to, że iteracja HashMap musi iterować nad wszystkimi zasobnikami, nawet tymi pustymi. Fakt, że LinkedHashMap ma listę wskazującą na dane, oznacza, że ​​może pomijać puste segmenty. Lista w LinkedHashMap jest połączoną listą, ponieważ czasy usuwania pozostają stałe (zamiast O (n), jeśli była to lista z pewnymi tablicami).

Answer 2

Niektóre szczegóły:

Kolejność iterator dla LinkedHashMap jest taka sama jak kolejności wkładania do mapy. Tak więc część LinkedList musi tylko "wstawić" na końcu (która jest O (1) dla połączonej listy, która śledzi ogon), a część Map jedynie wstawia mapę, która jest O (1). Ogólna wstawka z listą dołączoną to O (N), a wkładka ArrayList musi kopiować zawartość w układzie szeregowym na jednym gnieździe przed wstawieniem wstawki.

Answer 3

Powiązane listy Okresy iteracji (dostęp do każdego elementu) są "teoretycznie" takie same jak lista tablic. Oba wymagają środowiska wykonawczego O (n) (Big-O Notation). Jednak ponieważ alokacja pamięci dla tablic jest nad ciągłym blokiem pamięci (połączone elementy list są przydzielane indywidualnie i mogą znajdować się w dowolnym miejscu w pamięci), zaczyna działać buforowanie.

Answer 4

Aby powtórzyć listę połączoną, należy wykonać każdy odnośnik (link) w każdym elemencie. Odwołania te mogą wskazywać prawie wszędzie, nie ma gwarancji, że następny element podąża za bieżącym w pamięci, co jest złe dla buforowania. Ponieważ każda referencja musi zostać odzyskana, jest wolniejsza. Tablice są ciągłe w pamięci, a kolejnym elementem jest tylko położenie pamięci bieżącego elementu powiększone o wielkość elementu.

Dla listy podwójnie połączonej wstawianie w dowolnym miejscu tablicy jest bardzo szybkie, ponieważ tylko odniesienia do poprzedniego i następnego elementu muszą zostać zmienione. Z drugiej strony tablica jest wolniejsza, ponieważ wstawienie w dowolnym miejscu spowoduje skopiowanie całej tablicy w celu utworzenia miejsca dla nowego elementu. Nawet dołączenie elementu spowoduje również skopiowanie całej tablicy, gdy nie ma wystarczającej ilości pamięci ciągłej przydzielonej dla macierzy oraz nowo dodanego elementu.

Szczególnie zauważysz różnice w wstawianiu w przypadku dużych zbiorów danych. Niezależnie od tego, jak szybki może być arraycopy(), lista podwójnie połączona jest zawsze szybsza do wstawienia. Ponieważ HashMaps są rzadko iterowane i polegają na wstawianiu i porządku, lista podwójnie połączona może dać temu wzrost wydajności.