Neden demet(set([1,"bir","b","c","z","f"])) == demet(set(["a","b","c","z","f",1])) 85% karma rasgele zamanın etkin?

SORU

1 EKİM 2014, ÇARŞAMBA

Neden demet(set([1,"bir","b","c","z","f"])) == demet(set(["a","b","c","z","f",1])) 85% karma rasgele zamanın etkin?

Given Zero Piraeus' answer to another question, o var

x = tuple(set([1, "a", "b", "c", "z", "f"]))
y = tuple(set(["a", "b", "c", "z", "f", 1]))
print(x == y)

Baskılar hash randomization �'i etkin True. Neden 85%?

CEVAP

1 EKİM 2014, ÇARŞAMBA

Bu soru herhangi bir okuyucu hem okudum kabul ediyorum:

Not ilk şey karma rasgele tercüman-up başlatmak karar verdi.

Her harfin karma önemli olan tek şey eğer bir çarpışma düzeni etkilenecektir) ise her iki takım için de aynı olacak.

İkinci bağlantı kesintiler bu ayarlar için yedekleme dizi uzunluğu 8'de başlıyor biliyoruz:

_ _ _ _ _ _ _ _

İlk durumda, biz Ekle 12**:

_ 1 _ _ _ _ _ _

ve eklemek gerisi sonra:

α 1 ? ? ? ? ? ?

O zaman boyutu 32 gerekecektir

    1 can't collide with α as α is an even hash
  ↓ so 1 is inserted at slot 1 first
? 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

İkinci durumda, biz de Ekle sonuna:

? β ? ? ? ? ? ?

Ve Ekle 1 için deneyin:

    Try to insert 1 here, but will
  ↓ be rehashed if β exists
? β ? ? ? ? ? ?

Ve sonra İngiliz lirası olacaktır:

    Try to insert 1 here, but will
    be rehashed if β exists and has
  ↓ not rehashed somewhere else
? β ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

Yani yineleme emir farklı olup sadece beta var olup olmadığını bağlıdır.

Gurup şansı 5 harflerin herhangi 1 8 modül için karma şansınıve1 modül için karma 32.

1 modül için karma bir şey beri 32 de 1 32 yuvası, beş biri slot 1 deki şansı bulmak istiyoruz 8, modül dosyalar:

5 (number of letters) / 32 (number of slots)

5/32 0.15625, o kadar15.625% chance1 siparişlerin bir iki set yapılar arasında farklı olmak var.

Garip bir şekilde, bu Sıfır Pire ölçülen şey tam olarak bu değil.

1Technically bu belli bile değil. Biz gibi her biri 5 karma benzersiz yüzünden ne de doğrusal sondalama aslında biraz daha "durma" yapıların ortaya... ama olduğumuz için sadece bakmak ister tek bir slot işgal, bu değil aslında bizi etkiler.

Bunu Paylaş: