czy kolejność iteracji w Java HashMap keySet () jest spójna?

81

Rozumiem, że zestaw zwrócony z metody keySet () mapy nie gwarantuje żadnej określonej kolejności.

Moje pytanie brzmi, czy gwarantuje tę samą kolejność w wielu iteracjach. Na przykład

Map<K,V> map = getMap();

for( K k : map.keySet() )
{
}

...

for( K k : map.keySet() )
{
}

W powyższym kodzie, przy założeniu, że mapa nie jest modyfikowana, iteracja po zestawach kluczy będzie miała tę samą kolejność. Używając jdk15 firmy Sun, wykonuje iterację w tej samej kolejności, ale zanim polegam na tym zachowaniu, chciałbym wiedzieć, czy wszystkie JDK zrobią to samo.

EDYTOWAĆ

Z odpowiedzi widzę, że nie mogę na tym polegać. Szkoda. Miałem nadzieję, że ujdzie mi na sucho i nie będę musiał budować nowej kolekcji, aby zagwarantować moje zamówienie. Mój kod musiał przejść przez iterację, wykonać jakąś logikę, a następnie powtórzyć iterację ponownie z tą samą kolejnością. Po prostu utworzę nową ArrayList z zestawu kluczy, która zagwarantuje porządek.

karoberts
źródło
2
Czy kontrolujesz, która implementacja Map jest zwracana z metody getMap ()?
Andrey Adamovich
2
Z pewnością można uzyskać spójne zamawianie bez tworzenia własnej kolekcji. Zobacz SortedMap, jak wspominali inni. Jeśli więc twoja metoda getMap () zwraca zamiast tego SortedMap, wywołujący będą wiedzieć, że oczekują spójnej kolejności.
PSpeed
Moja odpowiedź dowodzi, że kolejność .keySet()i .values()jest spójna. Niestety przyjęta odpowiedź jest błędna. @karoberts - czy możesz rzucić okiem?
Harshal Parekh

Odpowiedzi:

52

Jeśli dokumentacja API nie gwarantuje, że jest to gwarantowane, nie powinieneś na tym polegać. Zachowanie może się nawet zmienić z jednej wersji JDK do następnej, nawet z JDK tego samego dostawcy.

Możesz łatwo zdobyć zestaw, a następnie po prostu posortować go samodzielnie, prawda?

Ken Liu
źródło
3
Jak ktoś inny wspomniał, jeśli możesz kontrolować, która instancja mapy jest zwracana przez getMap (), możesz zwrócić SortedMap. W takim przypadku prawdopodobnie chciałbyś jawnie zwrócić SortedMap z metody getMap () zamiast tylko mapy.
Ken Liu
4
Kolejność iteracji HashMap i HashSet została zmieniona między Java 7 a Java 8.
user100464
@KenLiu Cześć, jestem nowy w Javie, czy możesz podać przykład, jak uzyskać posortowaną mapę? Wielkie dzięki.
Cecilia
Czy możesz udowodnić, że jest to niespójne? To, że javadoc nie wspomina słowa „gwarantowane”, nie oznacza, że ​​jest niespójne.
Harshal Parekh
Ta odpowiedź jest nieprawidłowa. Są konsekwentni. Tutaj to udowodniłem .
Harshal Parekh
58

Możesz użyć LinkedHashMap, jeśli chcesz mieć HashMap, którego kolejność iteracji nie zmienia się.

Co więcej, zawsze powinieneś go używać, jeśli przeglądasz kolekcję. Iterowanie po entrySet lub keySet HashMap jest znacznie wolniejsze niż w przypadku LinkedHashMap.

ciamej
źródło
9

Map jest tylko interfejsem (a nie klasą), co oznacza, że ​​klasa bazowa, która ją implementuje (a jest ich wiele), może zachowywać się inaczej, a kontrakt dla keySet () w API nie wskazuje, że wymagana jest spójna iteracja.

Jeśli patrzysz na konkretną klasę, która implementuje Map (HashMap, LinkedHashMap, TreeMap itp.), To możesz zobaczyć, jak implementuje ona funkcję keySet (), aby określić, jakie będzie zachowanie, sprawdzając źródło, musisz naprawdę przyjrzyj się algorytmowi, aby sprawdzić, czy właściwość, której szukasz, jest zachowana (to znaczy spójna kolejność iteracji, gdy mapa nie miała żadnych wstawień / usunięć między iteracjami). Na przykład źródło HashMap znajduje się tutaj (otwórz JDK 6): http://www.docjar.com/html/api/java/util/HashMap.java.html

Może się znacznie różnić od jednego JDK do drugiego, więc zdecydowanie nie polegałbym na tym.

Biorąc to pod uwagę, jeśli spójna kolejność iteracji jest czymś, czego naprawdę potrzebujesz, możesz wypróbować LinkedHashMap.

mpobrien
źródło
Klasa Set sama w sobie nie gwarantuje porządku dla swoich elementów, tylko że jest unikalna. Więc kiedy pytasz o .keySet (), zwraca instancję Set, która nie ma gwarantowanej kolejności. Jeśli chcesz uporządkować, musisz to zrobić samodzielnie i posortować je (za pomocą implementacji Collections.sort lub SortedSet)
Matt
7

API for Map nie gwarantuje żadnej kolejności, nawet między wieloma wywołaniami metody na tym samym obiekcie.

W praktyce byłbym bardzo zaskoczony, gdyby kolejność iteracji zmieniła się dla wielu kolejnych wywołań (zakładając, że sama mapa nie zmieniła się w międzyczasie) - ale nie należy (i zgodnie z API nie można) na tym polegać.

EDYCJA - jeśli chcesz polegać na spójności iteracji, potrzebujesz SortedMap, która zapewnia dokładnie te gwarancje.

Andrzej Doyle
źródło
Pokonaj mnie o pięć sekund, więc dodam tylko, że nawet gdybyś mógł na tym polegać, wątpliwe jest, czy powinieneś. Zastanawiam się, dlaczego miałoby się na tym polegać, ponieważ wydaje się to bardzo delikatne.
PSpeed
5

Dla zabawy postanowiłem napisać kod, który będzie służył do zagwarantowania losowej kolejności za każdym razem. Jest to przydatne, abyś mógł wychwycić przypadki, w których jesteś zależny od zamówienia, ale nie powinieneś. Jeśli chcesz polegać na kolejności, jak powiedzieli inni, powinieneś użyć SortedMap. Jeśli po prostu używasz mapy i zdarzy ci się polegać na kolejności, użyj następującego RandomIteratora, aby to złapać. Użyłbym go tylko do testowania kodu, ponieważ zużywa więcej pamięci, niż gdyby tego nie robił.

Możesz również zawinąć mapę (lub zestaw), aby zwrócili RandomeIterator, który pozwoliłby ci użyć pętli for-each.

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class Main
{
    private Main()
    {
    }

    public static void main(final String[] args)
    {
        final Map<String, String> items;

        items = new HashMap<String, String>();
        items.put("A", "1");
        items.put("B", "2");
        items.put("C", "3");
        items.put("D", "4");
        items.put("E", "5");
        items.put("F", "6");
        items.put("G", "7");

        display(items.keySet().iterator());
        System.out.println("---");

        display(items.keySet().iterator());
        System.out.println("---");

        display(new RandomIterator<String>(items.keySet().iterator()));
        System.out.println("---");

        display(new RandomIterator<String>(items.keySet().iterator()));
        System.out.println("---");
    }

    private static <T> void display(final Iterator<T> iterator)
    {
        while(iterator.hasNext())
        {
            final T item;

            item = iterator.next();
            System.out.println(item);
        }
    }
}

class RandomIterator<T>
    implements Iterator<T>
{
    private final Iterator<T> iterator;

    public RandomIterator(final Iterator<T> i)
    {
        final List<T> items;

        items = new ArrayList<T>();

        while(i.hasNext())
        {
            final T item;

            item = i.next();
            items.add(item);
        }

        Collections.shuffle(items);
        iterator = items.iterator();
    }

    public boolean hasNext()
    {
        return (iterator.hasNext());
    }

    public T next()
    {
        return (iterator.next());
    }

    public void remove()
    {
        iterator.remove();
    }
}
TofuBeer
źródło
4

Zgadzam się z rzeczą LinkedHashMap. Po prostu umieszczam moje odkrycia i doświadczenie, gdy miałem problem, gdy próbowałem sortować HashMap według kluczy.

Mój kod do tworzenia HashMap:

HashMap<Integer, String> map;

@Before
public void initData() {
    map = new HashMap<>();

    map.put(55, "John");
    map.put(22, "Apple");
    map.put(66, "Earl");
    map.put(77, "Pearl");
    map.put(12, "George");
    map.put(6, "Rocky");

}

Mam funkcję showMap, która wyświetla wpisy mapy:

public void showMap (Map<Integer, String> map1) {
    for (Map.Entry<Integer,  String> entry: map1.entrySet()) {
        System.out.println("[Key: "+entry.getKey()+ " , "+"Value: "+entry.getValue() +"] ");

    }

}

Teraz, kiedy drukuję mapę przed sortowaniem, wypisuje następującą sekwencję:

Map before sorting : 
[Key: 66 , Value: Earl] 
[Key: 22 , Value: Apple] 
[Key: 6 , Value: Rocky] 
[Key: 55 , Value: John] 
[Key: 12 , Value: George] 
[Key: 77 , Value: Pearl] 

Która jest zasadniczo inna niż kolejność, w której zostały umieszczone klucze mapy.

Teraz, kiedy posortuję go za pomocą kluczy mapy:

    List<Map.Entry<Integer, String>> entries = new ArrayList<>(map.entrySet());

    Collections.sort(entries, new Comparator<Entry<Integer, String>>() {

        @Override
        public int compare(Entry<Integer, String> o1, Entry<Integer, String> o2) {

            return o1.getKey().compareTo(o2.getKey());
        }
    });

    HashMap<Integer, String> sortedMap = new LinkedHashMap<>();

    for (Map.Entry<Integer, String> entry : entries) {
        System.out.println("Putting key:"+entry.getKey());
        sortedMap.put(entry.getKey(), entry.getValue());
    }

    System.out.println("Map after sorting:");

    showMap(sortedMap);

wyjście to:

Sorting by keys : 
Putting key:6
Putting key:12
Putting key:22
Putting key:55
Putting key:66
Putting key:77
Map after sorting:
[Key: 66 , Value: Earl] 
[Key: 6 , Value: Rocky] 
[Key: 22 , Value: Apple] 
[Key: 55 , Value: John] 
[Key: 12 , Value: George] 
[Key: 77 , Value: Pearl] 

Możesz zobaczyć różnicę w kolejności kluczy. Posortowana kolejność kluczy jest w porządku, ale klucz skopiowanej mapy jest ponownie w tej samej kolejności, co wcześniejsza mapa. Nie wiem, czy można to powiedzieć, ale dla dwóch hashmap z tymi samymi kluczami kolejność kluczy jest taka sama. Oznacza to, że kolejność kluczy nie jest gwarantowana, ale może być taka sama dla dwóch map z tymi samymi kluczami ze względu na nieodłączną naturę algorytmu wstawiania kluczy, jeśli implementacja HashMap tej wersji maszyny JVM.

Teraz, kiedy używam LinkedHashMap do kopiowania posortowanych wpisów do HashMap, otrzymuję pożądany wynik (co było naturalne, ale nie o to chodzi. Chodzi o kolejność kluczy w HashMap)

    HashMap<Integer, String> sortedMap = new LinkedHashMap<>();

    for (Map.Entry<Integer, String> entry : entries) {
        System.out.println("Putting key:"+entry.getKey());
        sortedMap.put(entry.getKey(), entry.getValue());
    }

    System.out.println("Map after sorting:");

    showMap(sortedMap);

Wynik:

Sorting by keys : 
Putting key:6
Putting key:12
Putting key:22
Putting key:55
Putting key:66
Putting key:77
Map after sorting:
[Key: 6 , Value: Rocky] 
[Key: 12 , Value: George] 
[Key: 22 , Value: Apple] 
[Key: 55 , Value: John] 
[Key: 66 , Value: Earl] 
[Key: 77 , Value: Pearl] 
Parth Joshi
źródło
3

Hashmap nie gwarantuje, że kolejność mapy pozostanie stała w czasie.

Amir Afghani
źródło
2

Nie musi tak być. Funkcja keySet mapy zwraca zestaw, a metoda iteratora zestawu mówi tak w swojej dokumentacji:

„Zwraca iterator po elementach w tym zestawie. Elementy są zwracane w żadnej określonej kolejności (chyba że ten zestaw jest instancją jakiejś klasy, która zapewnia gwarancję).”

Tak więc, jeśli nie używasz jednej z tych klas z gwarancją, nie ma żadnej.

Jeff Storey
źródło
2

Mapa jest interfejsem i nie definiuje w dokumentacji, że kolejność powinna być taka sama. Oznacza to, że nie możesz polegać na zamówieniu. Ale jeśli kontrolujesz implementację mapy zwracaną przez getMap (), możesz użyć LinkedHashMap lub TreeMap i uzyskiwać tę samą kolejność kluczy / wartości przez cały czas ich iteracji.

Andrey Adamovich
źródło
2

tl; dr Tak.


Uważam, że kolejność iteracji dla .keySet()i .values()jest spójna (Java 8).

Dowód 1 : ładujemy HashMaplosowe klucze i losowe wartości. Wykonujemy iterację, HashMapużywając .keySet()i ładując klucze i odpowiadające im wartości do a LinkedHashMap(zachowa kolejność wstawianych kluczy i wartości). Następnie porównujemy .keySet()obie Mapy i .values()obie Mapy. Zawsze okazuje się taki sam, nigdy nie zawodzi.

public class Sample3 {

    static final String AB = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    static SecureRandom rnd = new SecureRandom();

    // from here: https://stackoverflow.com/a/157202/8430155
    static String randomString(int len){
        StringBuilder sb = new StringBuilder(len);
        for (int i = 0; i < len; i++) {
            sb.append(AB.charAt(rnd.nextInt(AB.length())));
        }
        return sb.toString();
    }

    public static void main(String[] args) throws Exception {
        for (int j = 0; j < 10; j++) {
            Map<String, String> map = new HashMap<>();
            Map<String, String> linkedMap = new LinkedHashMap<>();

            for (int i = 0; i < 1000; i++) {
                String key = randomString(8);
                String value = randomString(8);
                map.put(key, value);
            }

            for (String k : map.keySet()) {
                linkedMap.put(k, map.get(k));
            }

            if (!(map.keySet().toString().equals(linkedMap.keySet().toString()) &&
                  map.values().toString().equals(linkedMap.values().toString()))) {
                // never fails
                System.out.println("Failed");
                break;
            }
        }
    }
}

Dowód 2 : Od tutaj , tablejest tablicą Node<K,V>klasy. Wiemy, że iteracja tablicy za każdym razem da ten sam wynik.

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;

Klasa odpowiedzialna za .values():

final class Values extends AbstractCollection<V> {
    
    // more code here

    public final void forEach(Consumer<? super V> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e.value);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

Klasa odpowiedzialna za .keySet():

final class KeySet extends AbstractSet<K> {

    // more code here

    public final void forEach(Consumer<? super K> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e.key);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

Uważnie przyjrzyj się obu klasom wewnętrznym. Są prawie takie same, z wyjątkiem:

if (size > 0 && (tab = table) != null) {
    int mc = modCount;
    for (int i = 0; i < tab.length; ++i) {
        for (Node<K,V> e = tab[i]; e != null; e = e.next)
            action.accept(e.key);               <- from KeySet class
            // action.accept(e.value);          <- the only change from Values class
    }
    if (modCount != mc)
        throw new ConcurrentModificationException();
}

Iterują na tej samej tablicy, tableaby obsługiwać .keySet()w KeySetklasie i .values()w Valuesklasie.


Dowód 3: ta odpowiedź również wyraźnie stwierdza - Tak więc, keySet (), values ​​() i entrySet () zwracają wartości w kolejności używanej przez wewnętrzną listę połączoną.

Dlatego .keySet()i .values()są spójne.

Harshal Parekh
źródło
1

Logicznie rzecz biorąc, jeśli w umowie jest napisane „żadne konkretne zamówienie nie jest gwarantowane”, a ponieważ „zamówienie, które wyszło raz” jest konkretnym zamówieniem , to odpowiedź brzmi „nie”, nie można polegać na tym, że wyjdzie dwa razy w ten sam sposób.

Jonathan Feinberg
źródło
0

Możesz również przechowywać instancję Set zwróconą przez metodę keySet () i używać tej instancji, gdy potrzebujesz tej samej kolejności.

Shivang Agarwal
źródło
1
Czy to jest jednak gwarantowane? A może każde wywołanie iterator()zwracające iterator z inną kolejnością iteracji, nawet w tym samym zestawie?
Matt Leidholm