HashMap Nedir? Go ile Kendi HashMap'imizi Nasıl Implemente Ederiz?

Hash table olarak da bilinen HashMap'ler, 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, HashMplerin ne olduğunu, temel özelliklerini ve Go ile basit bir implementasyonunu inceleyeceğiz.

HashMap Nedir?

HashMap, 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. HashMap'lerin 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 HashMap'imizi Nasıl Implemente Ederiz?

Bir HashMap'in, 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'de, 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 HashMap 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 HashMap'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 HashMap'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) */
}

HashMap'lerin Temel Özellikleri

• Key-Value Saklama: HashMap'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. HashMap'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 HashMap 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: HashMap'ler, ekleme, silme ve arama gibi yaygın işlemler için ortalama olarak sabit zamanlı performans sunar.

Not: Normalde bir HashMap, 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.