Was genau ist Bucket in hashmap?
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. Kann ich also sagen, dass Bucket ein Array mit einer Kapazität von 16 ist, die Hashcodes speichern und auf welchen verknüpften Listen ihr Startzeiger steht?
Ich weiß, wie eine hashmap intern funktioniert, wollte nur wissen, was genau ein Eimer in Bezug auf Datenstrukturen ist.
4 Antworten
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.
Aus den Implementierungshinweisen in Java 8:
%Vor%
Buckets sind im Grunde eine Datenstruktur, die im Paging-Algorithmus des Betriebssystems verwendet wird. In einer sehr Laiensprache zu sein.
Die Objekte, die einen bestimmten Hashcode darstellen, werden in diesem Bucket gespeichert. (Grundsätzlich können Sie den Header der verknüpften Listendatenstruktur als den Hashcode-Wert betrachten, der in den Bucket-Begriffen dargestellt wird)
Die Referenzen des Objekts werden 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.
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 Buckets in HashMap aussehen:
%Vor%Tags und Links java hashmap hashcode linked-list bucket