Ağustos 15, 2022
Bilgisayar bilimi ile daha yoğun bir şekilde ilgileniyorsanız, hash işlevi terimiyle kesinlikle karşılaşmışsınızdır. Bu, birçok güncel teknoloji için önemli bir rol oynar – örneğin veri depolama veya blok zincirler için . Ancak hash fonksiyonları diğer birçok alanda da büyük önem taşımaktadır.
Bu iki bölümden oluşan makale, size karma işlevini tanıtır. İlk bölüm, bir hash fonksiyonunun ne olduğunu açıklar ve en önemli kalite kriterlerini belirtir. İkinci kısım daha sonra olası uygulamalarla ilgilenir ve sık kullanılan bir özet fonksiyonunu sunar.
Karma işlevi – genellikle Almanca’da dağılım işlevi olarak adlandırılır – bir girdi kümesinden bir hedef kümesine bir değeri eşlemek için kullanılır. Hedef miktar genellikle önemli ölçüde daha küçüktür, bu nedenle bunun için daha az depolama alanı gerekir.
Bunu bir örnekle göstermek için çok basit bir hash fonksiyonu geliştiriyoruz. Girilen miktar bir okulun sınıf listesini temsil eder, ancak sadece ilk isimleri kullanırız. Hash fonksiyonumuz artık her ismin harflerini saymaktan oluşuyor. Bu değer daha sonra hash fonksiyonunun sonucunu temsil eder ve bireysel isimlere atanır. Bu daha sonra şöyle görünebilir, örneğin:
Şimdi öğrencilerin devam durumunu bir tabloya girmek istediğimizi varsayarsak, nispeten büyük miktarda bellek kaplayan isimler yerine basitçe ilgili sayıları girebiliriz. Bunun için çok daha az depolama alanı gereklidir.
Ancak, birkaç öğrencinin adı aynı uzunlukta olduğunda sorunlar ortaya çıkabilir. Susanne’ın da sınıfta olduğunu varsayıyoruz. Hash değeri 7’dir – tıpkı öğrenci Michael gibi. Susanne’ın bir gün okula gitmediğini varsayarsak, tablomuza 7 değerini gireriz. Daha sonra velilere bir bildirim yazıp burada sadece 7 değerini bulmak istersek, o gün Michael mı yoksa Susanne mı eksik bilmiyoruz. Bu durumda net bir atama mümkün değildir. Bu durumda, birkaç çıktı değeri aynı karma değeri ürettiğinden, bir çarpışmadan söz edilir.
Bu sorunu çözmek için, mümkün olduğunca az çarpışma ile hash fonksiyonlarını kullanmak mantıklıdır. Örneğin, soyadını da alabilir ve harfleri alfabedeki konumlarına göre ağırlıklandırabiliriz. Bu zaten çarpışma olasılığını önemli ölçüde azaltacaktır. Çoğu okul için net bir atama muhtemelen bu şekilde zaten mümkün olacaktır. Bununla birlikte, çarpışma olasılığı pratik kullanımda önemli olmayacak kadar düşük olacak şekilde tasarlanmış birçok başka hash işlevi vardır.
Ek olarak, olası çarpışmalara rağmen bir karma işlevi kullanmanın anlamlı olduğu kullanım durumları vardır. Bunu göstermek için, bir konuşma yapacak bir öğrenci belirlemek istediğimizi varsayalım. Bunun için hangi öğrenciyi seçtiğimiz gerçekten umurumuzda değil. Tek şart, ders için temel bilgilerin tartışıldığı belirli bir okul gününde hazır bulunmasıdır. Artık sınıf listesinden rastgele bir öğrenci seçebiliriz. Hash değeri tabloda görünmüyorsa, o günü kaçırmadığını güvenle söyleyebiliriz. Bu nedenle onu ders için seçebiliriz.
Ancak karşılık gelen numara mevcutsa güvenilir bir açıklama yapamayız. Öğrencinin o gün gelmemiş olması mümkündür. Ancak, aynı sayıda harfe sahip olan başka bir öğrencinin kayıp olması da olabilir. Ancak örneğimizde kesin bir atama gerekli değildir. Başta belirtildiği gibi, herhangi bir öğrenci devamsızlık yapmadığı sürece ders için uygun olduğundan, başka bir tane seçip testi tekrarlayabiliriz – doğrulamamız seçilen kişinin devamsız olmadığından emin olana kadar. Bu örnek kesinlikle biraz yapmacık görünüyor. İstatistikte – ve dolayısıyla büyük verinin son derece önemli alanında – karma değerinin gerekli tüm bilgileri sağladığı ve yine de gerekli depolama alanını büyük ölçüde azaltabileceği birçok kullanım durumu vardır.
Karma işlevleri oluşturmanın sayısız yolu vardır. Ancak, belirli kalite kriterlerine dikkat etmek önemlidir. Yukarıda sunduğumuz sadece harfleri sayan fonksiyonumuz bir hash fonksiyonudur. Ancak, bu, pratikte neredeyse hiç kullanılmayacak kadar yüksek açıklara sahiptir. Aşağıdaki bölümlerde size iyi bir hash fonksiyonunun sahip olması gereken özellikleri tanıtacağız.
Çarpışma olasılığı mümkün olduğunca düşük olmalıdır. Özellikle, kesin bir atama gerekliyse, bu tür çarpışmaların olasılığı istatistiksel olarak önemsiz olacak kadar düşük olmalıdır.
Tüm hash değerleri, belirtilen değer aralığında mümkün olmalıdır. Fonksiyon, istenen değer aralığına ait olmasına rağmen belirli bir değerin oluşmayacağı şekilde tasarlanmışsa, özet fonksiyonu optimal olarak seçilmemiştir. Ayrıca değerler, değer aralığı boyunca mümkün olduğunca eşit olarak dağıtılmalıdır.
Hash fonksiyonları ile çalışırken genellikle ilgili hesaplamaları çok sık yapmak gerekir. Bu nedenle, bunların verimli bir şekilde çalışması önemlidir.
Bazı kullanım durumlarında, karma işlevi için ek gereksinimler vardır. Örneğin kriptografi alanında kullanılan hash fonksiyonlarında, hash değerinin sabit bir uzunluğu önemlidir. Hash fonksiyonları temelde geri döndürülemez – bu nedenle hash değerinden orijinal değeri tam olarak hesaplamak mümkün değildir. Kriptografik özet fonksiyonları söz konusu olduğunda, özet değerinin, başlangıç değeri hakkında herhangi bir yaklaşık sonuca varılmasına izin vermemesi de önemlidir . Ek olarak, orijinal girdinin küçük bir modifikasyonu bile burada çok farklı bir sonuç üretmelidir. Burada, fonksiyonun yüksek bir difüzyon seviyesine sahip olduğu gerçeğinden bahsediliyor. Diğer uygulamalar için, hash fonksiyonunun sıra koruyucu olması da önemli olabilir. Bu, sıralanan hash değerlerinin sıralanan tohum değerleriyle aynı sıraya sahip olduğu anlamına gelir.
Bir hash fonksiyonunun ne olduğunu ve hangi kalite kriterlerine sahip olması gerektiğini çözdükten sonra, bu fonksiyonların pratikte ne gibi olası uygulamaları olduğu sorusu ortaya çıkıyor. Bunun cevabını bu makalenin ikinci bölümünde okuyabilirsiniz.
Hash fonksiyonları bölüm 1: tanım ve kalite kriterleri