Hash Tablosu

İngilizcesi: Hash Table
Türkçe karşılığı: karma tablo
Okunuşu: heş teybıl

Günlük kullanımda çoğunlukla İngilizcesi tercih edilir.

Güncellendi 30 Eylül 20262 dk okuma

Kısaca

Hash tablosu, anahtar-değer çiftlerini saklayan ve hash fonksiyonuyla herhangi bir anahtarın değerini ortalamada sabit sürede bulan bir veri yapısıdır.

Hash tablosu (hash table) nedir?

Hash tablosu, bir kullanıcı adının bir kullanıcı profiline eşlenmesi gibi anahtar-değer çiftleri halinde veri saklar. İçeride, çoğunlukla bucket (kova) adı verilen yuvalardan oluşan bir dizi tutar. Bir çift eklediğinizde bir hash fonksiyonu anahtarı bir sayıya dönüştürür; bu sayının dizi boyutuna göre modülü (ona bölündükten sonra kalan) çiftin hangi bucket'a gideceğine karar verir.

Daha sonra bir anahtarı aramak için tablo onu yeniden hash'ler ve her kaydı taramak yerine doğrudan doğru bucket'a atlar; bu yüzden arama, ekleme ve silme ortalamada O(1) sürer. Bazen iki farklı anahtar aynı bucket'a düşer; buna çakışma (collision) denir. Tablolar çakışmaları bucket başına küçük bir liste tutarak (chaining) ya da bir sonraki boş yuvayı arayarak (open addressing) ele alır ve bucket'lar kısa kalsın diye çok dolduklarında büyüyüp tüm kayıtları yeniden hash'ler. Nadir en kötü durumda, birçok anahtar çakıştığında tek bir işlem O(n)'e kadar düşebilir.

Bir kütüphane iyi bir benzetmedir: her rafı kontrol etmek yerine bir kitabın yer numarasını kullanarak doğrudan doğru yere yürürsünüz. Hash tabloları en yaygın kullanılan veri yapıları arasındadır; Python'ın dict ve set yapıları ile JavaScript'in Map ve Set yapıları bunların üzerine kuruludur. Önbelleklere, sayma ve tekilleştirmeye, veritabanlarındaki hash indekslerine ve derleyicilerin değişken adlarını izlemek için kullandığı sembol tablolarına güç verirler.

Hash tablosu, güvenlik amaçlı hash'leme ile aynı şey değildir. Hash tablosunun hızlı olan ve anahtarları eşit dağıtan bir hash fonksiyonuna ihtiyacı varken, parola saklama kasıtlı olarak yavaş ve tersine çevrilmesi zor bir kriptografik hash gerektirir. Hash tabloları ayrıca dengeli arama ağaçlarıyla karşılaştırılır: tam anahtarla aramalarda hash tablosu daha hızlıdır, ancak anahtarları sıralı tutmaz; bu yüzden A ile F arasındaki tüm adları bulmak gibi aralık sorguları için ağaç daha iyi bir seçimdir.

Bir bakışta

Hash doğrudan bucket'ı seçer, bu yüzden arama diğer kayıtları hiç taramaz. Çakışan anahtarlar aynı bucket'ın zincirini paylaşır.

Önemli noktalar

Hash tablosu, bir hash fonksiyonu kullanarak anahtarları değerlere eşler.
Arama, ekleme ve silme ortalamada O(1), en kötü durumda O(n)'dir.
Çakışma iki anahtarın aynı bucket'a eşlenmesidir; chaining ve open addressing bunu çözer.
Python'ın dict yapısı ve JavaScript'in Map yapısı hash tablolarıdır.
Hash tabloları anahtarları sıralı tutmaz, bu yüzden aralık sorguları için uygun değildir.

Örnek

Python dict ile kelimeleri saymakpython

# A dict is Python's built-in hash table
text = "the cat sat on the mat by the door"
counts = {}

for word in text.split():
    counts[word] = counts.get(word, 0) + 1  # lookup and insert: O(1) on average

print(counts["the"])    # 3
print("dog" in counts)  # False: membership checks are also O(1) on average

Sık sorulan sorular

Hash table ile hash map arasındaki fark nedir?

Çoğu bağlamda aynı şey anlamına gelirler: hash'leme üzerine kurulu bir anahtar-değer yapısı. Bazı diller bu adları belirli sınıflar için kullanır; örneğin Java'nın Hashtable ve HashMap sınıfları, iş parçacığı güvenliği gibi ayrıntılarda farklılaşır.

Hash tablosunda arama neden O(1)'dir?

Hash fonksiyonu bir anahtarın nereye ait olduğunu doğrudan hesaplar; böylece tablo her kaydı aramak yerine o bucket'a atlayabilir. Hash fonksiyonu anahtarları eşit dağıttığı ve tablo çok dolmadan büyüdüğü sürece bu ortalamada O(1) kalır.

Herhangi bir değer hash tablosu anahtarı olarak kullanılabilir mi?

Anahtarlar hash'lenebilir olmalı ve saklanırken değişmemelidir; çünkü değişen bir anahtar farklı bir bucket'a hash'lenir ve artık bulunamaz. Python'ın string'leri, sayıları ve hash'lenebilir değerlerden oluşan tuple'ları dict anahtarı olarak kabul edip listeleri kabul etmemesinin nedeni budur.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin