question Hashmap nasıl çalışır?

1. // @author kenan | 28 Kasım 2017

   Basit düşünelim.

   Bir dizimiz var. Bu dizi içine değerler ekleyeceğiz. Mesela 20 uzunluğunda bir string dizisi var. İçine isimleri eklemeyi düşünüyoruz. Nasıl bir yapıyla koyarız. Sıradan tek tek eklemek bir yol. 1-kenan 2-ali 3-erkanerkisi 4-mehmet. Bunu yaptığımız zaman direk olarak bir dizi kullanmış oluyoruz. İstediğimiz ismi dizi içinde aramanın maliyeti bildiğimiz gibi O(n). Dizinin büyüklüğüne eşit. Şimdi öyle bir denge kurmalıyız ki tek bir işlemle erişebilelim, yani maliyet O(1) olursa zaten ulaşabileceğimiz en performanslı yapı olur. Bu örneği bilerek basit veriyorum ki hem benim anlatmam açısından kolay olsun, hem de zor nasıl bir örnek verebilirim pek kestiremiyorum.

   Elimizdeki isimlerin uzunluklarını alsak ve index olarak uzunlukları kullansak nasıl olur.

   dizi[4] = “kenan”;
   dizi[2] = “ali”;
   dizi[5] = “mehmet”;
   dizi[10] = “erkanerkisi”;

   Yeni bir fonksiyon yazalım, adı M olsun.

   int M(String name) { return name.length – 1; }
   dizi[M(“kenan”)] = “kenan erarslan”;
   dizi[M(“ali”)] = “ali erarslan”;
   dizi[M(“mehmet”)] = “mehmet aydin”;
   dizi[M(“erkanerkisi”)] = “akif erkan erkisi “;

   Böyle bir fonksiyonla kişileri indexlerine yerleştirmiş oluruz. Sonra bir kişinin değerini çekmek istediğimiz zaman nasıl kullanabiliriz?

   System.out.print(dizi[M(“erkanerkisi”)]);

   Şu anda maliyetimiz bir string’in uzunluğunu bulmak kadar oldu. O konu ayrı bir sorun 🙂 detaylarına girmeyeceğim. Sadece pascal/php gibi dillerde zaten bu bilgi bir byte içinde saklanıyor, yani maliyeti O(1). Dizi içinden çekmemiz de O(1). Dizinin içine yerleştirmemiz de O(1). Şu an yapabileceğimiz en hızlı veri yapısını yapmış oluyoruz.

   Peki sıkıntısı nedir. Buradan da anlayacağımız üzere. “kenan” yerine “kemal” gelseydi de sonuç 5 çıkacaktı ve eklemek istediğim zaman “collision(çarpışma)” oluşacaktı. Yani iki değerin aynı sonucu çıkarması. Genel olarak herşeye uygun bir map fonksiyon yok. Yani teorik olarak yok. Sizin elinizdeki verilere göre fonksiyon oluşturmanız gerekebilir. Ya da kullandığınız programlama dilinin kendiliğinden verdiği bazı algoritmalar olabilir. Java yanlış hatırlamıyorsam direk hafızadaki adresini veriyor. Bu da collisiona yakalanmamayı sağlar. Bu durumda da elinizdeki dizinin yüzde olarak kaçını doldurduğunuz sorusuna yol açabilir. Yani fonksiyonunuzun size verdiği değer aralığı 0-1000 arasında çıkarsa 1000 lik bir dizi tanımlananız gerektiği anlamına gelir. Gereksiz yer kaplayabilirsiniz. Ama her zaman için ya işlemci gücünden ya da yerden kaybetmeniz gerektiği konusunda bilinçli olmak lazım. Hashmap yerine ağaç (tree) kullanılabilir, orda da maliyet O(1) olmaz. Yer az olur. Kısacası hangisiniden ödün vereceğini planlamak lazım.

   Benim anlatacaklarım bu kadar 🙂

// Comments are closed.