OpenJDK'nın yeniden şekillendirme mekanizması

Question

OpenJDK'nın yeniden şekillendirme mekanizması

Bu kodu http://www.docjar.com/html tarihinde Bir HashMap uygulaması aradıktan sonra /api/java/util/HashMap.java.html .

  264       static int hash(int h) {
  265          //This function ensures that hashCodes that differ only by
  266          //constant multiples at each bit position have a bounded
  267          //number of collisions (approximately 8 at default load factor).
  268           h ^= (h >>> 20) ^ (h >>> 12);
  269           return h ^ (h >>> 7) ^ (h >>> 4);
  270       }

Birileri bunu aydınlatabilir mi? Yorum bize bu kodun neden burada olduğunu ancak bunun kötü bir karma değerini nasıl artırdığını ve konumların sınırlı sayıda kişiyi nasıl sınırlandırdığını garanti ettiğini anlamak istiyorum. çarpışmalar . Bu sihirli sayılar ne anlama geliyor?

18

katma 27 Ekim 2011 en 08:34 yazar c_maker düzenlendi 28 Ekim 2011 en 04:56

Görünümler: 16

kaynak

ro ru fr es pt de hi bn ar kk

1 cevap

yazar Affe · Answer 1 · 2011-10-27T08:50Z

Herhangi bir anlam ifade edebilmesi için HashMap'in eşyaları kovalara nasıl tahsis ettiği anlayışı ile birleştirilmelidir. Bu, bir kova endeksinin seçildiği önemsiz fonksiyondur:

static int indexFor(int h, int length) {
    return h & (length-1);
}

Öyleyse görüyorsunuz ki, varsayılan masa boyutu 16 ile, sadece hash'ın en az 4 önemli bitinin aslında kovaları ayırmak için önemli olduğunu! (16 - 1 = 15, hash'ı 1111 b ile maskeler)

Eğer hashCode fonksiyonunuz geri dönerse bu açıkça kötü bir haber olabilir:

10101100110101010101111010111111

01111100010111011001111010111111

11000000010100000001111010111111
//etc etc etc

Böyle bir karma işlevi büyük olasılıkla yazarı tarafından görünen herhangi bir şekilde "kötü" olmaz. Ancak, haritayı kova ayırma yöntemiyle birleştirirseniz, patlama, MapFail (tm).

H'nin 32 bitlik bir sayı olduğunu aklınızda tutarsanız, bunlar sihir sayıları değildir. Sistematik olarak sayının en anlamlı bitlerini en az anlamlı bitlere doğru xoring ediyor. Amaç, ikili olarak görüntülendiğinde, "her yerde" her yerde gerçekleşen sayıdaki "farklılıklar", en az anlamlı bitlerde görünür hale gelmesidir.

Çarpışmalar sınırlanır çünkü aynı ilgili LSB'lere sahip farklı sayıların sayısı artık önemli ölçüde sınırlıdır, çünkü ikili gösterimde herhangi bir yerde meydana gelen herhangi bir fark, kovalama için önemli olan bitlere sıkıştırılır.