Saya akan berasumsi bahwa setiap pembaca pertanyaan ini telah membaca keduanya:
Hal pertama yang perlu diperhatikan adalah bahwa pengacakan hash diputuskan pada saat penerjemah memulai.
Hash setiap huruf akan sama untuk kedua set, jadi satu-satunya hal yang penting adalah jika ada tabrakan (di mana urutan akan terpengaruh).
Dengan pengurangan dari tautan kedua itu, kita mengetahui bahwa susunan pendukung untuk set ini dimulai dari panjang 8:
_ _ _ _ _ _ _ _
Dalam kasus pertama, kami memasukkan 1
:
_ 1 _ _ _ _ _ _
lalu masukkan sisanya:
α 1 ? ? ? ? ? ?
Kemudian diulang ke ukuran 32:
1 can't collide with α as α is an even hash
↓ so 1 is inserted at slot 1 first
? 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
Dalam kasus kedua, kami memasukkan sisanya:
? β ? ? ? ? ? ?
Dan kemudian coba masukkan 1:
Try to insert 1 here, but will
↓ be rehashed if β exists
? β ? ? ? ? ? ?
Dan kemudian akan diulang:
Try to insert 1 here, but will
be rehashed if β exists and has
↓ not rehashed somewhere else
? β ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
Jadi apakah urutan iterasi berbeda hanya bergantung pada apakah β ada.
Peluang a β adalah peluang bahwa salah satu dari 5 huruf akan memiliki hash ke 1 modulo 8 dan hash hingga 1 modulo 32.
Karena apa pun yang memiliki hash ke 1 modulo 32 juga memiliki hash ke 1 modulo 8, kami ingin mencari peluang bahwa dari 32 slot, salah satu dari lima ada di slot 1:
5 (number of letters) / 32 (number of slots)
5/32 adalah 0,15625, jadi ada peluang 15,625% dari pesanan yang berbeda antara dua konstruksi yang ditetapkan .
Tidak terlalu aneh sama sekali, inilah yang diukur oleh Zero Piraeus.
¹ Secara teknis bahkan ini tidak jelas. Kami dapat menganggap setiap salah satu dari 5 hash secara unik karena pengulangan, tetapi karena penyelidikan linier sebenarnya lebih mungkin terjadi struktur "berkelompok" ... tetapi karena kami hanya melihat apakah satu slot terisi, ini tidak tidak benar-benar mempengaruhi kita.