Che cos'è esattamente il bucket in hashmap?

Question

Recentemente, in un'intervista mi è stato chiesto, che cos'è esattamente un bucket in hashmap? Che si tratti di un array o di un arraylist o di cosa?

Mi sono confuso. So che le hashmap sono supportate da array. Quindi posso dire che bucket è un array con una capacità di 16 all'inizio che memorizza i codici hash e a quali liste collegate hanno il loro puntatore iniziale?

So come funziona internamente una hashmap, volevo solo sapere cos'è esattamente un bucket in termini di strutture dati.

Answer 1

No, un bucket è ogni elemento nell'array cui si fa riferimento. Nelle versioni precedenti di Java, ciascun bucket conteneva un elenco collegato di voci Mappa. Nelle nuove versioni di Java, ciascun bucket contiene una struttura ad albero di voci o un elenco di voci collegate.

Dalle note di implementazione 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

Spero che questo possa aiutare a capire l'attuazione della mappa di hash bene.

Answer 3

I bucket sono fondamentalmente una struttura di dati che viene utilizzata nell'algoritmo di paging del sistema operativo. Essere in una lingua molto Laymans.

Gli oggetti che rappresentano un particolare codice hash viene memorizzato in quel secchio. (In pratica si può considerare l'intestazione della struttura di elenco dati collegati come valore hashcode rappresentato nei termini del secchio)

I riferimenti dell'oggetto viene memorizzato nell'elenco dei collegamenti, la cui intestazione rappresenta il valore di Hashcode.

La JVM li crea e la dimensione, dipende dalla memoria allocata dalla JVM.

Answer 4

Benne esattamente è una matrice di nodi. Quindi single bucket è un'istanza di classe java.util.HashMap.Node. Ogni nodo è una struttura di dati simile a LinkedList, o potrebbe essere come una TreeMap (dal momento che Java 8), HashMap decide se stesso cosa è meglio per le prestazioni - mantenere i bucket come LinkedList o TreeMap. TreeMap verrà scelto solo in caso di funzione hashCode() mal progettata, quando molte voci verranno inserite in un singolo bucket. Vedere come secchi assomigliano 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;