Czym dokładnie jest wiadro w hashmapie?

Question

Niedawno w wywiadzie zapytano mnie, czym właściwie jest wiadro w hashmapie? Czy jest to tablica, lista tablicowa czy co?

Byłem zdezorientowany. Wiem, że hashmapy są wspierane przez tablice. Więc czy mogę powiedzieć, że bucket to tablica o pojemności 16 w początkowym zapisie kodów hash i do której listy połączeń mają swój wskaźnik początkowy?

Wiem, jak działa wewnętrzna haczyk, po prostu chciałem wiedzieć, co dokładnie jest wiadrem pod względem struktur danych.

Answer 1

Nie, wiadro to każdy element w tablicy, do której się odnosisz. We wcześniejszych wersjach Javy każda z nich zawierała powiązaną listę pozycji mapy. W nowych wersjach Java każda z nich zawiera albo strukturę drzewiastą wpisów, albo połączoną listę wpisów.

Od notach wdrożeniowych w Java 8:

/* 
* 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 2

Mam nadzieję, że to może pomóc zrozumieć realizację hash mapie dobrze.

Answer 3

Wiadra są po prostu strukturą danych, która jest używana w algorytmie Paging w systemie operacyjnym. Być w języku bardzo Laymans.

Obiekty reprezentujące konkretną hashcode jest przechowywany w tym segmencie. (W zasadzie można rozważyć nagłówek połączonej strukturze lista danych, aby mieć wartość hashcode, który jest reprezentowany w kategoriach wiadrze)

odniesień obiektu jest przechowywany na liście linków, których nagłówek reprezentuje wartość Hashcode.

JVM tworzy je, a rozmiar zależy od pamięci przydzielonej przez JVM.

Answer 4

Łyżki dokładnie to tablica węzłów. Tak więc pojedyncze wiadro jest instancją klasy java.util.HashMap.Node. Każdy węzeł jest strukturą danych podobną do LinkedList lub może być jak TreeMap (od wersji Java 8), HashMap sam decyduje, co jest lepsze dla wydajności - zachowaj segmenty jako LinkedList lub TreeMap. TreeMap zostanie wybrany tylko w przypadku źle zaprojektowanej funkcji hashCode(), gdy wiele wpisów zostanie umieszczonych w pojedynczym wiadrze. Zobacz jak wiadra wyglądać w HashMap:

/** 
    * 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;