Uporządkowana mapa Java


322

W Javie, czy istnieje obiekt, który działa jak mapa do przechowywania i uzyskiwania dostępu do par klucz / wartość, ale może zwrócić uporządkowaną listę kluczy i uporządkowaną listę wartości, tak że listy kluczy i wartości są w tej samej kolejności?

Więc jako wyjaśnienie po kodzie szukam czegoś, co zachowuje się jak moja fikcyjna mapa zamówień:

OrderedMap<Integer, String> om = new OrderedMap<>();
om.put(0, "Zero");
om.put(7, "Seven");

String o = om.get(7); // o is "Seven"
List<Integer> keys = om.getKeys();
List<String> values = om.getValues();

for(int i = 0; i < keys.size(); i++)
{
    Integer key = keys.get(i);
    String value = values.get(i);
    Assert(om.get(key) == value);
}

4
Jeśli wszystko, co chcesz zrobić, to iterowanie obu jednocześnie, Map.entrySet () pozwoli ci to zrobić na dowolnej mapie. LinkedHashMap ma dobrze zdefiniowaną kolejność, ale dla każdej mapy zestaw wpisów odzwierciedla pary klucz / wartość.
Pete Kirkham

5
Ten kod nie jest dobrym przykładem, ponieważ każda implementacja mapy będzie zachowywać się jak przykładowy kod. posortowane, uporządkowane lub nie.
Peter Lawrey,

2
W implementacji Sun JDK, zestawy zwracane przez getKeys i getValues ​​() są wspierane przez entrySet () na mapie, więc będą miały tę samą kolejność iteracji, co testują twoje próbki.
Pete Kirkham

4
To interesujące, nigdy tego nie zauważyłem. Nadal nazywaj mnie szalonym, ale wolę nie przyjmować założeń dotyczących implementacji, które nie są wyraźnie weryfikowane przez interfejs. W przeszłości robiłem to zbyt wiele razy.
Whatsit

2
Powinno to nosić nazwę Java Sorted Map, ponieważ mapa uporządkowana to coś innego - patrz LinkedHashMap.
Ondra Žižka

Odpowiedzi:


397

SortedMap interfejs (z realizacją TreeMap ) powinien być twoim przyjacielem.

Interfejs ma następujące metody:

  • keySet() który zwraca zestaw kluczy w kolejności rosnącej
  • values() który zwraca kolekcję wszystkich wartości w porządku rosnącym odpowiednich kluczy

Interfejs ten spełnia dokładnie Twoje wymagania. Klucze muszą jednak mieć znaczącą kolejność. W przeciwnym razie możesz użyć LinkedHashMap, gdzie kolejność jest ustalana na podstawie kolejności wstawiania.


2
przykład: SortedMap <Ciąg, Obiekt> mapa = nowy TreeMap <> ();
Ben

7
Aby użyć TreeMap, wymagana była klasa kluczy, która musi implementować interfejs porównywalny. Jeśli nie, zostanie zgłoszony jakiś wyjątek RuntimeException. TreeMap to także posortowana mapa, ale myślę, że autor chce użyć właśnie uporządkowanej (nie posortowanej) mapy. LinkedHashMap to dobry wybór, aby uzyskać tylko zamówioną mapę (jak powiedziałeś, „ustaloną przez kolejność wstawiania”).
K. Gol

1
odpowiedź można poprawić, pokazując, jak wykonać iterację po keySet ()

4
Z java 8 doc . LinkedHashMapw której kolejności iteracji jest kolejność, w której jej wpisy były ostatnio otwierane
TRiNE

1
@TRiNE Nie śledzę twojego komentarza, ale mogłem przeoczyć jakiś kontekst. Domyślnie LinkedHashMapkolejność iteracji to kolejność wstawiania, ale zamiast tego można użyć innego konstruktora, aby określić kolejność dostępu. docs.oracle.com/javase/8/docs/api/java/util/…
rob

212

Czy istnieje obiekt, który działa jak mapa do przechowywania i uzyskiwania dostępu do par klucz / wartość, ale może zwrócić uporządkowaną listę kluczy i uporządkowaną listę wartości, tak że listy kluczy i wartości są w tej samej kolejności?

Szukasz java.util.LinkedHashMap . Otrzymasz listę par Map.Entry <K, V> , które zawsze są iterowane w tej samej kolejności. Ta kolejność jest taka sama, jak kolejność umieszczania elementów. Alternatywnie, użyj java.util.SortedMap , gdzie klucze muszą mieć naturalną kolejność lub mieć ją określoną przez Comparator.


14
Aby po prostu zaoszczędzić czytnikowi podwójnego sprawdzania tego, ponieważ trudno jest to sprawdzić przez testowanie, keySet()metoda skutecznie zwraca LinkedHashSet, który odzwierciedla kolejność twoich put()wywołań. Pamiętaj, że wielokrotne połączenia z put()tym samym kluczem nie zmienią kolejności, chyba że remove()wcześniej klucz.
Glenn Lawrence

Z java 8 doc . LinkedHashMapw której kolejności iteracji jest kolejność, w której ostatnio uzyskano dostęp do jej wpisów
TRiNE

24

LinkedHashMap zachowuje porządek kluczy.

Wygląda na to, że java.util.LinkedHashMap działa tak samo jak normalna HashMap.


1
To nie daje odpowiedzi na pytanie. Aby skrytykować lub poprosić autora o wyjaśnienie, zostaw komentarz pod jego postem - zawsze możesz komentować własne posty, a gdy będziesz mieć odpowiednią reputację , będziesz mógł komentować każdy post .
ianaya89,

2
@ ianaya89 Myślę, że to prawdziwa odpowiedź, ale jest bardzo podobna do odpowiedzi Johna Feminelli !
T30

1
Jeśli chcesz uzyskać uporządkowaną mapę, w której wpisy są przechowywane w takiej kolejności, w jakiej umieszczasz je na mapie, poprawną odpowiedzią jest LinkedHashMap. Jeśli chcesz posortować wpisy na mapie niezależnie od kolejności, w jakiej je umieściłeś, to SortedMap jest właściwą odpowiedzią.
Ralph

@TRiNE Połączony dokument java 8 mówi, że możliwe są dwa tryby porządkowania: kolejność wstawiania i kolejność dostępu. Zastanawiasz się nad tym drugim, który jest wywoływany przez użycie specjalnego konstruktora public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder). Domyślny konstruktor tworzy instancję LinkedHashMap zamówioną przy wstawianiu.
Artur Łysik

1
@ ArturŁysik tak to jest. To był błąd, który popełniłem kilka dni temu. Poprawię to. Usuwam komentarz. ponieważ nie mogę go już edytować
TRiNE

7

Myślę, że najbliższą kolekcją, którą otrzymasz z frameworka, jest SortedMap


3
Głosowałbym za odrzuceniem tej odpowiedzi, jeśli uznałem, że warto za nią stracić punkty. Jak wskazuje powyższa odpowiedź, w twojej odpowiedzi brakuje odpowiednich informacji o LinkedHashMap, a małe wyjaśnienie SortedMap również byłoby miłe.
CorayThan,

@CorayThan, w takim przypadku głosujesz za najlepszymi odpowiedziami, nie głosujesz za innymi, które mogą być poprawne, ale nie najlepsze ...
bruno conde

1
To jest to co zrobiłem. Tylko mówię, że rozumiem, dlaczego ktoś głosowałby na to.
CorayThan,

5

Możesz wykorzystać interfejs NavigableMap , do którego można uzyskać dostęp i przejść w kolejności rosnącej lub malejącej. Ten interfejs ma zastąpić interfejs SortedMap. Nawigowalna mapa jest zwykle sortowana zgodnie z naturalną kolejnością jej klawiszy lub według Komparatora dostępnego w czasie tworzenia mapy.

Istnieją trzy najbardziej użyteczne implementacje go: TreeMap , ImmutableSortedMap i ConcurrentSkipListMap .

Przykład TreeMap:

TreeMap<String, Integer> users = new TreeMap<String, Integer>();
users.put("Bob", 1);
users.put("Alice", 2);
users.put("John", 3);

for (String key: users.keySet()) {
  System.out.println(key + " (ID = "+ users.get(key) + ")");
}

Wynik:

Alice (ID = 2)
Bob (ID = 1)
John (ID = 3)



2

tl; dr

Aby utrzymać Map< Integer , String >porządek posortowany według klucza, użyj jednej z dwóch klas implementujących interfejsy SortedMap/ NavigableMap:

  • TreeMap
  • ConcurrentSkipListMap

Jeśli manipulujesz mapą w jednym wątku, użyj pierwszego TreeMap,. Jeśli manipulowania drugiej nici, użyj drugiego, ConcurrentSkipListMap.

Aby uzyskać szczegółowe informacje, zobacz poniższą tabelę i następującą dyskusję.

Detale

Oto tabela graficzna, którą stworzyłem, pokazującą funkcje dziesięciu Mapimplementacji dołączonych do Java 11.

NavigableMapInterfejs jest to, co SortedMappowinno być na pierwszym miejscu. SortedMapLogicznie powinien być usunięty, ale nie może być tak niektóre implementacje map 3rd-Party można za pomocą interfejsu.

Jak widać w tej tabeli, tylko dwie klasy implementują interfejsy SortedMap/ NavigableMap:

Oba te klucze trzymają w uporządkowanej kolejności, według ich naturalnej kolejności (przy użyciu compareTometody Comparable( https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/ Comparable.html ) interfejs) lub przez Comparatorprzekazaną implementację. Różnica między tymi dwiema klasami polega na tym, że druga ConcurrentSkipListMap, jest bezpieczna dla wątków , wysoce współbieżna .

Zobacz także kolumnę Kolejność iteracji w poniższej tabeli.

  • LinkedHashMapKlasa zwraca swoje wpisy w kolejności, w jakiej zostały one pierwotnie wstawionego .
  • EnumMapzwraca wpisy w kolejności, w której zdefiniowana jest klasa enum klucza . Na przykład mapa, której pracownik pokrywa, który dzień tygodnia ( Map< DayOfWeek , Person >) korzysta z DayOfWeekklasy enum wbudowanej w Javę. To wyliczenie jest zdefiniowane w poniedziałek pierwszy i niedziela ostatni. Wpisy w iteratorze pojawią się w tej kolejności.

Pozostałe sześć implementacji nie obiecuje kolejności zgłoszeń.

Tabela implementacji map w Javie 11, porównanie ich funkcji


0

Użyłem mapy Simple Hash, połączonej listy i kolekcji, aby posortować mapę według wartości.

import java.util.*;
import java.util.Map.*;
public class Solution {

    public static void main(String[] args) {
        // create a simple hash map and insert some key-value pairs into it
        Map<String, Integer> map = new HashMap<String, Integer>();
        map.put("Python", 3);
        map.put("C", 0);
        map.put("JavaScript", 4);
        map.put("C++", 1);
        map.put("Golang", 5);
        map.put("Java", 2);
        // Create a linked list from the above map entries
        List<Entry<String, Integer>> list = new LinkedList<Entry<String, Integer>>(map.entrySet());
        // sort the linked list using Collections.sort()
        Collections.sort(list, new Comparator<Entry<String, Integer>>(){
        @Override
         public int compare(Entry<String, Integer> m1, Entry<String, Integer> m2) {
        return m1.getValue().compareTo(m2.getValue());
        }
      });
      for(Entry<String, Integer> value: list) {
         System.out.println(value);
     }
   }
}

Dane wyjściowe to:

C=0
C++=1
Java=2
Python=3
JavaScript=4
Golang=5
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.