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

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.

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?

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.

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.

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.

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();
    }
}

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] 

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

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.

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.

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.

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.

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