HashMap utilizza LinkedList internamente

Question

public V get(Object key) { 
if (key == null) 
    return getForNullKey(); 
    int hash = hash(key.hashCode()); 
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
     e != null; 
     e = e.next) { 
     Object k; 
     if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
      return e.value; 
    } 
    return null; 
} 

Quello che sapevo è, se si vuole ottenere un oggetto da HashMap, prima di tutto cerca il secchio hash basato sul codice hash/valore di hash e quindi scorre la LinkedList in quel hashbucket (supponiamo gli oggetti diff hanno lo stesso codice hash, quindi nello stesso bucket hash).

Ma dopo aver guardato il codice di cui sopra, non sono in grado di capire quando esegue un'iterazione LinekedList (e dove è il LinkedList)

Answer 1

La benna è la lista collegata, in modo efficace. L'array table è un array di elementi Entry e ogni Entry è un elenco collegato, in cui ogni voce conosce il successivo nell'elenco, fino a quando non si raggiunge la fine quando il riferimento next è nullo. Il ciclo for che hai mostrato scorre sull'elenco collegato.

Non è un LinkedList come in un java.util.LinkedList - è un'implementazione separata (più semplice) solo per la mappa.

Answer 2

Utilizza la lista collegata, ma non la classe java.util.LinkedList.

Fondamentalmente e.next è qualcosa che stai cercando. Ogni voce ha un riferimento alla prossima voce nel bucket: si tratta di un'implementazione di elenchi collegati.

Answer 3

e.next è quello che stai cercando. Ogni voce ha un riferimento alla prossima voce nel bucket; è un'implementazione della lista collegata.