HashMap Java 8 realizacja

Question

zgodnie z poniższym dokumencie link: Java HashMap Implementation

jestem zmieszany z realizacją HashMap (czy raczej rozszerzeniem w HashMap). Moje pytania to:

pierwsze

static final int TREEIFY_THRESHOLD = 8; 
static final int UNTREEIFY_THRESHOLD = 6; 
static final int MIN_TREEIFY_CAPACITY = 64; 

Dlaczego i jak stosować te stałe? Chciałbym podać kilka wyraźnych przykładów. W jaki sposób osiągają w ten sposób wzrost wydajności?

drugie

Jeśli pojawi się kod źródłowy HashMap w JDK, znajdziesz następujące statyczne klasy wewnętrzna:

static final class TreeNode<K, V> extends java.util.LinkedHashMap.Entry<K, V> { 
    HashMap.TreeNode<K, V> parent; 
    HashMap.TreeNode<K, V> left; 
    HashMap.TreeNode<K, V> right; 
    HashMap.TreeNode<K, V> prev; 
    boolean red; 

    TreeNode(int arg0, K arg1, V arg2, HashMap.Node<K, V> arg3) { 
     super(arg0, arg1, arg2, arg3); 
    } 

    final HashMap.TreeNode<K, V> root() { 
     HashMap.TreeNode arg0 = this; 

     while (true) { 
      HashMap.TreeNode arg1 = arg0.parent; 
      if (arg0.parent == null) { 
       return arg0; 
      } 

      arg0 = arg1; 
     } 
    } 
    //... 
} 

jaki sposób je wykorzystuje? Chcę tylko wyjaśnienia algorytmu.

Answer 1

HashMap zawiera pewną liczbę wiadrach. Używa ona hashCode, aby określić, do którego kubełka je włożyć. Dla uproszczenia wyobraź sobie to jako moduł.

Jeśli nasz hashcode jest 123456 i mamy 4 wiadra, 123456 % 4 = 0 więc element przechodzi w pierwszym wiadra, wiadro 1.

Jeśli nasza funkcja hashcode jest dobry, że zapewni równomierne rozprowadzenie więc wszystkie wiadra będą używane w jednakowy sposób. W takim przypadku w zasobniku używana jest lista połączona do przechowywania wartości.

Ale nie można polegać na ludziach, aby wdrożyć dobre funkcje skrótu. Ludzie często piszą słabe funkcje mieszające, które spowodują nierównomierną dystrybucję.

Mniej nawet ten rozkład jest, że im dalej od ruchu O (1) operacje i bliżej jesteśmy w kierunku O (n) operacji.

Wdrożenie Hashmap próbuje złagodzić tę sytuację poprzez organizowanie niektórych segmentów w drzewa zamiast list powiązanych, jeśli zasobniki stają się zbyt duże. Właśnie do tego służy TREEIFY_THRESHOLD = 8. Jeśli wiadro zawiera więcej niż osiem elementów, powinno stać się drzewem.

Drzewo jest najpierw posortowane według kodu skrótu. Jeśli kody skrótu są takie same, korzysta z metody compareTo z obiektu, jeśli obiekty implementują ten interfejs, inaczej kod skrótu tożsamości.

Jeśli wpisy zostaną usunięte z mapy, liczba wpisów w wiadrze może zmniejszyć się tak, że ta struktura drzewa nie jest już potrzebna. Właśnie do tego służy UNTREEIFY_THRESHOLD = 6. Jeśli liczba elementów w wiadrze spadnie poniżej sześciu, równie dobrze moglibyśmy powrócić do korzystania z połączonej listy.

Wreszcie jest MIN_TREEIFY_CAPACITY = 64.

Gdy mapa skrótu rośnie, automatycznie zmienia rozmiar, aby mieć więcej segmentów. Jeśli dysponujemy małą mapą skrótu, prawdopodobieństwo, że otrzymamy bardzo pełne segmenty, jest dość wysokie, ponieważ nie mamy wielu różnych segmentów, w których można umieszczać elementy. O wiele lepiej jest mieć większą mapę mieszania, z większą liczbą mniejszych zasobników. Ta stała zasadniczo mówi, żeby nie zaczynać tworzenia wiader w drzewa, jeśli nasza mapa mieszania jest bardzo mała - powinna najpierw zmienić rozmiar, by była większa.

---

Aby odpowiedzieć na pytanie o przyrost wydajności, te optymalizacje zostały dodane w celu poprawy sprawę najgorszy. Spekuluję tylko, ale prawdopodobnie zauważysz zauważalną poprawę wydajności z powodu tych optymalizacji, jeśli twoja funkcja hashCode nie była zbyt dobra.

---

Obrazy są moje (dzięki MSPaint). Wykorzystaj je, jak chcesz.

Answer 2

TreeNode to alternatywny sposób przechowywania wpisów należących do pojedynczego pojemnika z HashMap. W starszych implementacjach wpisy bin były przechowywane na połączonej liście. W języku Java 8, jeśli liczba wpisów w skrzynce przekroczyła próg (TREEIFY_THRESHOLD), są one przechowywane w strukturze drzewa zamiast w oryginalnej, połączonej liście. To jest optymalizacja.

Z 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. 

Answer 3

Trzeba by go wizualizować: mówią, że to jest klucz klasy tylko hashCode() funkcja przeważa zawsze powrócić 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, ja wkładając 9 wpisy 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 drzewa szybciej {o (log n)} niż LinkedList {O (n)}, jak n wzrasta różnica staje się coraz bardziej istotna.

Answer 4

Mówiąc prościej (o ile mogłem prościej) + trochę więcej szczegółów.

Te właściwości zależą od wielu wewnętrznych rzeczy, które byłyby bardzo fajne do zrozumienia - przed przejściem do nich bezpośrednio.

TREEIFY_THRESHOLD -> gdy pojedynczy wiadro osiąga ten (a łączna liczba przekracza MIN_TREEIFY_CAPACITY) został przekształcony w doskonale zrównoważony węzła czerwony/czarny drzewa. Czemu? Ze względu na szybkość wyszukiwania. Pomyśl o tym w inny sposób:

zajęłoby co najwyżej 32 krokach aby wyszukać wpis w wiadrze/bin z Integer.MAX_VALUE wpisów.

Niektóre wstęp do następnego tematu. Dlaczego liczba pojemników/wiaderek zawsze jest równa dwóm? Co najmniej dwa powody: szybsze niż działanie modulo i modulo na liczbach ujemnych będą ujemne. I nie można umieścić wejście do „negatywnej” Bucket:

int arrayIndex = hashCode % buckets; // will be negative 

buckets[arrayIndex] = Entry; // obviously will fail 

Zamiast Jest miły trik stosowany zamiast modulo:

(n - 1) & hash // n is the number of bins, hash - is the hash function of the key 

To semantycznie samo jak działanie modulo. Zachowa dolne bity. Ma to interesujący skutek, kiedy to zrobić:

Map<String, String> map = new HashMap<>(); 

W powyższym przypadku, decyzja gdzie idzie wpis jest podjęte na podstawie na ostatnim 4 bity tylko z was hashcode.

W tym miejscu pojawia się pomnożenie wiader. W pewnych warunkach (zajmie to dużo czasu, aby wyjaśnić w szczegółach ), wiadra mają podwójną wielkość. Czemu? Gdy kubełki mają podwójny rozmiar, pojawia się jeszcze jeden element:.

Masz 16 pojemników - ostatnie 4 bity hashcode decydują o miejscu wejścia. Podwajasz liczbę pojemników: 32 wiadra - 5 ostatnich bitów decyduje o miejscu wejścia.

Jako taki proces ten nazywany jest ponownym mieszaniem. To może się wydłużyć. To jest (dla ludzi, którzy się tym przejmują), ponieważ HashMap jest "żartowany" jako: szybki, szybki, szybki, slooow. Istnieją inne implementacje - wyszukaj pauseless HashMap ...

Teraz UNTREEIFY_THRESHOLD wchodzi w grę po ponownym mieszaja. W tym momencie niektóre wpisy mogą przejść z tych pojemników do innych (dodają jeszcze jeden bit do obliczeń (n-1)&hash - i jako taki ruch migrujący do innych łyżek) i może osiągnąć to UNTREEIFY_THRESHOLD. W tym momencie to nie opłaca się trzymać pojemnik jako red-black tree node, ale jako LinkedList Zamiast tego, jak

entry.next.next.... 

MIN_TREEIFY_CAPACITY jest minimalna ilość wiader przed pewną wiadro przekształca się w drzewo.

Answer 5

Zmiana w implementacji HashMap została dodana z JEP-180. Celem było:

Poprawa wydajności java.util.HashMap warunkach wysokiej hash-kolizji za pomocą wyważonych drzew zamiast listy wpisów związanych sklep map. Zaimplementuj to samo ulepszenie w klasie LinkedHashMap:

Jednak czysta wydajność nie jest jedynym zyskiem.Będzie również zapobiecHashDoS attack, w przypadku, gdy mapa mieszania jest używana do przechowywania danych wejściowych użytkownika, ponieważ red-black tree, który jest używany do przechowywania danych w wiadrze, ma najgorszy przypadek złożoności wstawiania w O (log n). Drzewo jest używane po spełnieniu określonych kryteriów - patrz Eugene's answer.