Implementacja HashMap Java 8

Zgodnie z następującym dokumentem odsyłającym: Implementacja Java HashMap

Jestem zdezorientowany z implementacją HashMap(a raczej ulepszeniem HashMap). Moje zapytania to:

po pierwsze

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

Dlaczego i jak są używane te stałe? Chcę mieć na to jasne przykłady. Jak dzięki temu osiągają poprawę wydajności?

Po drugie

Jeśli zobaczysz kod źródłowy HashMapw JDK, znajdziesz następującą statyczną klasę wewnętrzną:

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;
        }
    }
    //...
}

Jak to jest używane? Chcę tylko wyjaśnienia algorytmu .

HashMapzawiera określoną liczbę zasobników. Używa hashCodedo 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 = 0wię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 = 8jest. 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 compareTometody, Comparablejeś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 = 6sł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 hashCodefunkcja nie była zbyt dobra.

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:

wyszukanie pozycji w zasobniku / koszu z pozycjami Integer.MAX_VALUE zajęłoby co najwyżej 32 kroki .

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

W powyższym przypadku decyzja o tym, gdzie trafia wpis, jest podejmowana na podstawie tylko ostatnich 4 bitów kodu hashcode.

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 .

Masz więc 16 segmentów - ostatnie 4 bity kodu skrótu decydują o tym, gdzie trafi wpis. Podwajasz wiadra: 32 wiadra - 5 ostatnich bitów decyduje, gdzie trafi wejście.

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)&hashobliczenia - 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 jako red-black tree node, ale LinkedListzamiast tego, jak

 entry.next.next....

MIN_TREEIFY_CAPACITY to minimalna liczba zasobników przed przekształceniem określonego zasobnika w drzewo.

TreeNodeto alternatywny sposób przechowywania wpisów należących do pojedynczego pojemnika pliku HashMap. 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.

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.

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

Popraw wydajność java.util.HashMap w warunkach dużej liczby kolizji skrótów, używając zrównoważonych drzew zamiast połączonych list do przechowywania wpisów map. Zaimplementuj to samo ulepszenie w klasie LinkedHashMap

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 .

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