2016-06-22 4 views
7

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?Che cos'è esattamente il bucket in hashmap?

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.

+1

è necessario leggere questo (http://stackoverflow.com/questions/6493605/how-does-a-java-hashmap-handle-different-objects-with -the-same-hash-code/6493946 # 6493946) – emotionlessbananas

+0

@JonnyHenly: volevo sapere esattamente cos'è un secchio? Nella domanda menzionata, è più di lavorare sull'hashcode e l'implementazione di hashmap. Quindi non considero la mia domanda un duplicato. Le domande potrebbero essere simili, ma la risposta che stanno cercando sono diverse. – dgupta3091

risposta

14

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. 
... 
+0

Quindi, quando diciamo che hashmap ha una capacità di 16 all'inizio, quindi in quel momento crea una matrice di 16 spazi e ha ogni elemento chiamato come un secchio. – dgupta3091

+0

@ dgupta3091 sì, sebbene nell'implementazione di Java 8 l'array sia creato pigramente (cioè solo quando la prima voce viene inserita in HashMap). – Eran

+0

@JonnyHenly Ho appena controllato l'implementazione in Java 8 e nessuno dei costruttori inizializza l'array. È solo inizializzato da 'resize()' (che sarà chiamato da 'put' se l'array è null) e' readObject (java.io.ObjectInputStream s) '(deserializzazione). – Eran

13

bucket

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

0

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.

0

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; 
Problemi correlati