Kiedy używać HashMap zamiast LinkedList lub ArrayList i odwrotnie

82

Z jakiego powodu nie zawsze możemy używać HashMap, mimo że jest on znacznie wydajniejszy niż ArrayList czy LinkedList w operacjach dodawania, usuwania, również niezależnie od liczby elementów.

Przeszukałem go w Google i znalazłem kilka powodów, ale zawsze istniało obejście dla korzystania z HashMap, z zaletami wciąż żyjącymi.


źródło
11
Listsi Mapssą to dwie zupełnie różne struktury danych, z różnymi operacjami i niezmiennikami. Czy możesz wyjaśnić kontekst / wymagania, o których myślisz, gdzie oba byłyby akceptowalne rozwiązania?
Mark Peters
3
Najwyraźniej nigdy nie musiałeś utrzymywać zestawu rzeczy w określonej kolejności ...
Brian Roach
52
Głosuj przeciw, dlaczego? Myślę, że to właściwe pytanie. Pokazuje jednak brak wiedzy, ale w kwestii SO nie należy go bagatelizować za wykazanie braku wiedzy. W rzeczywistości pytanie jest zawsze wynikiem braku wiedzy.

Odpowiedzi:

96

Listy reprezentują sekwencyjne uporządkowanie elementów. Mapy są używane do reprezentowania zbioru par klucz / wartość.

Chociaż możesz użyć mapy jako listy, istnieją pewne określone wady takiego rozwiązania.

Utrzymanie porządku: - Lista z definicji jest uporządkowana. Dodajesz elementy, a następnie możesz ponownie przeglądać listę w kolejności wstawienia pozycji. Kiedy dodajesz elementy do HashMap, nie masz gwarancji, że odzyskasz elementy w tej samej kolejności, w jakiej je umieściłeś. Istnieją podklasy HashMap, takie jak LinkedHashMap, które utrzymają kolejność, ale generalnie kolejność nie jest gwarantowana w przypadku mapy.

Semantyka klucz / wartość: - Celem mapy jest przechowywanie elementów w oparciu o klucz, którego można użyć do późniejszego pobrania elementu. Podobną funkcjonalność można osiągnąć tylko za pomocą listy w ograniczonym przypadku, gdy klucz jest pozycją na liście.

Czytelność kodu Rozważ następujące przykłady.

    // Adding to a List
    list.add(myObject);         // adds to the end of the list
    map.put(myKey, myObject);   // sure, you can do this, but what is myKey?
    map.put("1", myObject);     // you could use the position as a key but why?

    // Iterating through the items
    for (Object o : myList)           // nice and easy
    for (Object o : myMap.values())   // more code and the order is not guaranteed

Funkcjonalność kolekcji Niektóre wspaniałe funkcje narzędziowe są dostępne dla list za pośrednictwem klasy Kolekcje. Na przykład ...

    // Randomize the list
    Collections.shuffle(myList);

    // Sort the list
    Collections.sort(myList, myComparator);  

Mam nadzieję że to pomoże,

polster
źródło
Często mówi się, że LinkedLists są złe z powodu problemów z wydajnością. Często używam LinkedLists zamiast ArrayLists ze względu na porządkowanie elementów. Czy byłoby lepiej (pod względem wydajności i pamięci), gdybym użył HashMaps z pozycjami jako kluczami?
Cesar Castro
33

Listy i mapy to różne struktury danych. Mapy są używane, gdy chcesz skojarzyć klucz z wartością, a listy są uporządkowaną kolekcją.

Map to interfejs w Java Collection Framework, a HashMap to jedna z implementacji interfejsu Map. HashMap są wydajne do lokalizowania wartości na podstawie klucza oraz wstawiania i usuwania wartości na podstawie klucza. Wpisy HashMap nie są uporządkowane.

ArrayList i LinkedList są implementacjami interfejsu List. LinkedList zapewnia dostęp sekwencyjny i ogólnie jest bardziej wydajny w wstawianiu i usuwaniu elementów na liście, jednak jest mniej wydajny w uzyskiwaniu dostępu do elementów na liście. ArrayList zapewnia swobodny dostęp i jest bardziej wydajny w uzyskiwaniu dostępu do elementów, ale generalnie wolniej wstawia i usuwa elementy.

jazzdawg
źródło
1

Podam tutaj kilka prawdziwych przykładów i scenariuszy, kiedy użyć jednego lub drugiego, może to być pomocne dla kogoś innego:

HashMap

Kiedy musisz używać pamięci podręcznej w swojej aplikacji. Redis i membase to jakiś rodzaj rozszerzonej HashMap. (Nie ma znaczenia kolejność elementów, potrzebujesz szybkiego (O (1)) dostępu do odczytu (wartość) za pomocą klucza).

Połączona lista

Gdy kolejność jest ważna (są uporządkowane tak, jak zostały dodane do LinkedList), liczba elementów jest nieznana (nie marnuj przydziału pamięci) i potrzebujesz szybkiego czasu wstawienia (O (1)). Dobrym przykładem jest lista zadań do wykonania, które mogą być wyświetlane sekwencyjnie w miarę ich dodawania.

vhbazan
źródło
0

Wadą ArrayList i LinkedList jest to, że podczas iteracji po nich, w zależności od algorytmu wyszukiwania, czas potrzebny na znalezienie elementu rośnie wraz z rozmiarem listy.

Piękno haszowania polega na tym, że chociaż poświęcasz trochę czasu na szukanie elementu, czas ten nie rośnie wraz z rozmiarem mapy. Dzieje się tak, ponieważ HashMap znajduje informacje, konwertując szukany element bezpośrednio do indeksu, aby mógł wykonać skok.

Krótko mówiąc ... LinkedList : Zużywa trochę więcej pamięci niż ArrayList, niski koszt wstawiania (dodawania i usuwania) ArrayList : Zużywa mało pamięci, ale podobnie do LinkedList, a wyszukiwanie zajmuje więcej czasu, gdy jest duży. HashMap : może wykonać skok do wartości, dzięki czemu czas wyszukiwania jest stały dla dużych map. Zużywa więcej pamięci i zajmuje więcej czasu, aby znaleźć wartość niż małe listy.

Simon Walker
źródło