Linear Probing(Doğrusal Sondalama)

Veri yapıları konusunda Hash Function konusunda karşımıza çıkan Linear Probing konusunun kullanımını beraber anlamaya çalışalım.

Hash Function kullanarak belirli bir uzunluğu olan dizide sayıları sıralarken kullanılabilir.Sayıların çakışma durumunda mod değerinden sonraki sağında bulunan boş yere yerleşir.

Uygulama:

24,75,65,32,81,16,22,17 sayıları bizim değerlerimiz olsun. Bu diziyi Linear Probing dizinin boyutu olan 8’e göre mod alalım.

Her elemanı 8’e bölüp kalan sayıyı ilgili indexin altına yazalım. Çakışma durumu olursa boşta bulunan en küçük index’e o sayı yerleştirilir.

8 Elemanlı bir dizi için index değelerlerini yazalım.

0 – 1 – 2 – 3 – 4 – 5 – 6 – 7

24 sayısı 8‘ye göre mod alma işlemi yaparsak kalan 0 olacaktır. 0. indexe 24 sayısını koyabiliriz.

0.index-> 24

Aynı işlemleri hızlıca tamamlıyalım.

3.index->75

1.index->65

32 değerini 8’e böldüğümüzde kalan 0 ve bizim 0.indeximiz dolu. Bu durumda 32 boşta bulunan en küçük indexe yazılır. Bu durumda 2.indexe 32 değerini koyarız.

2.index->32

Aynı şekilde 81 sayısını 8’e böldüğümüzde 1 kalanını verir.1.index dolu olduğu için en küçük index olan 4’e yazılır.

4.index->81

Aynı şekilde 16 sayısının 8’e göre modu 0.Bu durumda 0. indexte 16 olmalı. Fakat bu index ve beraberindeki 1,2,3,4 dolu olduğu için boş olan en küçük index değeri 5’e 16 değeri yazılır.

5.index->16

6.index->22

7.index->17

Özetle:

Önce ilk elemandan dizinin uzunluğuna bölünür. Mod değerinin indexine yerleştirilir. Eğer iki tane aynı mod değerine sahip değer varsa bunlar o indexten sonraki en küçük boş index değerine sahip yere yerleştirilir. Bu şekilde sıralama tamamlanır.