yazılım geyiklemeleri

Klasik programlamanın temel taşlarından biri array tipidir. Basitçe;

int[] pi = new int[] { 3, 1, 4, 1, 5, 9 , 2, 6, 5, 4 };

şeklinde tanımlanan bir arrayde elemanlara index (elemanın numarası) değerleri ile ulaşılır. Yani;

pi[0] değeri 3'ü, p[5] değeri de 9'u taşır. Bizde gayette hızlı olan yolla index vererek array içindeki değerleri kullanabiliriz. Bunun bilgisayar mühendisliğindeki geyiği erişim O(1) dır.

Follow up:

Ne demek bu O(1)?

Dizi boyutu ne olursa olsun, ister 10 ister 1.000.000 elemanlı array içerisindeki herhangi bir elemana ulaşma süresi sabittir, aynıdır, hızlıdır.

Buraya kadar olanı bize okullarda öğretilen.

Peki index yerine başka bişey kullanmak gerekirse?

Mesela tanıdığınız evinizdeki kedilerin yaşlarını tutan bir array yapmak gerekirse.

Bu durumda klasik olarak düşünürsek bize iki tane array lazım. Yani;

string[] isimler = new string[] { "memcoş", "pıtık", "sarı", "nuri" };
int[] yaslar = new int[] { 4, 3, 5, 2 };

Şimdi sorunlar burda başlıyor.

Mesela "sarı" isimli kedinin yaş'ını bulmak istersek önce isimler array'inden "sarı"nın index'ini isimler'deki elemanların içine bakarak bulmak, sonrada o index'deki yaşlar arrayindeki değeri almak gerekli.

Bu 4 elemanlı bir arrayde sorun yaratmayabilir ama evde 10.000 tane kedi beslemeyi düşünüyorsanız maddi manevi acılar çekiyor olacaksınız.

Hemen mühendislik geyiği karşılığını verelim. Bu tür bir kullanımdaki erişim algoritmasıda O(n) dır. "n" dizideki eleman adedidir ve arrayiniz ne kadar büyükse algoritmanızda o kadar yavaş çalışır.

HashTable

HashTable algoritması/class'ı bu sorunları çözmek amacıyla geliştirilmiştir. Temel amaç index tipi ne olursa olsun bir array'deki elemanlara O(1) süresinde erişmektir.

HashTable kediler = new HashTable();

kediler.Add("memcoş",4);
kediler.Add("pıtık",3);
kediler.Add("sarı",5);
kediler.Add("nuri",2);

şeklinde array'inizi doldurabilir,

int yas = (int)kediler["sarı"];

şeklinde sarı'nın yaşını kaç tane kediniz olursa olsun çok kısa bir sürede bulabilirsiniz.

HashTable class'ı .NET'in 1.0 versiyonundan beri System.Collections altında sakince oturur ve birisinin onu kullanmasını bekler.

Ancak bu class'ın örnekte verilen Add() metodu iki tane "object" tipinde parametre ister. object tipinde olmasının sebebi ise bu class'a herhangi bir tipde birşey koyabilmeniz içindir ama c#'daki "object" sorunsalı olarak boxing/unboxing yapılmak zorunda. Yani HashTable'dan veri alırken asıl tipe cast etmek ( (int) şeklinde ) zorundasınız.

Eğer halen 1.0 veya 1.1 versiyonlarını kullanıyorsanız daha az boxing yapılsın diye NameValueCollection benzeri genetik bozuklukları olan class'ları kullanabilirsiniz.

Eğer 2.0 versiyonunu kullanıyorsanız bu class'ın daha yakışıklı hali Dictinary'i kullanabilirsiniz. Generics nedir bilmiyorsanız bu bölümü atlayın.

Dictionary<string,int> kediler = new Dictionary<string,int>();

şeklinde tanımlayarak gayet sorunsuz bir şekilde kullanabilirsiniz.

Güneş yüzü henüz görmemiş programcılarımız "aa! süper!" diyerek bu class'a atlamadan önce son bir konu olarakta bu HashTable algoritmasının nasıl çalıştığını öğrenmek tavsiye edilir.

Nasıl Çalışıyor?

Bu sorunun cevabı aslında en dipdeki class olan "object" üzerinde bulunur.

GetHashCode()

Bu fonksiyonun yaptığı şey mümkün olabildiği kadar o obje için unique (benzersiz) bir sayı üretir. Eğer iki objenin hashcode'ları aynı ise aynı şey olduğunu düşünebilirsiniz ancak bu her zaman garanti edilmez. (Bu konuya sonra gelelim)

Yeni bir hash table yarattığınızda yaptığı şey temel olarak kendi içerisinde yine bir array, array'in boyutunu ve array'deki eleman adedini gösteren bir rakam tutar. Örneğin;

int doluluk = 0;
int boyut = 16;
int[] indexler = new int[boyut];

ve siz her Add(key,value) metodunu çağırdığınızda key objesinin üstündeki GetHashCode() fonksiyonunu çağırır.

Dönen sayıyı array boyutu ile modlar. (Mod nedir bilmiyorsanız bölme işleminden kalan demektir)

Mesela hash code'u 23 olan bir şey eklediğinizde;

23 % 16 = 7

diyerek kendi içerisindeki array'in 7. elemanına o objeyi yerleştirir ve doluluk oranını 1 arttırır.

Siz hashtable içerisinden bir şey istediğinizde verdiğiniz key'in hashcode'u ile aynı tekrar işlemleri yapar ve içerdeki arrayde ne varsa onu size geri verir yani dizideki 7. pozisyondaki şey ne ise o. ( İşte burası O(1) algoritmasıdır.)

Bu işlem doluluk oranı array'in boyutuna gelene ( aslında burda istatistik hesapları yapıp tam dolmasını beklemez ama neys) kadar hep aynı şeyleri yapar.

Diyelimki içerdeki array dolmak üzere, bu durumda da eski array boyutundan daha büyük (genellikle 2 katı) yeni bir array tanımlar ve eski key'lerin tekrar hashcode'larını alarak yeni array'e yerleştirir.

Tahmin edeceğiniz üzere bu işlem biraz maliyetli. Bu çok olmasın diye HashTable yaratırken kapasite veya fill factor oranlarını düşünerek vermeniz gerekebilir.

Son bir sorun kaldı o da mod işleminden sonra iki farklı obje aynı hashcode'u verirse ne olacak? Burdaki çözümde yine basittir, genellikle yapılan o pozisyona minik boyutlarda bir hashtable daha konarak 2. seviyede yerleştirme yapılır. Bu olayın mühendislik geyiğide collision diye geçer. Yine tahmin edileceği üzere bu da biraz maliyetli bir işlem.

Collision oluşmasını engellemek için GetHashCode fonksiyonunu gerekirse override ederek düzgün değerler ( genellikle yapılan database'deki ID numarası verilir ) dönmesi sağlanmalıdır.

Yüzelli bin tane farklı yaklaşımla/strateji ile HashTable yazmak mümkündür ancak genel olarak hikaye böyledir.