Einfache Hashtabelle mit Vektor

Question

Wie ich richtig verstanden habe, berechnet das Implementieren der Hashtabelle den Index basierend auf der eingegebenen Zeichenfolge und gibt ihn direkt zurück, was es zu einem einfachen Schlüsselwertspeicher macht.

So einfach Hash-Funktion so etwas wie

int hash(string name){ 

    int index = 0; 
    int hash = 0; 
    for (int i = 0; i < name.length() ;i++){ 
     hash += (int)name[i]; 
    } 
    index = sizeOfArray % hash; 
} 

SizeOfArray ist Array von Zeigern mit vordefinierten Größe aussehen könnte. Wenn dieser Index nicht existiert, wird er erstellt. Aber wie implementiere ich es mit Vektoren?

Vektor hat keine vordefinierte Größe. An sie wachsen automatisch. Wenn also sizeOfArray% hash aufgerufen wird, ändert sich jeder Vektor.

Was ist Logik dahinter hat Tabellen? Was ist die beste Methode, um den Index selbst mit wachsendem Vektor/Array zu berechnen?

Answer 1

Sie können eine vector<list<string>> als zugrunde liegende Datenstruktur für die Hash-Tabelle verwenden.
Auch die Indexberechnung ist falsch. anstelle von sizeOfArray % hash sollte es umgekehrt sein.

vector<list<string>> hash_table; 
const size_t hash_table_size = 100; 
hash_table.resize(hash_table_size); 

int hash(string name){ 
    int index = 0; 
    int hash = 0; 
    for (int i = 0; i < name.length() ;i++){ 
     hash += (int)name[i]; 
    } 

    index = hash % hash_table.size(); 
    hash_table[index].push_back(name); 
}