Evrensel hashing - Universal hashing - Wikipedia

İçinde matematik ve bilgi işlem, evrensel hashing (içinde rastgele algoritma veya veri yapısı), bir Özet fonksiyonu belirli bir matematiksel özelliğe sahip bir karma fonksiyon ailesinden rastgele olarak (aşağıdaki tanıma bakınız). Bu, düşük sayıda çarpışmayı garanti eder. beklenti, veriler bir düşman tarafından seçilmiş olsa bile. Pek çok evrensel aile bilinmektedir (tam sayılara, vektörlere, dizelere hashing uygulamak için) ve bunların değerlendirilmesi genellikle çok etkilidir. Evrensel hashing, bilgisayar bilimlerinde çeşitli kullanımlara sahiptir, örneğin karma tablolar, rastgele algoritmalar, ve kriptografi.

Giriş

Bir evrendeki anahtarları haritalamak istediğimizi varsayalım ${ displaystyle U}$ içine ${ displaystyle m}$ kutular (etiketli ${ displaystyle [m] = {0, noktalar, m-1 }}$). Algoritmanın bazı veri setlerini işlemesi gerekecek ${ displaystyle S subseteq U}$ nın-nin ${ displaystyle | S | = n}$ önceden bilinmeyen anahtarlar. Genellikle hashing işleminin amacı, düşük sayıda çarpışma elde etmektir (anahtarlar ${ displaystyle S}$ aynı bölmedeki arazi). Belirleyici bir hash fonksiyonu, rakip bir ortamda, eğer ${ displaystyle U}$ daha büyüktür ${ displaystyle m cdot n}$düşman seçebileceği için ${ displaystyle S}$ tam olarak olmak ön görüntü bir çöp kutusu. Bu, tüm veri anahtarlarının aynı bölmeye düştüğü ve hash işlemini gereksiz hale getirdiği anlamına gelir. Ayrıca, deterministik bir hash fonksiyonu, yeniden yıkama: bazen giriş verileri hash işlevi için kötü olabilir (örneğin, çok fazla çarpışma vardır), bu nedenle biri karma işlevini değiştirmek ister.

Bu sorunların çözümü, karma işlevler ailesinden rastgele bir işlev seçmektir. Bir işlev ailesi ${ displaystyle H = {h: U - [m] }}$ denir evrensel aile Eğer, ${ displaystyle forall x, y U, ~ x neq y: ~~ Pr _ {h H içinde} [h (x) = h (y)] leq { frac {1} {m }}}$.

Başka bir deyişle, evrenin herhangi iki anahtarı en fazla olasılıkla çarpışır. ${ displaystyle 1 / m}$ karma işlevi ne zaman ${ displaystyle h}$ rastgele çekilir ${ displaystyle H}$. Hash fonksiyonu her anahtara gerçekten rastgele hash kodları atarsa, bu tam olarak beklediğimiz çarpışma olasılığıdır. Bazen tanım, çarpışma olasılığına izin verecek şekilde gevşetilir ${ displaystyle O (1 / m)}$. Bu kavram Carter ve Wegman tarafından tanıtıldı^[1] 1977'de ve bilgisayar biliminde çok sayıda uygulama bulmuştur (örneğin bkz. ^[2]). Bir üst sınırımız varsa ${ displaystyle epsilon <1}$ çarpışma olasılığında, elimizde olduğunu söylüyoruz ${ displaystyle epsilon}$- neredeyse evrensellik.

Hepsi olmasa da çoğu evrensel ailede aşağıdakiler daha güçlüdür tekdüze fark özelliği:

${ displaystyle forall x, y , U, ~ x neq y}$, ne zaman ${ displaystyle h}$ aileden rastgele çekilir ${ displaystyle H}$, fark ${ displaystyle h (x) -h (y) ~ { bmod {~}} m}$ eşit olarak dağıtılır ${ displaystyle [m]}$.

Evrensellik tanımının yalnızca ${ displaystyle h (x) -h (y) = 0}$, çarpışmaları sayar. Tekdüze fark özelliği daha güçlüdür.

(Benzer şekilde, evrensel bir aile XOR evrensel olabilir, eğer ${ displaystyle forall x, y , U, ~ x neq y}$, değer ${ displaystyle h (x) oplus h (y) ~ { bmod {~}} m}$ eşit olarak dağıtılır ${ displaystyle [m]}$ nerede ${ displaystyle oplus}$ bit düzeyinde özel veya işlemdir. Bu sadece mümkünse ${ displaystyle m}$ ikinin gücüdür.)

Daha da güçlü bir durum ikili bağımsızlık: bu mülke sahip olduğumuzda ${ displaystyle forall x, y , U, ~ x neq y}$ olasılığımız var ${ displaystyle x, y}$ herhangi bir karma değer çiftine karma oluşturacaktır ${ displaystyle z_ {1}, z_ {2}}$ sanki tamamen tesadüflermiş gibi: ${ displaystyle P (h (x) = z_ {1} land h (y) = z_ {2}) = 1 / m ^ {2}}$. İkili bağımsızlık bazen güçlü evrensellik olarak adlandırılır.

Diğer bir özellik de tekdüzeliktir. Tüm hash değerleri eşit olasılığa sahipse bir ailenin tek tip olduğunu söylüyoruz: ${ displaystyle P (h (x) = z) = 1 / m}$ herhangi bir hash değeri için ${ displaystyle z}$. Evrensellik, tekdüzelik anlamına gelmez. Bununla birlikte, güçlü evrensellik, tekdüzelik anlamına gelir.

Tekdüzen uzaklık özelliğine sahip bir aile verildiğinde, bir çift olarak bağımsız veya güçlü bir evrensel hash ailesi, içindeki değerlere sahip tekdüze dağıtılmış bir rastgele sabit ekleyerek üretilebilir. ${ displaystyle [m]}$ hash işlevlerine. (Benzer şekilde, if ${ displaystyle m}$ ikinin gücüdür, bir XOR evrensel hash ailesinden bir dışlayıcı yaparak veya tekdüze dağıtılmış bir rasgele sabit yaparak ikili bağımsızlık elde edebiliriz.) Bir sabit tarafından yapılan bir kayma bazen uygulamalarda (örneğin, hash tabloları) alakasız olduğundan, dikkatli bir ayrım düzgün uzaklık özelliği ile ikili bağımsızlık arasında bazen yapılmaz.^[3]

Bazı uygulamalar için (karma tablolar gibi), karma değerlerin en az anlamlı bitlerinin de evrensel olması önemlidir. Bir aile son derece evrensel olduğunda, bu garanti edilir: ${ displaystyle H}$ ile son derece evrensel bir ailedir ${ displaystyle m = 2 ^ {L}}$, sonra aile fonksiyonlardan oluşur ${ displaystyle h { bmod {2 ^ {L '}}}}$ hepsi için ${ displaystyle h H'de}$ aynı zamanda için son derece evrenseldir ${ displaystyle L ' leq L}$. Ne yazık ki, aynı şey (yalnızca) evrensel aileler için geçerli değildir. Örneğin, kimlik işlevinden oluşan aile ${ displaystyle h (x) = x}$ açıkça evrenseldir, ancak işlevin oluşturduğu aile ${ displaystyle h (x) = x { bmod {2 ^ {L '}}}}$ evrensel olmakta başarısızdır.

UMAC ve Poly1305-AES ve diğerleri mesaj doğrulama kodu algoritmalar evrensel hashlemeye dayanır.^[4][5]Bu tür uygulamalarda, yazılım her mesaj için o mesaj için benzersiz bir nonce'a dayalı olarak yeni bir özet işlevi seçer.

Çeşitli karma tablo uygulamaları evrensel karmaşaya dayanmaktadır. Bu tür uygulamalarda, tipik olarak yazılım yeni bir karma işlevini ancak "çok fazla" anahtarın çarpıştığını fark ettikten sonra seçer; o zamana kadar, aynı hash işlevi defalarca kullanılmaya devam eder. (Bazı çarpışma çözümleme şemaları, örneğin dinamik mükemmel hashing, her çarpışma olduğunda yeni bir hash işlevi seçin. Diğer çarpışma çözme şemaları, örneğin guguklu haşlama ve 2 seçenekli hashing, yeni bir karma işlevi seçmeden önce bir dizi çarpışmaya izin verin). Tamsayılar, vektörler ve dizgiler için en hızlı bilinen evrensel ve son derece evrensel hash işlevlerinin bir araştırması içinde bulunur.^[6]

Matematiksel garantiler

Herhangi bir sabit set için ${ displaystyle S}$ nın-nin ${ displaystyle n}$ anahtarlar, evrensel bir aile kullanmak aşağıdaki özellikleri garanti eder.

1. Herhangi bir sabit için ${ displaystyle x}$ içinde ${ displaystyle S}$, bölmedeki beklenen anahtar sayısı ${ displaystyle h (x)}$ dır-dir ${ displaystyle n / m}$. Hash tablolarını uygularken zincirleme, bu sayı, anahtarın dahil olduğu bir işlemin beklenen çalışma süresiyle orantılıdır. ${ displaystyle x}$ (örneğin bir sorgu, ekleme veya silme).
2. Beklenen anahtar çifti sayısı ${ displaystyle x, y}$ içinde ${ displaystyle S}$ ile ${ displaystyle x neq y}$ çarpışan (${ displaystyle h (x) = h (y)}$) ile sınırlanmıştır ${ displaystyle n (n-1) / 2m}$hangisi doğru ${ displaystyle O (n ^ {2} / m)}$. Kutu sayısı ne zaman, ${ displaystyle m}$ doğrusal olarak seçilmiştir ${ displaystyle n}$ (yani, içindeki bir işlev tarafından belirlenir ${ displaystyle Omega (n)}$), beklenen çarpışma sayısı ${ displaystyle O (n)}$. Hashing yaparken ${ displaystyle n ^ {2}}$ en az yarım olasılıkla hiçbir çarpışma yok.
3. En az anahtarın bulunduğu bölmelerdeki beklenen anahtar sayısı ${ displaystyle t}$ İçlerindeki anahtarlar yukarıda ${ displaystyle 2n / (t-2 (n / m) +1)}$.^[7] Bu nedenle, her bölmenin kapasitesi ortalama boyutun üç katı ile sınırlandırılmışsa (${ displaystyle t = 3n / m}$), taşan bölmelerdeki toplam anahtar sayısı en fazla ${ displaystyle O (m)}$. Bu sadece çarpışma olasılığı yukarıda belirtilen hash ailesi için geçerlidir. ${ displaystyle 1 / m}$. Daha zayıf bir tanım kullanılıyorsa, onu sınırlayarak ${ displaystyle O (1 / m)}$, bu sonuç artık doğru değil.^[7]

Yukarıdaki garantiler herhangi bir sabit set için geçerli olduğundan ${ displaystyle S}$, veri seti bir düşman tarafından seçilmişse tutarlar. Bununla birlikte, rakip bu seçimi, algoritmanın bir hash fonksiyonunun rastgele seçiminden önce (veya ondan bağımsız olarak) yapmalıdır. Düşman algoritmanın rastgele seçimini gözlemleyebiliyorsa, rastgelelik hiçbir amaca hizmet etmez ve durum deterministik hashing ile aynıdır.

İkinci ve üçüncü garanti tipik olarak aşağıdakilerle birlikte kullanılır: yeniden yıkama. Örneğin, bazılarını işlemek için rastgele bir algoritma hazırlanabilir. ${ displaystyle O (n)}$ çarpışma sayısı. Çok fazla çarpışma gözlemlerse, başka bir rastgele seçer. ${ displaystyle h}$ aileden ve tekrarlar. Evrensellik, tekrarların sayısının bir geometrik rastgele değişken.

İnşaatlar

Herhangi bir bilgisayar verisi bir veya daha fazla makine kelimesi olarak temsil edilebildiğinden, genellikle üç tip alan için karma fonksiyonlara ihtiyaç vardır: makine kelimeleri ("tamsayılar"); makine kelimelerinin sabit uzunluklu vektörleri; ve değişken uzunluklu vektörler ("dizeler").

Karma tamsayılar

Bu bölüm, makine sözcüklerine uyan tamsayıların hash edilmesi durumuna atıfta bulunur; bu nedenle, çarpma, toplama, bölme vb. işlemler, makine seviyesinde ucuz talimatlardır. Evren hashedilsin ${ displaystyle U = {0, noktalar, m-1 }}$.

Carter ve Wegman'ın orijinal önerisi^[1] bir asal seçmekti ${ displaystyle p geq m}$ ve tanımla

${ displaystyle h_ {a, b} (x) = ((balta + b) ~ { bmod {~}} p) ~ { bmod {~}} m}$

nerede ${ displaystyle a, b}$ rastgele seçilen tamsayı modulo ${ displaystyle p}$ ile ${ displaystyle a neq 0}$. (Bu, bir doğrusal eşleşik üreteç.)

Görmek için ${ displaystyle H = {h_ {a, b} }}$ evrensel bir ailedir, unutmayın ${ displaystyle h (x) = h (y)}$ sadece ne zaman tutar

${ displaystyle ax + b equiv ay + b + i cdot m { pmod {p}}}$

bir tamsayı için ${ displaystyle i}$ arasında ${ displaystyle 0}$ ve ${ displaystyle (p-1) / m}$. Eğer ${ displaystyle x neq y}$onların farkı ${ displaystyle x-y}$ sıfırdan farklıdır ve ters bir moduloya sahiptir ${ displaystyle p}$. İçin çözme ${ displaystyle a}$ verim

${ displaystyle a eşdeğeri ben cdot m cdot (x-y) ^ {- 1} { pmod {p}}}$.

Var ${ displaystyle p-1}$ için olası seçenekler ${ displaystyle a}$ (dan beri ${ displaystyle a = 0}$ hariç tutulur) ve değişen ${ displaystyle i}$ izin verilen aralıkta, ${ displaystyle lfloor (p-1) / m rfloor}$ sağ taraf için olası sıfır olmayan değerler. Böylece çarpışma olasılığı

${ Displaystyle lfloor (p-1) / m rfloor / (p-1) leq ((p-1) / m) / (p-1) = 1 / m}$.

Görmenin başka bir yolu ${ displaystyle H}$ evrensel bir ailedir istatistiksel mesafe. Farkı yazın ${ displaystyle h (x) -h (y)}$ gibi

${ displaystyle h (x) -h (y) eşdeğeri (a (x-y) ~ { bmod {~}} p) { pmod {m}}}$.

Dan beri ${ displaystyle x-y}$ sıfır değildir ve ${ displaystyle a}$ eşit olarak dağıtılır ${ displaystyle {1, noktalar, p-1 }}$bunu takip eder ${ displaystyle a (x-y)}$ modulo ${ displaystyle p}$ ayrıca homojen olarak dağıtılır ${ displaystyle {1, noktalar, p-1 }}$. Dağılımı ${ displaystyle (h (x) -h (y)) ~ { bmod {~}} m}$ bu nedenle, olasılık farkına kadar neredeyse tekdüzedir ${ displaystyle pm 1 / p}$ örnekler arasında. Sonuç olarak, tek tip bir aileye istatistiksel mesafe ${ displaystyle O (a / p)}$ne zaman önemsiz hale gelir ${ displaystyle p gg m}$.

Daha basit hash fonksiyonları ailesi

${ displaystyle h_ {a} (x) = (balta ~ { bmod {~}} p) ~ { bmod {~}} m}$

sadece yaklaşık olarak evrensel: ${ displaystyle Pr {h_ {a} (x) = h_ {a} (y) } leq 2 / m}$ hepsi için ${ displaystyle x neq y}$.^[1] Dahası, bu analiz neredeyse sıkıdır; Carter ve Wegman ^[1] olduğunu göstermektedir ${ displaystyle Pr {h_ {a} (1) = h_ {a} (m + 1) } geq 2 / (m-1)}$ her ne zaman ${ displaystyle (p-1) ~ { bmod {~}} m = 1}$.

Modüler aritmetikten kaçınmak

Tamsayılara hashing uygulamak için en son teknoloji, çarpma vardiyası Dietzfelbinger ve ark. 1997'de.^[8] Modüler aritmetikten kaçınarak, bu yöntemin uygulanması çok daha kolaydır ve ayrıca pratikte önemli ölçüde daha hızlı çalışır (genellikle en az dört faktör ile)^[9]). Şema, bölme sayısının ikinin bir üssü olduğunu varsayar, ${ displaystyle m = 2 ^ {M}}$. İzin Vermek ${ displaystyle w}$ bir makine kelimesindeki bit sayısı olabilir. Daha sonra hash fonksiyonları tek pozitif tamsayılar üzerinden parametrik hale getirilir ${ displaystyle a <2 ^ {w}}$ (bir kelimeye uyan ${ displaystyle w}$ bitler). Değerlendirmek ${ displaystyle h_ {a} (x)}$, çarpmak ${ displaystyle x}$ tarafından ${ displaystyle a}$ modulo ${ displaystyle 2 ^ {w}}$ ve sonra yüksek düzeni koru ${ displaystyle M}$ karma kodu olarak bitler. Matematiksel gösterimde bu

${ displaystyle h_ {a} (x) = (a cdot x , , { bmod {,}} 2 ^ {w}) , , mathrm {div} , , 2 ^ { wM}}$

ve uygulanabilir C benzeri programlama dilleri

${ displaystyle h_ {a} (x) =}$ (size_t) (a * x) >> (w-M)

Bu şema yapar değil tekdüze fark özelliğini karşılar ve yalnızca ${ displaystyle 2 / m}$-neredeyse evrensel; herhangi ${ displaystyle x neq y}$, ${ displaystyle Pr {h_ {a} (x) = h_ {a} (y) } leq 2 / m}$.

Karma işlevinin davranışını anlamak için, eğer ${ displaystyle balta { bmod {2}} ^ {w}}$ ve ${ displaystyle ay { bmod {2}} ^ {w}}$ aynı en yüksek 'M' bitlerine sahipse ${ displaystyle a (x-y) { bmod {2}} ^ {w}}$ en yüksek M bit olarak 1'lerin veya tüm 0'ların hepsine sahiptir ( ${ displaystyle balta { bmod {2}} ^ {w}}$ veya ${ displaystyle ay { bmod {2}} ^ {w}}$ daha büyüktür). ${ displaystyle x-y}$ pozisyonda görünür ${ displaystyle w-c}$. Dan beri ${ displaystyle a}$ rastgele bir tek tamsayıdır ve tek tamsayıların tersi yüzük ${ displaystyle Z_ {2 ^ {w}}}$bunu takip eder ${ displaystyle a (x-y) { bmod {2}} ^ {w}}$ arasında eşit olarak dağıtılacak ${ displaystyle w}$-konumda en az anlamlı ayarlanmış bit ile bit tamsayıları ${ displaystyle w-c}$. Bu bitlerin hepsinin 0 veya tüm 1 olma olasılığı bu nedenle en fazla ${ displaystyle 2/2 ^ {M} = 2 / m}$Öte yandan, eğer ${ displaystyle c$, sonra daha yüksek M bitleri ${ displaystyle a (x-y) { bmod {2}} ^ {w}}$ hem 0 hem de 1 içerir, bu nedenle ${ displaystyle h (x) neq h (y)}$. Son olarak, eğer ${ displaystyle c = M}$ sonra biraz ${ displaystyle w-M}$ nın-nin ${ displaystyle a (x-y) { bmod {2}} ^ {w}}$ 1 ve ${ displaystyle h_ {a} (x) = h_ {a} (y)}$ eğer ve sadece bitlerse ${ displaystyle w-1, ldots, w-M + 1}$ 1, bu da olasılıkla ${ displaystyle 1/2 ^ {M-1} = 2 / m}$.

Bu analiz, örnekte de görülebileceği gibi sıkıdır ${ displaystyle x = 2 ^ {w-M-2}}$ ve ${ displaystyle y = 3x}$. Gerçekten 'evrensel' bir hash işlevi elde etmek için, çarpma-ekleme-değiştirme şeması kullanılabilir.

${ displaystyle h_ {a, b} (x) = ((balta + b) { bmod {2}} ^ {w}) , mathrm {div} , 2 ^ {w-M}}$

hangisinde uygulanabilir C benzeri programlama dilleri

${ displaystyle h_ {a, b} (x) =}$ (size_t) (a * x + b) >> (w-M)

nerede ${ displaystyle a}$ rastgele tek pozitif bir tamsayıdır ${ displaystyle a <2 ^ {w}}$ ve ${ displaystyle b}$ rastgele negatif olmayan bir tamsayıdır ${ displaystyle b <2 ^ {w-M}}$. Bu seçimlerle ${ displaystyle a}$ ve ${ displaystyle b}$, ${ displaystyle Pr {h_ {a, b} (x) = h_ {a, b} (y) } leq 1 / m}$ hepsi için ${ displaystyle x not equiv y { pmod {2 ^ {w}}}}$.^[10] Bu, İngilizce makaledeki yanlış çeviriden biraz ama önemli ölçüde farklıdır.^[11]

Hashing vektörleri

Bu bölüm, makine kelimelerinin sabit uzunlukta bir vektörüne hashing uygulamakla ilgilidir. Girişi bir vektör olarak yorumlayın ${ displaystyle { bar {x}} = (x_ {0}, noktalar, x_ {k-1})}$ nın-nin ${ displaystyle k}$ makine kelimeleri (tamsayıları ${ displaystyle w}$ her biri bit). Eğer ${ displaystyle H}$ tek tip farklılık özelliğine sahip evrensel bir ailedir, aşağıdaki aile (Carter ve Wegman'a dayanmaktadır.^[1]) ayrıca tekdüze fark özelliğine sahiptir (ve dolayısıyla evrenseldir):

${ displaystyle h ({ çubuğu {x}}) = sol ( toplamı _ {i = 0} ^ {k-1} h_ {i} (x_ {i}) sağ) , { bmod { ~}} m}$her biri nerede ${ displaystyle h_ {i} H}$ bağımsız olarak rastgele seçilir.

Eğer ${ displaystyle m}$ ikinin gücüdür, biri toplamı özel veya ile değiştirilebilir.^[12]

Pratikte, eğer çift duyarlıklı aritmetik mevcutsa, bu, hash fonksiyonlarının çok-vardiyalı hash ailesi ile somutlaştırılır.^[13] Karma işlevini bir vektörle başlatın ${ displaystyle { bar {a}} = (a_ {0}, noktalar, a_ {k-1})}$ rastgele garip tamsayılar açık ${ displaystyle 2w}$ her biri bit. O zaman bölme sayısı ${ displaystyle m = 2 ^ {M}}$ için ${ displaystyle M leq w}$:

${ displaystyle h _ { bar {a}} ({ bar {x}}) = sol ({ büyük (} toplam _ {i = 0} ^ {k-1} x_ {i} cdot a_ {i} { büyük)} ~ { bmod {~}} 2 ^ {2w} right) , , mathrm {div} , , 2 ^ {2w-M}}$.

Pratikte kabaca iki kat hızlanma anlamına gelen çarpma sayısını yarıya indirmek mümkündür.^[12] Karma işlevini bir vektörle başlatın ${ displaystyle { bar {a}} = (a_ {0}, noktalar, a_ {k-1})}$ rastgele garip tamsayılar açık ${ displaystyle 2w}$ her biri bit. Aşağıdaki hash ailesi evrenseldir:^[14]

${ displaystyle h _ { bar {a}} ({ bar {x}}) = sol ({ Büyük (} toplamı _ {i = 0} ^ { lceil k / 2 rceil} (x_ { 2i} + a_ {2i}) cdot (x_ {2i + 1} + a_ {2i + 1}) { Büyük)} { bmod {~}} 2 ^ {2w} sağ) , , mathrm {div} , , 2 ^ {2w-M}}$.

Çift kesinlikli işlemler mevcut değilse, girdi yarım kelimelerin bir vektörü olarak yorumlanabilir (${ displaystyle w / 2}$-bit tamsayılar). Algoritma daha sonra kullanacak ${ displaystyle lceil k / 2 rceil}$ çarpımlar, nerede ${ displaystyle k}$ vektördeki yarım kelimelerin sayısıdır. Bu nedenle, algoritma, girdi kelimesi başına bir çarpma "hızında" çalışır.

Aynı şema, bitlerini bayt vektörleri olarak yorumlayarak tamsayılara hashing uygulamak için de kullanılabilir. Bu varyantta vektör tekniği olarak bilinir tablo karması ve çarpma tabanlı evrensel hashing şemalarına pratik bir alternatif sağlar.^[15]

Yüksek hızda güçlü evrensellik de mümkündür.^[16] Karma işlevini bir vektörle başlatın ${ displaystyle { bar {a}} = (a_ {0}, noktalar, a_ {k})}$ rastgele tamsayılar ${ displaystyle 2w}$ bitler. Hesaplama

${ displaystyle h _ { bar {a}} ({ bar {x}}) ^ { mathrm {strong}} = (a_ {0} + sum _ {i = 0} ^ {k-1} a_ {i + 1} x_ {i} { bmod {~}} 2 ^ {2w}) , , mathrm {div} , , 2 ^ {w}}$.

Sonuç son derece evrenseldir ${ displaystyle w}$ bitler. Deneysel olarak, son Intel işlemcilerde bayt başına 0.2 CPU döngüsünde çalıştığı bulundu. ${ displaystyle w = 32}$.

Hashing dizeleri

Bu, hashing a değişken boyutlu makine kelimelerin vektör. Dizenin uzunluğu küçük bir sayı ile sınırlanabiliyorsa, yukarıdan vektör çözümünü kullanmak en iyisidir (kavramsal olarak üst sınıra kadar vektörü sıfırlarla doldurmak). Gerekli alan, dizenin maksimum uzunluğu, ancak değerlendirme süresi ${ displaystyle h (s)}$ sadece uzunluğu ${ displaystyle s}$. Dizide sıfırlar yasak olduğu sürece, evrenselliği etkilemeden karma işlevi değerlendirilirken sıfır doldurma göz ardı edilebilir.^[12] Dizede sıfırlara izin veriliyorsa, doldurmadan önce tüm dizelere hayali bir sıfır olmayan (ör. 1) karakter eklemenin en iyisi olacağını unutmayın: bu, evrenselliğin etkilenmemesini sağlayacaktır.^[16]

Şimdi hash yapmak istediğimizi varsayalım ${ displaystyle { bar {x}} = (x_ {0}, noktalar, x _ { ell})}$, nerede iyi bir sınır ${ displaystyle ell}$ önceden bilinmemektedir. Tarafından önerilen evrensel bir aile ^[13] dizeyi ele alır ${ displaystyle x}$ bir polinom modülünün katsayıları olarak büyük bir asal. Eğer ${ displaystyle x_ {i} [u]}$, İzin Vermek ${ displaystyle p geq max {u, m }}$ asal olun ve şunları tanımlayın:

${ displaystyle h_ {a} ({ bar {x}}) = h _ { mathrm {int}} sol ({ büyük (} toplamı _ {i = 0} ^ { ell} x_ {i} cdot a ^ { ell -i} { büyük)} { bmod {~}} p sağ)}$, nerede ${ displaystyle a [p]}$ tekdüze rastgele ve ${ displaystyle h _ { mathrm {int}}}$ evrensel bir aile eşleme tamsayı alanından rastgele seçilir ${ displaystyle [p] mapsto [m]}$.

Modüler aritmetiğin özelliklerini kullanarak, yukarıdaki büyük dizeler için büyük sayılar üretmeden aşağıdaki gibi hesaplanabilir:^[17]

uint karma(Dize x, int a, int p)	uint h = BAŞLANGIÇ DEĞERİ	için (uint ben=0 ; ben < x.uzunluk ; ++ben)		h = ((h*a) + x[ben]) mod p	dönüş h

Bu Rabin-Karp haddeleme hash dayanmaktadır doğrusal eşleşik üreteç.^[18]Yukarıdaki algoritma şu şekilde de bilinir: Çarpımsal karma işlevi.^[19] Uygulamada, mod operatör ve parametre p tamsayının taşmasına izin verilerek tamamen önlenebilir, çünkü mod (Max-Int-Value + 1) birçok programlama dilinde. Aşağıdaki tablo başlatmak için seçilen değerleri göstermektedir h ve a bazı popüler uygulamalar için.

İki dizeyi düşünün ${ displaystyle { bar {x}}, { bar {y}}}$ ve izin ver ${ displaystyle ell}$ uzun olanın uzunluğu; analiz için, kısa dizge kavramsal olarak uzunluğa kadar sıfırlarla doldurulur ${ displaystyle ell}$. Uygulamadan önce bir çarpışma ${ displaystyle h _ { mathrm {int}}}$ ima ediyor ki ${ displaystyle a}$ katsayıları olan bir polinomun köküdür ${ displaystyle { çubuğu {x}} - { çubuğu {y}}}$. Bu polinom en fazla ${ displaystyle ell}$ kökler modulo ${ displaystyle p}$, dolayısıyla çarpışma olasılığı en fazla ${ displaystyle ell / p}$. Rastgele çarpışma olasılığı ${ displaystyle h _ { mathrm {int}}}$ toplam çarpışma olasılığını ${ displaystyle { frac {1} {m}} + { frac { ell} {p}}}$. Böylece, asal ${ displaystyle p}$ karma dizelerin uzunluğuna kıyasla yeterince büyük, aile evrensele çok yakındır (içinde istatistiksel mesafe ).

Bilinmeyen uzunluktaki dizeleri sabit uzunluklu karma değerlere hash etmek için kullanılan diğer evrensel karma işlevi aileleri şunları içerir: Rabin parmak izi ve Buzhash.

Modüler aritmetikten kaçınmak

Modüler aritmetiğin hesaplama cezasını azaltmak için pratikte üç numara kullanılır:^[12]

1. Biri asal olanı seçer ${ displaystyle p}$ ikiye yakın olmak, örneğin Mersenne asal. Bu, aritmetik modüle izin verir ${ displaystyle p}$ Bölünmeden uygulanacak (toplama ve kaydırma gibi daha hızlı işlemler kullanılarak). Örneğin, modern mimariler üzerinde çalışılabilir ${ displaystyle p = 2 ^ {61} -1}$, süre ${ displaystyle x_ {i}}$'ler 32 bit değerlerdir.
2. Bloklara vektör hashlemesi uygulanabilir. Örneğin, biri dizenin her 16 kelimelik bloğuna vektör hashingi uygular ve ${ displaystyle lceil k / 16 rceil}$ Sonuçlar. Daha yavaş dizi karması önemli ölçüde daha küçük bir vektöre uygulandığından, bu esasen vektör karması kadar hızlı olacaktır.
3. Bölen olarak ikinin üssü seçilerek aritmetik modülo ${ displaystyle 2 ^ {w}}$ bölünmeden uygulanacak (daha hızlı operasyonlar kullanılarak biraz maskeleme ). NH hash-function ailesi bu yaklaşımı alır.

Ayrıca bakınız

• K'den bağımsız hashing
• Rolling hashing
• Tablolama karması
• Minimum bağımsızlık
• Evrensel tek yönlü hash işlevi
• Düşük tutarsızlık dizisi
• Mükemmel hashing

Referanslar

daha fazla okuma

• Knuth, Donald Ervin (1998). Bilgisayar Programlama Sanatı, Cilt. III: Sıralama ve Arama (3. baskı). Okuma, Kitle; Londra: Addison-Wesley. ISBN  0-201-89685-0.

Dış bağlantılar

• Açık Veri Yapıları - Bölüm 5.1.1 - Çarpımlı Karma Oluşturma, Pat Morin