Hashtable zugrunde liegenden Platzhalter?

Question

Ich versuche, die HashTable Datenstruktur zu verstehen. Ich verstehe, dass wir in HashTable zuerst HashFunction verwenden, um einen Schlüssel zu Hash-Code zu konvertieren und dann mit Modulo-Operator in Ganzzahl-Index zu konvertieren und die verwendet wird, um den Speicherort in HashTable zu erhalten, wo Daten platziert werden.

Auf einer hohen Ebene ist der Fluss so?

Key ->Hash Function ->Hash code ->Modulo operator ->integer index ->Store in HashTable

Da der Schlüssel auf der Grundlage des Index gespeichert wird, wie durch den Modulo-Operator emittieren, meine Zweifel, was die zugrundeliegende Datenstruktur Welches wird verwendet, um die tatsächlichen Daten zu halten? Ist es ein Array, kann auf Array mit Index zugegriffen werden.

Kann mir jemand helfen, das zu verstehen?

Answer 1

Obwohl es vollständig von der Implementierung abhängt, würde ich zustimmen, dass zugrunde liegende Datenstruktur Array mit verknüpften Liste sein würde, da Array bequem ist, Elemente zu niedrigen Kosten zugreifen, während verknüpfte Liste Hash-Kollisionen zu behandeln ist.

Hier Beispiel von Einzelheiten, wie es umgesetzt in java openjdk Hashtable
es Array erzeugt zunächst mit Anfangskapazität:

table = new Entry<?,?>[initialCapacity]; 

Es ist für Kapazitätsschwelle jedes Mal überprüft, wenn neue Element hinzugefügt wird. Wenn Grenzwert erreicht ist es führt Wiederkäuen und erstellt ein neues Array, das

doppelte Größe des alten Array ist

int newCapacity = (oldCapacity << 1) + 1; 
    if (newCapacity - MAX_ARRAY_SIZE > 0) { 
     if (oldCapacity == MAX_ARRAY_SIZE) 
      // Keep running with MAX_ARRAY_SIZE buckets 
      return; 
     newCapacity = MAX_ARRAY_SIZE; 
    } 
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; 

    modCount++; 
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); 
    table = newMap; 

Hashtable Entry bildet eine verbundene Liste. Es wird im Falle von Hash-Kollisionen verwendet, da der Index für zwei verschiedene Werte gleich wird und der erforderliche Wert über die verknüpfte Liste überprüft wird.

private static class Entry<K,V> implements Map.Entry<K,V> { 
    final int hash; 
    final K key; 
    V value; 
    Entry<K,V> next; 

Sie möchten other more simple Implementierungen von Hash-Tabellen für ein besseres Verständnis überprüfen.