Hash tablosu nasıl çalışır?

Bir hash tablosu (hash table), bir ilişkilendirilmiş dizi (associative array) uygulayan bir veri yapısıdır.

Çalışma prensibi:

1. Hashleme. Her anahtar (key) için, bir hash fonksiyonu (hash function) kullanılarak bir hash kodu (hash code) hesaplanır. Hash kodu, tam sayı türündedir.
2. İndeksleme. Hash kodu, iç yapının (örneğin, hash tablosunun) dizisinde (array) bir indeks (index) belirlemek için kullanılır. Genellikle, indeks hash_code % dizi_uzunluğu şeklinde hesaplanır.
3. Depolama. Bulunan indeks üzerinde, anahtarla ilişkili değer (value) saklanır.

Sorunlar ve çözümler:

• Çakışmalar. Farklı anahtarlar aynı hash kodunu üretebilir ve dolayısıyla aynı dizin (index) üzerinde olabilir. Buna çakışma denir.
  • Çakışma çözme yöntemleri:
    • Bağlantı yöntemi (Separate Chaining): Her dizide, "anahtar-değer" çiftlerinin listesi (liste, vektör, vb.) saklanır. Çakışma durumunda, yeni çift bu listeye eklenir. Dizin araması sırasında, ilgili liste taranarak istenen anahtar bulunur.
    • Açık adresleme (Open Addressing): Çakışma durumunda, belirli bir kurala göre (sondalama) dizide başka boş hücre aranır.
      • Doğrusal sondalama (Linear Probing): index + 1, index + 2, vb. hücreler ardışık olarak, dizinin boyutuna göre mod alınarak kontrol edilir.
      • Kare sondalama (Quadratic Probing): index + 1^2, index + 2^2, vb. hücreler, dizinin boyutuna göre mod alınarak kontrol edilir.
      • Çift hashleme (Double Hashing): İkinci bir hash fonksiyonu kullanılarak adım (step) belirlenir.

Avantajlar:

• Ortalama olarak, ekleme, silme ve arama işlemleri O(1) karmaşıklıkla gerçekleştirilir.

Dezavantajlar:

• En kötü durumda (örneğin, çok sayıda çakışma veya kötü hash fonksiyonu kullanımıyla), işlemlerin karmaşıklığı O(n) olabilir, burada n, eleman sayısıdır.
• Ek hafıza gerektirir (örneğin, bağlantı listeleri veya açık adresleme için ek alan).