unordered_map konteynerinde bir hash tablosu nasıl yapılandırılmıştır?

C++'ta unordered_map, bir hash tablosu olarak uygulanır.

Çalışma prensibi:

1. Hashleme: Anahtar, bir hash fonksiyonu kullanılarak tam sayıya — hash koduna — dönüştürülür.
2. İndeksleme: Hash kodu, bir dizi gösterici veya listede indeks (kova veya bucket) belirlemek için kullanılır.
3. Depolama: Her kovada anahtar-değer çiftleri saklanır.

Özellikler:

• Kovalar: Hash tablosu, bir kova dizisinden oluşur. Kovaların sayısı, belirli bir yük oranına ulaşıldığında dinamik olarak değiştirilebilir (rehashing).
• Çakışmalar: Farklı anahtarlar aynı hash kodunu verebilir. Buna çakışma denir. Çakışmaları çözmek için unordered_map, ** zincirleme (chaining) ** yöntemini kullanır: Aynı hash'e sahip öğeler, ilgili kovada bağlı listeye (veya başka bir veri yapısına) eklenir.
• Hash fonksiyonu ve karşılaştırma fonksiyonu: Doğru çalışması için iki şeye ihtiyaç vardır:
  • Anahtarları kovalar arasında düzgün dağıtan iyi bir hash fonksiyonu, çakışmaları en aza indirir.
  • Aynı hash koduna sahip anahtarları ayırt etmek için eşitlik fonksiyonu (==).
• Performans: Ortalama olarak, ekleme, silme ve arama işlemleri O(1) zaman karmaşıklığına sahiptir. En kötü durumda (örneğin, çok sayıda çakışma veya kötü seçilmiş bir hash fonksiyonu ile) performans O(n)’ye düşebilir, burada n öğe sayısıdır.

Basitçe yapı örneği:

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Bağlı liste için
};

struct Bucket {
  Node* head; // Listenin başlangıcını gösterir
};

Bucket* buckets; // Kovalar dizisi
size_t num_buckets;

Öğe ekleme süreci:

1. Anahtarın hash kodu hesaplanır.
2. Kovanın indeksi belirlenir: bucket_index = hash(key) % num_buckets.
3. Anahtar-değer çifti, bu kovadaki listeye eklenir. Eğer anahtar zaten varsa, değer güncellenir.

Öğe arama süreci:

1. Anahtarın hash kodu hesaplanır.
2. Kovanın indeksi belirlenir.
3. Bu kovadaki liste taranır, anahtarlar == operatörü kullanılarak karşılaştırılır.

Rehashing, öğe sayısı ile kova sayısı belirli bir eşiği (yük faktörü) aştığında gerçekleşir. Rehashing sırasında, daha büyük yeni bir kova dizisi oluşturulur ve eski kovaların tüm öğeleri yeniden hash edilerek yeni dizilere taşınır.