W Jaki Sposób Java porządkuje elementy w Hashmapie lub tabeli HashTable?

Po pierwsze: HashMap konkretnie nie zapewnia stabilnego i/lub zdefiniowanego porządku. Więc wszystko, co zaobserwujesz, jest po prostu szczegółem implementacji i nie możesz od niej w żaden sposób zależeć.

Ponieważ czasami warto znać przyczynę pozornie przypadkowego zamówienia, oto podstawowa idea:

A HashMap posiada liczbę kubełków (zaimplementowanych jako tablica), w których można przechowywać wpisy.

Gdy element zostanie dodany do mapy, zostanie przypisany do wiadra na podstawie wartości uzyskanej z jej hashCode i wielkości wiadra HashMap. (Zauważ, że możliwe jest, że wiadro jest już zajęte, co nazywa się kolizją. To jest obsługiwane wdzięcznie i poprawnie, ale zignoruję tę obsługę dla opisu, ponieważ nie zmienia to koncepcji).

Postrzegana kolejność entrów (np. zwracana przez iterację nad Map) zależy od kolejności wpisów w tych wiadrach.

Ilekroć rozmiar jest zmieniany (ponieważ Mapa przekroczyła swój próg pełności), wtedy zmienia się liczba łyżek, co oznacza, że pozycja każdego elementu może się zmienić, ponieważ pozycja łyżki pochodzi również od liczby łyżek.

HashMap nie sortuje w ogóle. Dla mapy sortującej według wartości klucza należy użyć TreeMap.

From the JavaDocs for TreeMap:

Czerwono-czarne drzewo oparte na implementacji interfejs SortedMap. Ta klasa gwarantuje, że mapa będzie w rosnąca kolejność klawiszy, posortowane według do naturalnego porządku dla klucza klasy (patrz porównywalne), lub przez komparator dostarczony w czasie tworzenia, w zależności od tego, który konstruktor jest używany.

Z dokumentacja HashMap:

Ta klasa nie daje żadnych gwarancji co do kolejność mapy; w szczególności, nie gwarantuje, że zamówienie pozostanie stała w czasie.

A Map nie jest uporządkowaną strukturą danych - nie należy polegać na tym, że wpisy w HashMap są w określonej kolejności. Niektóre implementacje Map, takie jak LinkedHashMap i TreeMap gwarantują pewną kolejność, ale HashMap nie gwarantuje.

Jeśli naprawdę chcesz wiedzieć, co dzieje się wewnętrznie, Wyszukaj kod źródłowy HashMap - możesz go znaleźć w src.zip , który powinien znajdować się w katalogu instalacyjnym JDK.

A HashMap posiada pewną liczbę "wiader", w których przechowuje swoje wpisy. Które bucket wpis jest przechowywany jest określony przez kod hash klucza wpisu. Kolejność wyświetlania wpisów w HashMap zależy od kodów skrótu kluczy. Ale nie pisz programów, które polegają na tym, że wpisy są w określonej kolejności w HashMap - implementacja może się zmienić w przyszłej wersji Javy i twój program nie będzie już działał.

Hashmap ma nie zdefiniowaną kolejność elementów

Nie ma zdefiniowanej kolejności w tabeli hash. Klucze są umieszczane w gnieździe, na podstawie kodu hash, ale nawet to nie jest trywialne kolejność po kodzie hash.

HashMap przechowuje wartości za pomocą unikalnej wartości hash Wygenerowanej za pomocą części klucza. Ta wartość skrótu mapuje adres, w którym ma być przechowywana. W ten sposób zapewnia dostęp O(1).

LinkedHashmap z drugiej strony zachowuje kolejność dodawania do mapy.