Karışık sayısal ve basit tanımlayıcılar için en iyi karma işlevi

Question

Performans nedenleri için bir dizeyle tanımlanmış bir nesne grubunu gruplara bölme ihtiyacım var. Nesne ya da bir dizi veya noktalar tanımlayıcı parçalarını ayıran öneki (kalifiye) şeklinde bir dizi tanımlanabilir:

12 
323 
12343 
2345233 
123123131 
ns1:my.label.one 
ns1:my.label.two 
ns1:my.label.three 
ns1:system.text.one 
ns2:edit.box.grey 
ns2:edit.box.black 
ns2:edit.box.mixed 

Sayısal tanımlayıcıları 1'den birkaç milyon bulunmaktadır. Metin tanımlayıcılarının, aynı ad alanı öneki (ns1 :) ve aynı yol öneki (edit.box) ile başlayan çok fazla olması muhtemeldir.

Bu amaç için en iyi karma işlevi nedir? Nesne tanımlayıcı istatistiklerine dayanan kepçenin büyüklüğünü bir şekilde tahmin edersem iyi olur. Bazı istatistiksel bilgilere dayanarak iyi hash fonksiyonu oluşturmak için bazı iyi makaleler var mı?

Birkaç milyondan fazla tanımlayıcı vardır, ancak bunların amacı karma işlevine göre bunları 1-2 bin gruba ayırmaktır.

Answer 1

İki iyi karma işlevi, her ikisi de aynı değer alanıyla eşleştirilebilir ve genellikle bunların bir araya getirilmesi sonucunda yeni sorunlara neden olmaz.

Yani karma işlevi şöyle olabilir:

if it's an integer value: 
    return int_hash(integer value) 
return string_hash(string value) 

çevresine belirli değerleri N kovalar olası bir sayıdır N, modulo sizin herhangi bir tamsayı topaklanma bulunmaması durumunda, o zaman int_hash sadece kendi giriş döndürebilir.

Dize hashının seçilmesi yeni bir sorun değildir. Müstehcen performans gereklilikleri olmadıkça "djb2" yi (http://www.cse.yorku.ca/~oz/hash.html) veya benzeri kullanmayı deneyin.

Genel önekleri dikkate almak için karma işlevini değiştirme konusunda fazla bir nokta olduğunu sanmıyorum. Eğer karma işleviniz başlangıçta iyi ise, ortak öneklerin karma değerlerin kümelenmesini yaratması olası değildir.

Bunu yaparsanız ve hash beklenmedik bir şekilde kötü performans göstermezse ve birkaç milyon karma değerinizi birkaç bin kepçeye koyarsanız, kepçe popülasyonları normal olarak dağıtılır (ortalama birkaç milyon/birkaç). bin) ve varyans 1/12 (birkaç bin)^2

Kova başına ortalama 1500 girdiyle, bu, standart sapmayı 430 civarında bir yerde yapar. Normal dağılımın% 95'i, ortalama 2 standart sapma içinde bulunur. Bu yüzden toplamlarımı yanlış yapmadıkça, kovalarınızın% 95'i 640-2360 giriş içerecektir. Bu yeterli mi yoksa daha yakından benzer boyutlarda olması için kovalara mı ihtiyacınız var?

Answer 2

Muhtemelen sha1 ile güvenli bir şekilde gidiyor ve istediğiniz boyuta kesiliyor olabilirsiniz.

Son derece verimli olmaz, ama belki de karma işlevi bir darboğaz olmayacaktır.

Answer 3

CRC16'nın bu dizeleri kullanmak için makul bir karma olacağını ve grupların 1-2 binden fazla çıkmaması gerektiğini düşünüyorum.

Karma tabloyu 1MB + yapmalısınız, ancak içinde birçok öğe var * 4 bayt, bu yüzden 50MB konuşuyoruz ve daha sonra da depolanan tüm gerçek verilere sahip oluyorsunuz.