Hash Tablosu Nedir?
İngilizce: Hash Table
Yayın: · Son güncelleme:
Hash Tablosu Nedir? Kısaca
Hash tablosu, verileri anahtar-değer çiftleri olarak saklayan ve bir hash fonksiyonu yardımıyla aranan değere ortalamada sabit sürede ulaşmayı sağlayan veri yapısıdır. Python'daki dict ve JavaScript'teki Map bu mantıkla çalışır.
Hash tablosu nedir?
Hash tablosu, bir anahtarı kullanarak ilgili değeri çok hızlı bulmayı sağlayan veri yapısıdır. "TC kimlik numarası" ile kişi bilgisini, "ürün kodu" ile fiyatı tutmak buna örnektir. İngilizcede hash table ya da hash map olarak geçer. Pek çok dilde sözlük yapısının arkasında bu tablo çalışır.
Nasıl çalışır?
Tablonun içinde numaralı kutulardan oluşan bir dizi vardır. Bir anahtar eklendiğinde, hash fonksiyonu bu anahtarı bir sayıya dönüştürür. Bu sayı, değerin hangi kutuya konacağını belirler. Arama yapılırken aynı fonksiyon yeniden çalışır ve doğrudan doğru kutuya gidilir.
Varsayımsal bir örnek düşünün. 1.000 ürünlük bir katalogda "TSH-42" kodlu tişörtün fiyatını arıyorsunuz. Liste olsaydı ürünleri tek tek kontrol etmeniz gerekirdi. Hash tablosunda ise fonksiyon "TSH-42" anahtarını örneğin 317 numaralı kutuya eşler ve fiyat tek adımda bulunur. Katalog bir milyon ürüne çıksa bile arama süresi ortalamada değişmez.
Çakışma nedir?
Kutu sayısı sınırlı olduğu için iki farklı anahtar bazen aynı kutuya düşer. Buna çakışma denir. Bir çözüm, aynı kutudaki değerleri küçük bir listede tutmaktır. Diğer yaygın çözüm ise boş bir sonraki kutuyu bulup değeri oraya yerleştirmektir.
Nelere dikkat etmeli?
Tablo çok dolarsa çakışmalar artar ve hız düşer. Bu yüzden diller, doluluk belli bir oranı aşınca tabloyu otomatik olarak büyütür. Anahtar olarak değişmeyen değerler kullanın; Python'da liste anahtar olamaz ama demet olabilir. Sıralı çıktı gerekiyorsa, hash tablosu yerine ağaç tabanlı bir yapı tercih edin.
Sıkça Sorulan Sorular
Hash tablosunda çakışma nedir?
İki farklı anahtarın hash fonksiyonundan aynı konumu almasıdır. Bu durumda değerler aynı konumda küçük bir listede tutulur ya da boş bir sonraki konuma yerleştirilir.
Hash tablosu sıralı mıdır?
Klasik hash tablosu sıra garantisi vermez. Bazı diller, örneğin güncel Python sürümlerindeki dict, ekleme sırasını korur ama bu değere göre sıralama anlamına gelmez.