SORU
8 Mayıs 2011, Pazar


Neden boyutu 127 (prime) karma tablo için 128'den daha mı iyi?

Basit üniforma sağlama, diyelim ki, herhangi bir değer karma deliklerini içine haşhaş gibi aynı derecede. Neden büyüklükte bir tablo 127 ve 128 kullanmak daha mı iyi? Gerçekten 2 Sayı gücü ile sorun ne anlamıyorum. Ya aslında hiç fark etmez.

Bölünme yöntemini kullanırken, biz genellikle bazı değerleri önlemek m (tablo boyutu). Örneğin, m beri m 2, Bir güç olmamalı = 2^p , h(k) p en düşük mertebe k parçaları.

Hadi Olası öğeler sadece 1 ve 10000 arasında olduğu sanıyor ve 128 tablo boyutu seçtim. 127 nasıl daha iyi olabilir? Yani 128 2^6 (1000000) ve 127 0111111. Ne fark bu mu? Tüm sayılar karma (zaman), en düşük p-sipariş 127 k parçaları da olacak. Yanlış bir şey söyledim mi?

Gerçekten bu kadar kötü olduğunu anlayamıyorum bazı örnekler arıyorum. Şimdiden çok teşekkürler!

PS: farkındayım: Hash table: why size should be prime?

CEVAP
8 Mayıs 2011, Pazar


Tüm sayılar karma (zaman), en düşük p-sipariş 127 k parçaları da olacak.

Yanlış (ya da ben yanlış anladım). k % 127 k tüm bitleri bağlıdır. k % 128 7 en düşük bit bağlıdır.


DÜZENLEME:

1 ile 10.000 arasında mükemmel bir dağıtım varsa. 10,000 % 127 10,000 % 128 mükemmel küçük bir dağıtım bu dönecek. Tüm kova = 78 10,000 /128 (ya da 79) öğeleri içerir.

Eğer 1 ile 10.000 arasında bir dağıtım varsa, {x, 2x, 3x,..} ortaya daha sık çünkü önyargılı. Sonra Başbakan bir boyutu bu izah answer çok, çok daha iyi bir dağıtım verecektir. (X, tam olarak mükemmel boyut. sürece)

Böylece, yüksek bit (128 boyut kullanarak) keserek hiçbir sorun yokeğerdaha düşük bit dağılımı yeterince iyi. Ancak, kötü tasarlanmış gerçek veriler gerçek hash fonksiyonları ile, bu yüksek bit gerekir.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Ayite Atiwoto (superjiffrey)

    Ayite Atiwot

    29 EYLÜL 2010
  • esnathesinger

    esnathesinge

    6 NİSAN 2009
  • hockeywebcasts

    hockeywebcas

    31 EKİM 2012

İLGİLİ SORU / CEVAPLAR