Collision - Çarpışma?

Hash'ten girince Collision'ı unutmak yakışı kalmaz. Peki nedir bu collision? Gelin şimdi biraz daha geriden alıp, collision'ın tanımını yapalım.

Hash dediğimiz olayı anlatayım önce. Bir key değeriniz var. Yani anahtarınız. O anahtar değerini alıyorsunuz ve bir önceki başlıkta yazdığım Hash Fonksiyonlarına tabi tutuyorsunuz. Ve sonucunda bir değer elde ediyorsunuz ki, bu da sizin adresiniz oluyor. Yani bir değeri hangi adreste saklayacağınızı elde etmiş oluyorsunuz.

Collision, yani çarpışma da farklı key değerlerinden aynı adresi elde etmeniz demektir. Yani iki anahtar çarpışmış oluyor çünkü aynı adrese sahipler! Peki durup duruken iki anahtar aynı adres değerini üretir mi? Elbette hayır. Çarpışma olması için "packing factor"un olması gerekir. Yani kayıt alanının doluluğu. Kayıt ettiğiniz alan dolarsa, haliyle adres de azalır. Bu durumda çarpışma riski de artar. Demek ki bu "packing factor" denilen illete dikkat etmeliyiz. Şöyle tanımlanır:
packing factor= depolanan kayıt sayısı/toplam depolama yerinin boyutu
Bu oran %75'i aşarsa risk de oldukça yüksektir.

Depolama alanı arttıkça collision oranı azalıyor demek ki. Ancak siz depolama alanını arttırısanız, indeks sayısı da artacaktır. Kaldı ki ne zaman kadar arttıracaksınız bu alanı? Sonsuz yer diye birşey olamaz. İlla ki bir sınırı var depolama alanının da. Demek ki farklı yollar aramalıyız. Örneğin, depolama alanını dinamik olarak peyderpey büyütebiliriz. Eş zamanlı olarak hash fonksiyonlarını da peyderpey değiştirebiliriz. Hatta yeri gelir, kayıt silmeyi bile göz önünde bulundurabilirsiniz. Ancak en iyi çözüme ulaşmak için bunlar yetersiz kalacaktır.

Collision Resolution Algorithms (Çarpışmalara Çözüm Algoritmaları) ile bu sorun halledilir. Üç çeşittir:
1. With Links (Bağlar ile)
2. Without Links (Bağ Olmadan)
3. With PseudoLinks (Yalancı Bağlarla)

Bunların detayları çok uzun, bölüm bölüm anlatacağım.