Giriş
Hash table olarak da bilinen hash mapler, bilgisayar bilimlerinde key-value çiftlerini saklamak için kullanılan temel veri yapılarıdır. Verimli ekleme, silme ve arama işlemleri sunmaları onları çeşitli uygulamalarda vazgeçilmez kılar. Bu blog yazısında, hash maplerin ne olduğunu, temel özelliklerini ve Go ile basit bir implementasyonunu inceleyeceğiz.
Hash Map Nedir
Hash map, verileri hashing adı verilen bir teknik kullanarak düzenleyen bir veri yapısıdır. Hashing, key'lerin bir hash fonksiyonu aracılığıyla sayısal indekslere dönüştürülmesini içerir. Bu indeksler daha sonra bu keylere karşılık gelen valueları verimli bir şekilde saklamak ve gerektiğinde geri getirmek için kullanılır. Hash maplerin birincil avantajı, iyi bir hash fonksiyonu ve collisionların etkili şekilde çözüldüğü varsayıldığında, ekleme, silme ve arama işlemleri için ortalama olarak sabit zamanlı bir zaman karmaşıklığı (En iyi senaryoda O(1) denebilir.) sağlamalarıdır.
İsminizi 10.000 isim arasında bulmanız gerektiğini düşünün. İsminizi bulana kadar bu büyük isim dizisinde sırayla arama yapmanız gerekir. Tahmin edebileceğiniz gibi bu uzun zaman alacaktır. En kötü durumda, adınız listenin sonunda olacak veya hiç bulunmayacaktır, bu senaryoda zaman karmaşıklığı O(n)'dir. Ancak isimleri alfabetik olarak kovalara ayırdıysanız, isminizin ilk harfine karşılık gelen kovayı aramanız gerektiğini bilirdiniz. Artık isminizi nispeten sabit bir zaman karmaşıklığı ile elde edebilirsiniz, çünkü basitçe isminizi nerede arayacağınızı bilirsiniz. Elbette bu diziye yeni bir isim eklediğinizde de bu sınıflandırmayı göz önünde bulundurmalısınız.
Yukarıda "iyi hash fonksiyonu ve uygun collision yönetimi "nden bahsetmiştik. Bu terimleri senaryomuzu kullanarak açıklayalım. Hash fonksiyonu bize kullanışlı bir indeks sağlar. Senaryomuzda hash fonksiyonumuz basitçe ismimizin ilk harfini alır. Eğer isminiz "John" ise, isminizi "J" kovasında arayacaksınız. Normal olarak "Ama J ile başlayan başka isimler de olacaktır." diyebilirsiniz. İşte collision tam olarak budur. Eğer hash fonksiyonumuz farklı değerler için aynı indeksi üretiyorsa, birden fazla değeri tek bir indekse koymak zorundayız. Bu nedenle hashmap basit olarak tekil değerlerden oluşan bir array değildir, "linked-list"lerden oluşan bir arraydir. Bizim senaryomuzda her indekste sadece bir "isim" değeri değil, isim değerinin yanında bir sonraki isme bakan bir pointer da içeren bir node olmalıdır. Kendi hash map implementasyonumuzda bu konuyu daha iyi kavrayacağız.
Go ile Kendi Hash Map'imizi Nasıl Implemente Ederiz:
Bir hash mapin, Go ile basit bir implementasyonunu inceleyelim. Örneğimiz, key-value çiftlerinin eklenmesi, alınması ve silinmesi gibi temel işlevlere odaklanacaktır.
Senaryomuzda basitlik adına sadece isimlere yer vermiştik. Gerçek bir hashmap'te, key-value çiftlerine sahip olurduk. Ve görebileceğiniz üzere, bir indeksteki her node; bir key, bir value ve aynı indeksteki bir sonraki node'a bakan bir pointer içerecektir. Bunu uyguladığımızda hash tablosunun her bir indeksinde bir linked-list'e sahip oluruz.
type Node struct {
Key string
Value string
Next *Node
}
Ve işte basitçe Node pointerlarından oluşan bir array ve tablonun boyutunu temsil eden bir sayı içeren hash tablomuz.
type HashMap struct {
buckets []*Node
size int
}
Şimdi yeni bir hash map oluşturmak için bir fonksiyona ihtiyacımız var.
func NewHashMap(size int) *HashMap {
return &HashMap{
buckets: make([]*Node, size),
size: size,
}
}
Şimdi hash tablomuzda saklayacağımız her key-value çiftinin indeksini hesaplamak için bir hash fonksiyonuna ihtiyacımız var. Normalde collisionları en aza indirmeye yönelik bir hash algoritması kullanılmalıdır. Ancak basitliği korumak adına, key'in uzunluğunun hash map'in boyutuna bölünmesiyle elde edilen kalanı hash olarak alacağız.
func hashFunction(key string, size int) uint {
return uint(len(key) % size)
}
Şimdi HashMap'imizin "insert" metodu ile hash map'lerin yapısını daha iyi anlayacağız.
// Insert metodu parametre olarak basitçe key ve value alır
func (hm *HashMap) Insert(key string, value string) {
/* Burada hashFunction kullanarak key-value çiftimizi (node) koyacağımız indeksi
hesaplıyoruz. */
index := hashFunction(key, hm.size)
// Şimd key ve value ile node'umuzu oluşturuyoruz
node := &Node{Key: key, Value: value}
// Elde edilen indekste key-value çifti yoksa, yeni node'umuzu bu indekse yerleştiririz.
if hm.buckets[index] == nil {
hm.buckets[index] = node
} else {
/* Elde edilen indekste bir node varsa, bu bir collision olduğu anlamına gelir.
Panik yok, bu yüzden "node" "Next"i içerir. Bir sonraki node "nil" olana kadar
mevcut node'u sürekli olarak bir sonraki node'a set etmeliyiz. Bu, son durumda
mevcut node'dan sonra hiçbir node olmadığı anlamına gelir. */
current := hm.buckets[index]
for current.Next != nil {
current = current.Next
}
/* Artık mevcut node'un bir sonraki node'unu gönül rahatlığıyla yeni oluşturduğumuz
node'a set edebiliriz. */
current.Next = node
}
}
Şimdi bir "get" metodu oluşturalım:
func (hm *HashMap) Get(key string) string {
/* İstediğimiz değeri nerede aramamız gerektiğini bilmek için hashFunction ile indeksi
hesaplıyoruz. */
index := hashFunction(key, hm.size)
// Bu indeksteki ilk node'u alıyoruz ve bir değişkene atıyoruz.
current := hm.buckets[index]
for current != nil {
/* Aradığımız key'i sadece mevcut node'un key'i ile karşılaştıramayız. Çünkü öevcut
node aradığımız node olmayabilir, peki ya onun bir sonraki node'u, onun bir sonraki
node'unun bir sonraki node'u... Bu nedenle, mevcut node'un key'i bizim key'imizle
eşleşene kadar mevcut node'u sürekli olarak bir sonraki node'a set ederiz ve o
node'un değerini döndürürüz. */
if current.Key == key {
return current.Value
}
current = current.Next
}
/* Kod buraya ulaşırsa, key'imizle eşleşen bir node olmadığı anlamına gelir. Burada basitçe
boş bir string döndürüyoruz. (Gerçek bir hash map'te bu durum farklı bir şekilde ele
alınır.). */
return ""
}
Son metodumuz "delete" olacaktır.
func (hm *HashMap) Delete(key string) {
// Silmek istediğimiz değerin bulunduğu indeksi hashFunction'ı kullanarak hesaplıyoruz.
index := hashFunction(key, hm.size)
// Bu indeksteki ilk node'u alıyoruz ve bir değişkene atıyoruz.
current := hm.buckets[index]
// Önceki node'u takip edebilmek için bir pointer oluşturuyoruz.
var prev *Node
// Hesapladığımız indeksteki linked-list'i geziyoruz.
for current != nil {
// Güncel node'un key'i silinecek key ile eşleşiyorsa,
if current.Key == key {
// Önceki node'un nil olması, silinecek node'un ilk node olduğu anlamına gelir
if prev == nil {
/* Güncel node'u atlamak için linked-list'in ilk node'unu güncelliyoruz (bir
sonraki node'a set ederek). Bu durumda, artık güncel node'u silmiş oluruz. */
hm.buckets[index] = current.Next
} else {
/* Önceki node nil değilse, önceki node'un "next" pointerını güncelleyerek
güncel node'u atlıyoruz. Önceki node'un bir sonraki node'unu, güncel node'un
bir sonraki node'una set ettiğimizde, artık güncel node'a sahip olmayız.
Karmaşık görünebilir ama bir deneyin, anlayacaksınız :). */
prev.Next = current.Next
}
// Silme işleminden sonra metoddan çıkıyoruz.
return
}
/* Güncel node'un key'i bizim key'imizle eşleşmiyorsa, linked-list'teki bir sonraki
node'a geçeriz. */
prev = current
current = current.Next
}
HashMap'imizin Örnek Kullanımı
func main() {
// Boyutu 10 olan yeni bir hash map oluşturuyoruz:
myHashMap := NewHashMap(10)
// Insert metodu kullanımı:
myHashMap.Insert("john", "doe")
myHashMap.Insert("foo", "bar")
// Get metodu kullanımı:
value := myHashMap.Get("john")
fmt.Println("Value for key john:", value)
// Delete metodu kullanımı:
myHashMap.Delete("foo")
/* Eğer "foo" key'ine karşılık gelen değeri almaya çalışırsak boş bir string alırız. (get
metodunuzda uygun bir exception veya flag de döndürebilirdik) */
}
Hash Map'lerin Temel Özelliklerini Özetleyecek Olursak:
- Key-Value Saklama: Hash map'ler, verileri her bir key'in benzersiz olduğu ve belirli bir değerle ilişkilendirildiği key-value çiftleri halinde depolar.
- Hash Fonksiyonu: Bir hash fonksiyonu, key'leri hash tablosundaki indekslerle eşleştirerek değerlere hızlı erişimi kolaylaştırır.
- Collision Çözümleme: Birden fazla key aynı hash değerini ürettiğinde collision meydana gelir. Hash map'ler, collisionları etkili bir şekilde çözmek için zincirleme veya açık adresleme gibi collision çözümleme teknikleri kullanır.
- Dinamik Boyutlandırma: Birçok hash map implementasyonu, dengeli bir load-faktör'ü korumak için dinamik olarak yeniden boyutlandırılır ve öğe sayısı değiştikçe optimum performans sağlar.
- Verimli İşlemler: Hash map'ler, ekleme, silme ve arama gibi yaygın işlemler için ortalama olarak sabit zamanlı performans sunar.
Not: Normalde bir hash map, verimli bellek kullanımı için bir büyüme/küçülme (grow/shrink) implementasyonuna sahip olacaktır. Basitliği korumak adına bunu buraya dahil etmedik.
“Yazmak, geleceği görmektir.” Paul Valéry