Hash tablosunun çalışma prensibi nedir?

Hash tablosu (veya ilişkisel dizi), "anahtar-değer" çiftlerini saklar. Çalışma prensibi, anahtarı sayısal bir indekse (hash) dönüştüren bir hash fonksiyonunun kullanılmasına dayanır ve bu indeks, değerin depolandığı yeri (sepet) gösterir.

Adımlar:

Hash Hesaplama: Belirli bir anahtar için hash hesaplanır.

<?php
$key = "example";
$hash = crc32($key); // Basit bir hash fonksiyonu örneği

İndeks Belirleme: Hash, genellikle dizinin boyutunun modülü kullanılarak dizin haline getirilir.
```
<?php
$arraySize = 10;
$index = $hash % $arraySize;
```
Sepete Erişim: Hesaplanan indeks kullanılarak dizideki ilgili sepete erişilir.
Çakışma Çözümü: Farklı anahtarlar aynı hash'e sahip olabilir (çakışma), bu durumda sepet birden fazla "anahtar-değer" çifti içerebilir. Çakışmaları çözmek için farklı yöntemler kullanılır:
- Bağlantı Yöntemi (Separate Chaining): Her sepette, hash'leri eşleşen "anahtar-değer" çiftlerinin listesi (örneğin bağlı liste) saklanır.
- Açık Adresleme (Open Addressing): Çakışma durumunda, belirli bir kurala göre (doğrusal, kare, çift hash) boş bir hücreyi tekrar arama yapılır.

İşlemler:

Ekleme: Anahtarın hash'i hesaplanır, indeks belirlenir ve "anahtar-değer" çifti ilgili sepete yerleştirilir. Çakışma durumunda, listeye eklenir (bağlantı) veya boş bir yer aranır (açık adresleme).
Arama: Anahtarın hash'i hesaplanır, indeks belirlenir. İlgili sepette, anahtar kullanılarak değer aranır. Bağlantı yönteminde liste elemanları taranır; açık adreslemede ise sıralı arama yapılır.
Silme: Anahtarın hash'i hesaplanır, indeks belirlenir. İlgili sepette, anahtar kullanılarak çift bulunur ve silinir.

Avantajlar:

Öğelere hızlı erişim (ortalama O(1)).
Belleğin verimli kullanımı.

Dezavantajlar:

Çok sayıda çakışma varsa performans düşebilir.
Tablo boyutu, verimliliği korumak için ayarlama (rehashing) gerekebilir.