Home / Veri Yapıları / Hashing Nedir? (Veri Yapıları)

Hashing Nedir? (Veri Yapıları)

Veri yapıları dersleri kapsamında Hashing nedir sorusunu ayrıntılı bir şekilde cevaplamaya çalışacağız. Hashing’i anlatmadan önce, programlama dünyasında özellikle ram üzerindeki bir veriyi bulmakla ilgili bir derdimizin olduğunu bilmek gerekir. Bir veri yapısı üzerinde bir veriyi aramak ve bulmak sancılı bir süreçtir. Bu konuyla ilgili çeşitli arama algoritmaları oluşturulmuş, çeşitli veri yapıları kullanılmıştır. Örneğin Heap Yapısı da bunlardan biridir.

Hashing’in temel fikri, elimdeki veriyi sistematik olarak yerleştireyim ki, aradığımda direkt adrese bakayım şeklindedir. Mesela evinizde bir dolap olsun, dolaplarda da gözler olsun. Siz bir eşyayı aradığınızda tüm gözlere tek tek mi bakarsınız yoksa hangi gözde hangi eşyanız var bilir de direkt olarak hedefe mi yönlenirsiniz? İşte Hashing Veri Yapısındaki temel fikir de budur. Ancak bilgisayar dünyasındaki temel sorun, bu dünyanın sürekli dinamik olması ve ekleme & çıkarma işlemlerinin sık sık yapılması kaynaklıdır.

Şimdi konuyu biraz daha spesifik bir hale getirelim. Elimizde sayılar var, bu sayıları bir diziye (array) yerleştirmemiz gerekiyor. Ancak temel hedefimizde arama işlemini kolaylaştırmak olacak. Bunu nasıl yapabiliriz? Akla Sıralama Algoritması Kullanmak gelebilir. iyi bir fikir gibi görünse de bizim temel amacımız olan hemen bulma durumunu gerçekleştiremeyecektir. Şimdi neden olmayacaktır bunu anlatalım Sorunları listeleyelim.

1- Sıralama Maliyeti: Çok yüksek miktardaki sayıyı sıralamak zaten bir işlem ve süre maliyeti getirecektir.

2- Ekleme/Çıkarma işlemleri: Özellikle dizi veri yapısı üzerinde ekleme çıkarma yapmak sancılı bir iştir. Hele kaydırma yapmak gibi işlemler düşünüldüğünde bu maliyet iyice artmaktadır

3- Arama Maliyeti: Sayıların sıralı olması, hemen bulunacağı manasına gelmez, yalnızca arama algoritmasının performansına kalmış bir durumdur.

Yukarıdaki 3 temel problem, bizim hızlı bulma amacımızı karşılamamaktadır. Peki ama çözüm nasıl olacak?

Hashing Nedir?

Şimdi direkt olaya girelim, Hashing bize diyor ki, Eklemek istediğin sayıyı, yerleştirmek istediğin dizinin boyutuna göre modunu al, o indise yerleştir. Arama yaparken, bir sayıyı aradığın dizinin boyutuna böl, o indiste sayıyı bulacaksın. Evet Hashing bize bunu diyor, örnek üzerinde göstermek gerekirse; 10 tane eleman alabilen bir dizimiz olsun. Amacımız elimizdeki sayıları bu dizi üzerine hashing mantığına göre yerleştirerek nasıl yapıldığını görelim.

Hashing Örnek

24, 36, 98, 102 ve 70 sayılarını 10 boyutlu dizimize yerleştirmeye kalktığınızda hangi indise yerleştireceğimizi şu şekilde buluruz;

24 % 10 (24’ün 10’a göre modu) = 4

36 % 10 = 6

98 % 10 = 8

102 % 10 = 2

70 % 10 = 0

Solda Gördüğünüz üzere dizinin ilgili indislerine (indisin sıfırdan başladığına dikkat edin) sayılarımızı yerleştirdiğimizi görüyorsunuz. Eklemek istediğimiz sayının, dizinin boyutuna göre modunu alıp dizinin ilgili indisine sayıyı yerleştiriyoruz. İlla sayı yerleştirmek zorunda değiliz. Yerleştirilen bir string ya da nesne de olabilirdi. Sayılar üzerinden gitmemizin nedeni daha anlaşılabilir olmasıdır. Peki yerleştirme işlemi bu şekilde, bulma işlemi nasıl olacak?

Örnek olarak 102 sayısını aramak istediğimizde biz bu diziye tek tek bakmayacağız. Nasıl olsa yerleştirme mantığını biliyoruz, 102 sayısının 10’a göre modunu aldığımızda 2 olduğunu görürüz ve dizinin 2. indisine bakarız, baktığımız yerde 102 sayısını buluruz. İşler bu ana kadar toz pembe olarak gitti, ancak bilgisayar dünyasında işler hiç de böyle gitmez. Şimdi dizimize yeni bir sayı ekleyelim, sayımız da 224 olsun. 224 % 10 yaptığımızda sonucun 4 olduğunu görürüz. Dizinin 4. indisine gideriz, o da ne? dizinin 4. indisi dolu, o halde ne yapacağız? İşte Hashing’i bilmek esasında bundan sonraki durumlar ile ilgili bir konudur. Genel terminolojide bu duruma Collision adı verilir. Collision kelimesinin Türkçesi çakışmadır. Zaten olan durumun tam da karşılığı budur. Hashing Collision durumunda 3 değişik çözüm sunar. (Bazıları iki değişik çözüm der, 2. ve 3. çözümler birbirine benzerdir çünkü. Şimdi bu duruma açıklama getirelim…

Hashing Collision (Çakışma) Çözümleri

Eğer yerleştirilecek olan verinin yerinde başka bir veri varsa aşağıdaki çözümler uygulanır.

  1. Çözüm: Seperate Chaining
  2. Çözüm: Open Addressing (bu da kendi içerisinde ikiye ayrılır, hocanız size totalde 3 çözüm anlatırsa kafanız karışmasın, aynı şeyden bahsedeceğiz)

Seperate Chaining

Seperate Chaining aynı hash değeri üzerinde linked list (Bağlı liste) oluşturmayı hedefler. Yani başka bir hashing değerine elemanı yerleştirmek yerine ilgili hashing değerinde yer alan sayı, yeni gelen sayıyı işaret eder.

Hatırlatma: Bağlı Listeler konusunu unuttuysanız sitemizin arama kısmına bağlı liste ya da linked list yazarak pek çok yazıya ulaşabilirsiniz.

Hemen örnek üzerinde gösterelim, yukarıdaki örneğe, 224, 44 ve 94 sayılarını ekleyelim. Dizimizin boyutuna göre modunu aldığımızda tüm sayılar için sonucun 4 olduğunu göreceğiz. Yani dizimizin 4. indisine yerleşmesi gerekecek. Hatta bunun da üzerine 56 ve 86 sayılarını ekleyelim.

Soldaki örnekte de gördüğünüz üzere, dizide herhangi bir yeni alan işgal etmeden elemanlarımızı bağlı liste şeklinde ekledik. Peki böyle bir durumda, nasıl eleman bulacağız? 94 sayısını aramaya kalktığımızda, 94%10 = 4 bulup dizinin 4. indisinde 74’ü bulacağız. İlgili elemanın next node (işaret ettiğini değeri) kontrol edeceğiz, 224, daha sonra 224’ün işaret ettiği değeri kontrol edeceğiz 44’ü bulup tekrar kontrol ettiğimizde 94 sayısını bulacağız. Evet tek seferde bulamıyoruz ancak bunu çok büyük veri grupları içerisinde uyguladığımızı düşününce daha küçük bir alanda arama yaptığımız bir gerçek. Ancak bu yöntemin de Avantajları ve dezavantajları var. Dilerseniz bunlara göz atalım.

Seperate Chaining Yönteminin Avantajları

  • Uygulaması Kolaydır
  • Hash Tablosu asla dolmaz, sürekli yeni eleman ekleyebilirsiniz.
  • Bu yöntem çoğunlukla kaç tane eleman ekleyeceğinizi bilmediğiniz durumlarda uygulayabilirsiniz. Daha işlevseldir.

Seperate Chaining Yönteminin Dezavantajları

  • Bağlı Listeler üzerinde Cache performansı çok iyi değildir. Open Addressing bu durumlarda daha işlevsel kalır.
  • Dizinin boş alanları çöpe gider. Örneğimizde de gördüğünüz üzere bir sürü boş alan kaldı.
  • Eklenen sayılar sürekli benzer sonuç üretiyorsa yani sürekli modu aynı sonucu veriyorsa hashing yönteminin hiçbir avantajı kalmaz, maliyet O(n)’e bile gidebilir. (Worst case)
  • Bağlı liste kullandığımız için ekstra bir alan kullanırız.

Seperate Chaining yani Linked List yöntemi genel anlamda kaç tane sayı ekleneceğinizi bilmiyorsanız, ekleyeceğiniz verinin dizi sınırlarını aşma ihtimali varsa kullanılmalıdır. Diğer durumlarda Hashingin nimetlerinden faydalanmanızı engelleyebilir.

 

Open Probing

Open Probing Seperate Chaining’e alternatif bir yöntemdir. Amaç yine Hashing üzerinde collision’ları (çakışmaları) çözmektir. Kendi içerisinde ikiye ayrılır.

Lineer Probing

Lineer probing, eğer hash tablosunda ilgili yer dolu ise bir sonrakine bakmak ile ilgili bir çözüm sunar. Formülüze edersek (h(x) + i) % s şeklindedir. s dediğimiz size’ın kısaltması yani dizinin boyutudur. (Örneğimizde bu değer 10’du. i ise 0’dan başlayan bir sayıdır. Hani ilgili yer boşsa i = 0 denemesinde direkt yerleştirme yapılır. şimdi örnek üzerinde gösterelim.

Örnek üzerinde 103 sayısını yerleştirmek istiyoruz, daha önceden (kırmızı ile yazılmış sayılar) yerleştirilmiş durumda. Elemanlarımızı H(x) + i % s formülüne göre yerleştirmek istediğimiz için ilkin doğal olarak 3. indise bakıyoruz, ancak dolu olduğunu görüyoruz. (ilk adımda i = 0) Daha sonra i değerini 1’er 1’er artırıp kontrol ediyor ve doğru konuma yerleştirme yapıyoruz.

Quadratic Probing,

Quadratic Probing hemen hemen linear probing ile aynı mantıktadır. Tek farkı i değeri i^2 olur. (i*i) O örneği de gösterelim.
Soldaki örnekteki tek fark, i sayısı yerine i^2 değerini kullandık. Esasında amaç olası sıkışıklıklarda daha sonraki boş yerleri bulmak. Ancak daha az adımda çözmüş olmamız daha iyidir demek için yeterli değil. Örnekteki durumumuz tesadüfidiydi. Daha başka durumlarda tam tersi bir durum oluşabilir.

Seperate Chaining versus Open Addressing (Linear & Quadratic Probing)

Şimdi bu iki mantığı birbirleri ile kıyaslayalım.

Seperate Chaining
Open Addressing
Uygulaması Kolaydır
Uygulaması zordur daha çok hesaplama gerektirir
Hash tablosu asla dolmaz, her zaman daha fazla eleman ekleyebilirsiniz
Tablo dolabilir, daha fazla eleman eklemeniz mümkün olmayabilir
Çoğunlukla kaç tane eleman ekleneceği bilinmeyen durumlarda kullanılır
Genellikle eleman sayısı belirli durumlarda kullanılır. Çünkü tablo dolduğunda yeni eleman ekleyemezsiniz.
Teorik olarak tabloda pek çok boş alan kalabilir
Tablodaki tüm boşluklardan yararlanabilirsiniz.
Linked List kullanıldığı için ekstra alan kullanılır
herhangi bir linklemeye ihtiyaç duyulmaz.

 

 

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir