Veri Yapıları 8 Hashing Nedir ? Verilerin belirli bir mantıkla tutulmasına yarayan bir sistemdir. Yaptığı işlemler insert, delete, search gibi işlemlerdir ancak bunları yapabilmek için gerekli olan aramayı belirli bir mantıkla yapmaktadır. Diziler, bağlı listeler de alternatif olarak kullanılabilir. Esas işlem search işlemi olduğundan burada doğrusal yöntemler yavaş kalacaktır. Önceki bölümlerde aramadaki gücünden bahsettiğimiz Graf veya ağaç veri yapısı ise maliyetli kalacaktır. İkisinin ortası niyetine kullanılan hashing arama maliyeti neredeyse tek bakmada bulduğundan o(1) kadardır.
Hashing ile veriyi nereye yerleştireceğimiz bir liste vasıtasıyla belirlenir. Daha sonra arama işleminde de aynı mantık kullanılacağından hızlı bir bulma söz konusu olacaktır.
Eklenmek istenen sayı oluşturulan liste dizisinin boyutuna göre modunun alınması ve mod değerine göre ilgili indise yerleştirilmesi şeklinde çalışmaktadır. Örneğin dizi boyutu 10 olsun ve eklenecek sayı 23 olsun. 23 sayısının 10’a bölümünden kalan 3 olacaktır. Bu da bize 23 sayısının dizide 3. indise yerleştirilmesi gerektiğini söyler. Burada unutulmaması gereken dizi indislerinin sıfırdan başladığıdır.
Resim-1
Yerleştirirken de ararken de hatta silme işlemi yapılırken de mod alınır indisi tespit eder. Hash çalışma mekanizmasının olumsuz yanı ise mod alarak tespit edilen değerden iki tane – üç tane olabilir. Yani 35 % 10 ile 45 % 10 ikisinde de mod 5 olacaktır. Hangi indis olduğunu tespit etmek burada sorun teşkil edecektir. Bu durum collision (çakışma) olarak geçmektedir. Çakışma olduğunda 3 yöntemle çözüme gidilir.
- Seperate Chaining (Linked List ile çözüm)
- Linear Probing
- Quadratic Probing
Seperate Chaining Yöntemi
Bu yöntemle aynı mod değerine sahip birden fazla değer geldiğinde değerleri ilgili indisin yanından bir bağlı liste oluşturarak yan yana yazarız. Yani 25 % 10 ve 35 % 10 örneklerinde her ikisinde de 5 gelecektir. İlk gelen değeri yani 25 ‘i dizide 5 numaralı indise yazarız. Daha sonra gelen 35 değerini ise 25 değerinin hemen yanına bağlı liste ile işaret ederek yazarız. Bu şekilde kaç tane değer varsa aynı indise yan yana bağlı liste olarak yazmaya devam ederiz. Arama ve diğer işlemlerde de bu şekilde önce indis daha sonra bağlı listesi kontrol edilir.
Resim-2
Linear Probing Yöntemi
Bu yöntemde çakışma olduğundan sayıyı dizinin bir sonraki indisine ekleriz. Yani seperate chaining H(x) ise Linear Probing H(x)+i olarak yerleşir. Bu yöntemin bir avantajı da tüm listeyi dolduruyor oluşudur.
Resim-3
Quadretic Probing Yöntemi
Bu yöntemde de H(x) + i^2 olarak işlem yapılır. Yani çakışma olduğu durumda bir sonraki indis değerinin karesi olan yere veri yerleştirilir. Arama ve diğer işlemlerde de buna göre bakılır.
Resim-4
Hashing Nedir yazımızın sonuna geldik.
Bu konuyla ilgili sorularınızı alt kısımda bulunan yorumlar alanını kullanarak sorabilirsiniz.
Referanslar
Algoritmalara Giriş Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
