Çarpışmaya neden olan bit modelinin özelliği nedir?

Question

Java'nın karma tuşları here
rasgeleleştirme yaklaşımı hakkında okumuştum. Görünüşe göre bu fikir, alt bitlerin dağıtıma yardımcı olmak için "rastgele" olduklarından emin olmaktır ancak bunu daha fazla anlamaya çalışıyorum.
Yani 10 nolu bir tablomuz varsa, o zaman 0, 10, 20, 30, 40 vb. Sayıların tümü kova 0'a düşer, 1,11,21,31 sayıları kepçeye 1 vs. düşer (modulo 10 kullanarak) .
Bit desenlerini değiştirmek, bunların tümünü kova 0'a gitmek yerine farklı kovalara yönlendirebilirsiniz.
Ancak, net olmayan şey, düşük sipariş bitlerinin bunu etkilemesini sağlayan özelliktir ve rastgele hale getirmemiz gerekir. onlar. Yani elimizde:

0000 0000 (0) 
0000 1010 (10) 
0001 0100 (20) 
0001 1110 (30) 
0010 1000 (40) 

aynı yuvaya yerleştirilen bunları yapar düşük değerli bitlerden düzenlilik nedir?
Belki de aşağıda kafam karıştı mı? Anlayışım, çarpışmalara neden olan düşük sıralı bitlerde bir düzenlilik olduğunu ve

Answer 1

'u telafi etmek için rasgele hale getirmeye çalıştığımız yönündedir. Bazı karma işlevleri düşük sipariş bitlerini rasgele hale getirmek için gerçekten kötü bir iş yapar.

Klasik adreslerden biri, nesne başvuruları için bir karma olarak (C dilinde "işaretçiler") donanım adreslerinin kullanılmasıdır, aksi takdirde nesne kimliği için benzersiz bir sayıyı ucuza almak için makul bir yol olacaktır. Bu, karma tablosunun kova sayısı bir asal sayı olsa, ancak kovaların sayısı her zaman 2'nin gücü olduğu karma uygulamaları için iyi çalışır, tüm karmaların 8 ile bölünebilir olması çoğu kovaların boş olduğu anlamına gelir.

Bu olağanüstü bir durumdur, ancak karma olan verilerin düzgün bir şekilde dağıtılmaması ve karma işlevinin düşük sipariş bitlerini koruma eğiliminde olduğu her zaman, kova atamalarında bazı sapmalar bulacaksınız.

Answer 2

Java'nın HashMap'i, iki yetki olan bir karma tablo boyutu kullanır. Kalan/modulo işlemini her zamanki gibi sıkıştırma işlevi olarak kullanırsanız, karma kodun en düşük bitlerini kova dizini olarak alırsınız. Eğer karma kodlar bir iktidarın iki katı olacaksa, en düşük bitlerin bir kısmı her zaman sıfır olacaktır ve siz de mevcut kovaların bir kısmını kullanarak sonuçlanırsınız.

Beton örneği: 32 kovaya sahip olduğunuzu ve karma kodlarının 8'in katları olduğunu varsayalım. Tablo, kodun yalnızca 5 en az anlamlı bitini kullanır ve bunların 3'ü her zaman 0'dır. Bu nedenle, yalnızca 2 bit kepçeyi belirler, ve sadece 4 32 kovalar kullanın: o kadar çok değil, böylece bit karıştırır:

XXXXXX00000 -> bucket 0 
XXXXXX01000 -> bucket 8 
XXXXXX10000 -> bucket 16 
XXXXXX11000 -> bucket 24 

Neyse şeyler Java HashMap hash kodu sadece düşük bit kullanmadığı için bu kötü değildir Yanlışlıkla kötü senaryolar üretmek kolaydır. Bu konuda net değilim

/** 
* Applies a supplemental hash function to a given hashCode, which 
* defends against poor quality hash functions. This is critical 
* because HashMap uses power-of-two length hash tables, that 
* otherwise encounter collisions for hashCodes that do not differ 
* in lower bits. Note: Null keys always map to hash 0, thus index 0. 
*/ 
static int hash(int h) { 
    // This function ensures that hashCodes that differ only by 
    // constant multiples at each bit position have a bounded 
    // number of collisions (approximately 8 at default load factor). 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
}