İyi bir Karma işlev nedir? Üniversitede veri yapıları benim derslerde hash fonksiyonları ve uygulamaları bir sürü gördüm, ama çok zor iyi bir karma işlev yaratmak için çoğunlukla. Çarpışmaları önlemek için genel bir kural olarak benim Profesör dedi ki:

function Hash(key)
  return key mod PrimeNumber
end

(mod C % operatör ve benzeri diller)

karma tablo boyutu asal sayı ile. Bu çarpışmalar ve hızlı bir önlemek için oldukça iyi bir işlevi olduğunu biliyorum, ama nasıl daha iyisini yapabilirim? Daha iyi sayısal tuşlar karşı dize anahtarları için fonksiyonları hash var mı?

“İyi karma” evrensel karma (ed. için bir işlev diye bir şey yok Evet, “evrensel karma” ama demek istediğim bu değil). böyle bir şey var biliyorum İçeriğe bağlı olarak farklı kriterleri bir karma kalitesini belirler. İki kişi zaten SHA bahsetti. Bu bir şifreleme karma ve sen muhtemelen anlamına gelen karma tablo için iyi değil.

Hash tabloları çok farklı gereksinimleri vardır. Ama yine de, iyi bir karma işlev bulma evrensel olarak farklı veri türleri sağlaması farklı bilgileri açığa çıkarmak zordur çünkü. Genel bir kural olarak iyi düşününtümbir tür bilgi aynı derecede tutar. Bu her zaman kolay ve hatta mümkün değildir. İstatistik sebep (ve dolayısıyla çarpışma) için de önemli bir sorun alanı, yani olası tüm oyuncularla iyi bir yayılma oluşturmak mümkün değildir Bu demek oluyor o zaman karma sayıları 100 ila 1050 değil izin en önemli basamak oynamak büyük bir kısmında karma çünkü ~ 90% nesneleri, bu rakam 0 olacaktır. Çok daha önemli son üç rakamı karma tespit edelim.

Dizeleri karma aynı şekilde, tüm dizelerin ilk üç karakteri aynı olacağı önceden bilinen önemli tüm karakterler konuları dışında, bütün bunları göz önüne alarak o zaman kaybıdır.

Bu aslında Knuth için ne diyecek okumanızı tavsiye ederim olgulardan biridirBilgisayar Programlama Sanatıvol. 3. İyi bir okuma Walker The Art of Hashing Şerit.