HashMap
zawiera określoną liczbę zasobników. Używa hashCode
do określenia, do którego wiadra je umieścić. Dla uproszczenia wyobraź sobie to jako moduł.
Jeśli nasz hashcode to 123456 i mamy 4 segmenty, 123456 % 4 = 0
więc element trafia do pierwszego segmentu, Bucket 1.
Jeśli nasza funkcja hashcode jest dobra, powinna zapewniać równomierną dystrybucję, więc wszystkie zasobniki będą używane w pewnym stopniu po równo. W tym przypadku zasobnik używa połączonej listy do przechowywania wartości.
Ale nie można polegać na ludziach, którzy zaimplementują dobre funkcje skrótu. Ludzie często piszą słabe funkcje skrótu, co spowoduje nierównomierną dystrybucję. Możliwe jest również, że po prostu mieliśmy pecha z naszymi danymi wejściowymi.
Im mniej równomierny jest ten rozkład, tym dalej przechodzimy od operacji O (1) i tym bliżej zbliżamy się do operacji O (n).
Wdrożenie Hashmap próbuje to złagodzić, organizując niektóre segmenty w drzewa zamiast połączonych list, jeśli zasobniki stają się zbyt duże. Po to TREEIFY_THRESHOLD = 8
jest. Jeśli wiadro zawiera więcej niż osiem elementów, powinno stać się drzewem.
To drzewo jest drzewem czerwono-czarnym. Najpierw jest sortowany według kodu skrótu. Jeśli kody skrótu są takie same, używa compareTo
metody, Comparable
jeśli obiekty implementują ten interfejs, w przeciwnym razie kod skrótu tożsamości.
Jeśli wpisy zostaną usunięte z mapy, liczba wpisów w zasobniku może się zmniejszyć, tak że ta struktura drzewa nie będzie już potrzebna. Do tego UNTREEIFY_THRESHOLD = 6
służy. Jeśli liczba elementów w zasobniku spadnie poniżej sześciu, równie dobrze możemy wrócić do korzystania z listy połączonej.
Wreszcie jest MIN_TREEIFY_CAPACITY = 64
.
Kiedy mapa skrótów rośnie, automatycznie zmienia swój rozmiar, aby mieć więcej zasobników. Jeśli mamy małą mapę mieszania, prawdopodobieństwo, że otrzymamy bardzo pełne segmenty, jest dość wysokie, ponieważ nie mamy tak wielu różnych segmentów, w których można umieścić rzeczy. Znacznie lepiej jest mieć większą mapę mieszania z większą liczbą mniejszych zasobników. Ta stała w zasadzie mówi, że nie należy zaczynać przekształcania wiader w drzewa, jeśli nasza mapa skrótów jest bardzo mała - zamiast tego powinna najpierw zmienić rozmiar na większy.
Aby odpowiedzieć na pytanie dotyczące wzrostu wydajności, te optymalizacje zostały dodane w celu poprawy najgorszego przypadku. Spekuluję tylko, ale prawdopodobnie zauważysz zauważalną poprawę wydajności z powodu tych optymalizacji, jeśli twoja hashCode
funkcja nie była zbyt dobra.
String
, mają znacznie większą przestrzeń wartości niżint
kod skrótu, dlatego kolizje są nieuniknione. Teraz zależy to od rzeczywistych wartości, takich jak rzeczywiste wartości,String
które umieścisz na mapie, czy uzyskasz równomierny rozkład, czy nie. Zła dystrybucja może wynikać po prostu z pecha.java.lang.String
ma deterministyczny, niekryptograficznyhashCode
, więc atakujący mogą w trywialny sposób tworzyć odrębne ciągi znaków z kolidującymi hashCodes. Przed tą optymalizacją mogło to zdegradować operacje HashMap do O (n) -time, teraz po prostu degraduje je do O (log (n)).if the objects implement that interface, else the identity hash code.
szukałem tej innej części.MIN_TREEIFY_CAPACITY
. Czy to oznacza: „Kiedy wstawimy klucz, który ma być zaszyfrowany do zasobnika zawierającego już 8 (TREEIFY_THRESHOLD
) kluczy i jeśli jest już 64 (MIN_TREEIFY_CAPACITY
) kluczyHashMap
, połączona lista tego zasobnika jest konwertowana na zrównoważone drzewo”.Mówiąc prościej (o ile mógłbym prościej) + więcej szczegółów.
Te właściwości zależą od wielu wewnętrznych rzeczy, które byłoby bardzo fajne do zrozumienia - przed przejściem do nich bezpośrednio.
TREEIFY_THRESHOLD -> kiedy pojedyncze wiadro to osiągnie (a całkowita liczba przekroczy
MIN_TREEIFY_CAPACITY
), jest przekształcane w idealnie zrównoważony czerwono-czarny węzeł drzewa . Czemu? Ze względu na szybkość wyszukiwania. Pomyśl o tym w inny sposób:Trochę wstępu do następnego tematu. Dlaczego liczba pojemników / wiader jest zawsze potęgą dwóch ? Co najmniej z dwóch powodów: operacja szybsza niż modulo i modulo na liczbach ujemnych będzie ujemna. Nie możesz umieścić wpisu w „negatywnym” segmencie:
int arrayIndex = hashCode % buckets; // will be negative buckets[arrayIndex] = Entry; // obviously will fail
Zamiast tego zamiast modulo użyto fajnej sztuczki:
(n - 1) & hash // n is the number of bins, hash - is the hash function of the key
To jest semantycznie to samo, co operacja modulo. Zachowa niższe bity. Ma to interesujące konsekwencje, gdy:
Map<String, String> map = new HashMap<>();
Tutaj do gry wkracza mnożenie wiader. W pewnych warunkach ( dokładne wyjaśnienie wymagałoby dużo czasu ), rozmiary wiader są dwukrotnie większe. Czemu? Kiedy kubełki są podwojone, pojawia się jeszcze jeden bit .
W związku z tym proces ten nazywa się ponownym haszowaniem. To może być powolne. To znaczy (dla ludzi, którym zależy), ponieważ HashMap jest „żartowany” jako: szybko, szybko, szybko, wolno . Istnieją inne implementacje - wyszukiwanie pauzy hashmap ...
Teraz UNTREEIFY_THRESHOLD wchodzi do gry po ponownym haszowaniu. W tym momencie niektóre wpisy mogą przenieść się z tego kosza do innych (dodają jeszcze jeden bit do
(n-1)&hash
obliczenia - i jako takie mogą przenieść się do innych segmentów) i może to osiągnąćUNTREEIFY_THRESHOLD
. W tym momencie nie opłaca się trzymać kosza jakored-black tree node
, aleLinkedList
zamiast tego, jakMIN_TREEIFY_CAPACITY to minimalna liczba zasobników przed przekształceniem określonego zasobnika w drzewo.
źródło
TreeNode
to alternatywny sposób przechowywania wpisów należących do pojedynczego pojemnika plikuHashMap
. W starszych implementacjach wpisy pojemnika były przechowywane na połączonej liście. W Javie 8, jeśli liczba wpisów w koszu przekroczyła próg (TREEIFY_THRESHOLD
), są one przechowywane w strukturze drzewa zamiast oryginalnej połączonej listy. To jest optymalizacja.Od realizacji:
/* * Implementation notes. * * This map usually acts as a binned (bucketed) hash table, but * when bins get too large, they are transformed into bins of * TreeNodes, each structured similarly to those in * java.util.TreeMap. Most methods try to use normal bins, but * relay to TreeNode methods when applicable (simply by checking * instanceof a node). Bins of TreeNodes may be traversed and * used like any others, but additionally support faster lookup * when overpopulated. However, since the vast majority of bins in * normal use are not overpopulated, checking for existence of * tree bins may be delayed in the course of table methods.
źródło
TREEIFY_THRESHOLD
ORAZ łączna liczba pojemników wynosi co najmniejMIN_TREEIFY_CAPACITY
. Próbowałem to ukryć w mojej odpowiedzi ...Musisz to sobie wyobrazić: powiedzmy, że istnieje klucz klasy z nadpisaną tylko funkcją hashCode (), aby zawsze zwracała tę samą wartość
public class Key implements Comparable<Key>{ private String name; public Key (String name){ this.name = name; } @Override public int hashCode(){ return 1; } public String keyName(){ return this.name; } public int compareTo(Key key){ //returns a +ve or -ve integer } }
a potem gdzie indziej wstawiam 9 wpisów do HashMap ze wszystkimi kluczami będącymi instancjami tej klasy. na przykład
Map<Key, String> map = new HashMap<>(); Key key1 = new Key("key1"); map.put(key1, "one"); Key key2 = new Key("key2"); map.put(key2, "two"); Key key3 = new Key("key3"); map.put(key3, "three"); Key key4 = new Key("key4"); map.put(key4, "four"); Key key5 = new Key("key5"); map.put(key5, "five"); Key key6 = new Key("key6"); map.put(key6, "six"); Key key7 = new Key("key7"); map.put(key7, "seven"); Key key8 = new Key("key8"); map.put(key8, "eight"); //Since hascode is same, all entries will land into same bucket, lets call it bucket 1. upto here all entries in bucket 1 will be arranged in LinkedList structure e.g. key1 -> key2-> key3 -> ...so on. but when I insert one more entry Key key9 = new Key("key9"); map.put(key9, "nine"); threshold value of 8 will be reached and it will rearrange bucket1 entires into Tree (red-black) structure, replacing old linked list. e.g. key1 / \ key2 key3 / \ / \
Przechodzenie po drzewie jest szybsze {O (log n)} niż LinkedList {O (n)}, a gdy n rośnie, różnica staje się bardziej znacząca.
źródło
compareTo
fromComparable
.identityHashCode
to kolejny mechanizm, którego używa.Key
się nie wdrożyComparable
,identityHashCode
zostanie wykorzystany :)Zmiana w implementacji HashMap została dodana wraz z JEP-180 . Celem było:
Jednak czysta wydajność to nie jedyny zysk. Zapobiegnie to również atakowi HashDoS w przypadku użycia mapy skrótów do przechowywania danych wejściowych użytkownika, ponieważ czerwono-czarne drzewo używane do przechowywania danych w zasobniku ma najgorszą złożoność wstawiania w O (log n). Drzewo jest używane po spełnieniu określonych kryteriów - patrz odpowiedź Eugene'a .
źródło
Aby zrozumieć wewnętrzną implementację hashmap, musisz zrozumieć hashowanie. Haszowanie w najprostszej formie to sposób na przypisanie unikalnego kodu do dowolnej zmiennej / obiektu po zastosowaniu dowolnej formuły / algorytmu do jej właściwości.
Prawdziwa funkcja skrótu musi przestrzegać tej reguły -
„Funkcja skrótu powinna zwracać ten sam kod skrótu za każdym razem, gdy jest stosowana do tych samych lub równych obiektów. Innymi słowy, dwa równe obiekty muszą konsekwentnie generować ten sam kod skrótu ”.
źródło