HashMap verwendet LinkedList intern

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; 
} 

Was I wusste, wenn Sie ein Objekt aus HashMap erhalten wollen, vor allem sucht er den Eimer Hash basierend auf hashcode/Hash-Wert und durchläuft dann die LinkedList in diesem hashbucket (annehmen die Diff-Objekte haben denselben Hash-Code, also im selben Hash-Bucket).

Aber nach oben Blick auf den Code, ich bin zu verstehen, nicht in der Lage, wenn es durch die LinekedList iteriert (und wo ist die LinkedList)

Answer 1

Der Eimer Liste der verbunden ist, effektiv. Das table Array ist ein Array von Entry Elementen, und jedes Entry ist eine verknüpfte Liste, in der jedem Eintrag der nächste in der Liste bekannt ist, bis Sie das Ende erreichen, wenn der next Verweis null ist. Die for Schleife, die Sie angezeigt haben, iteriert über die verknüpfte Liste.

Es ist kein LinkedList wie in einem java.util.LinkedList - es ist eine separate (einfachere) Implementierung nur für die Karte.

Answer 2

Es verwendet verknüpfte Liste, aber nicht java.util.LinkedList Klasse.

Grundsätzlich e.next ist etwas, was Sie suchen. Jeder Eintrag hat einen Verweis auf den nächsten Eintrag im Bucket - es handelt sich um eine Implementierung einer verknüpften Liste.

Answer 3

e.next ist was du suchst. Jeder Eintrag hat einen Verweis auf den nächsten Eintrag im Bucket. es ist eine verkettete Listenimplementierung.