Vektör ile basit hash tablosu

Question

Doğru şekilde anlaşıldığı gibi, hash tablosu uygulayarak, giriş dizgisine dayalı olarak dizin hesaplanıyor ve basit bir anahtar - değer depolaması yapıyor.

Yani basit hash fonksiyonu SizeOfArray önceden tanımlanmış boyutu ile işaretçileri dizidir

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

gibi bir şey olabilir. Bu dizin mevcut değilse, onu oluşturur. Ama bunu nasıl vektörlerle uygularım?

Vektör önceden tanımlı bir boyuta sahip değil. Otomatik olarak büyürler. Böylece sizeOfArray% karma değerinin değişmesi her zaman değişecektir.

Mantığın ardındaki tablo nedir? Büyüyen vektör/dizi ile bile endeksi hesaplamak için en iyi yöntem nedir?

Answer 1

Hash tablosu için temel veri yapısı olarak vector<list<string>> kullanabilirsiniz.
Ayrıca, dizin hesaplaması yanlış var; sizeOfArray % hash yerine, diğer yol yuvarlak olmalıdır.

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