Was genau ist Eimer in hashmap?

Question

Kürzlich, in einem Interview wurde ich gefragt, was genau ist ein Eimer in hashmap? Ob es ein Array oder eine Arraylist ist oder was?

Ich war verwirrt. Ich weiß, hashmaps werden von Arrays unterstützt. Also kann ich sagen, dass Bucket ein Array mit einer Kapazität von 16 ist, die Hash-Codes speichern und zu denen verknüpfte Listen ihren Startzeiger haben?

Ich weiß, wie eine hashmap intern funktioniert, wollte nur wissen, was genau ist ein Eimer in Bezug auf Datenstrukturen.

Answer 1

Nein, ein Bucket ist jedes Element in dem Array, auf das Sie sich beziehen. In früheren Java-Versionen enthielt jeder Bucket eine verknüpfte Liste von Map-Einträgen. In neuen Java-Versionen enthält jeder Bucket entweder eine Baumstruktur von Einträgen oder eine verknüpfte Liste von Einträgen.

Von den Implementierungshinweise in 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

Ich hoffe, dies kann Ihnen helfen, die Implementierung von Hash-Karte gut zu verstehen.

Answer 3

Buckets sind grundsätzlich eine Datenstruktur, die im Paging-Algorithmus des Betriebssystems verwendet wird. In einer sehr Laiensprache zu sein.

Die Objekte einen bestimmten Hash-Code darstellen, werden in diesem Eimer gespeichert werden. (Im Grunde kann man den Kopf der verknüpften Listendatenstruktur betrachtet den Hash-Code-Wert zu sein, die in den Bedingungen der Schaufel dargestellt ist)

Die Referenzen des Objekts wird in der Linkliste gespeichert, deren Header den Wert des Hashcodes darstellt.

Die JVM erstellt sie und die Größe hängt von dem Speicher ab, der von der JVM zugewiesen wird.

Answer 4

Buckets genau ist ein Array von Knoten. Ein einzelner Bucket ist also eine Instanz der Klasse java.util.HashMap.Node. Jeder Knoten ist eine Datenstruktur ähnlich LinkedList oder kann wie eine TreeMap sein (seit Java 8), HashMap entscheidet selbst, was für die Leistung besser ist - Bewahren Sie Buckets als LinkedList oder TreeMap auf. TreeMap wird nur dann ausgewählt, wenn die HashCode() Funktion schlecht designed ist, wenn viele Einträge in einem einzelnen Bucket platziert werden. Sehen Sie, wie Eimer aussehen wie in 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;