Cuckoo hashing'de "yeni karma işlevler" nelerdir?

Question

Ben Pagh ve Rodle gelen karma guguklu hakkında okuyorum ve bu paragrafın anlamını anlayamıyorum.

O Şek bu süreç, döngüler olduğunu ortaya çıkabilir 1 (b) '. Bu nedenle yineleme sayısı, Kısım 2.3'te belirtilecek bir "MaxLoop" değeri ile arasında belirtilir. Bu yineleme sayısına ulaşıldığında, , yeni hash işlevlerini kullanarak tablolardaki tuşları yeniden işler ve yuva olmayan anahtarı yerleştirmek için 'u bir kez daha deneyin. Rehashing için yeni tablolar tahsis etmenize gerek yoktur: Tabloda planlanan konumlarında bulunmayan tüm tuşlara tuşlarını silmek ve uygulamak için tablolarını kullanabiliriz.

yeni özet fonksiyonlarını kullanılarak ne demek istiyor

?
Ekleme algoritmasında tablo yeniden boyutlandırılır. Bir şekilde kullanmak için bir karma fonksiyonlar havuzumuz olmalı mı? Bu havuzu nasıl yaratıyoruz?

Answer 1

Evet, aynen söyledikleri gibi yeni karma işlevleri bekliyorlar. Neyse ki, yeni bir algoritma yığını gerektirmiyor, mevcut veri kümenizde sadece biraz farklı karma davranışlar var.

Kağıdın bölüm 2.1 ve sonra Ek A'ya bakın. Rastgele universal hash functions yapısını ele alır.

Basit, umut verici bir örnek, istediğiniz bayt bloklarında çalışan bazı normal karma işleviniz olduğunu varsayalım. Biz buna H(x) diyoruz. Yeni, biraz farklı karma işlevleri H_n(x) bir aile üretmek için kullanmak istersiniz. Peki, H(x) iyi ve gereksinimleriniz zayıfsa, H_n(x) = H(concat(n,x)) tanımlayabilirsiniz. H_n(x)'un davranışları hakkında güçlü garantileriniz yok, ancak çoğunun farklı olmasını beklersiniz.