Java HashMap çarpışmayı algılıyor

Question

Java Hash-map'deki çarpışmayı algılamanın bir yolu var mı? Herhangi biri, çarpışmaların çoğunun gerçekleşebileceği bazı durumlara işaret edebilir. Elbette bir nesne için karma kodunu geçersiz kılarsanız ve basitçe bir sabit değer çarpışması döndürürseniz emin olursunuz. Bu konuda konuşmuyorum. Daha önce bahsettiğim diğer tüm durumların ne olduğunu bilmek istiyorum. varsayılan hashcode uygulaması değiştirilmeden.

Answer 1

Bu tür şeyleri karşılaştırmak için bir proje hazırladım: http://code.google.com/p/hashingbench/ (Zincirleme, açık adresleme ve çiçek filtreleri içeren karma işler için). Hashtable fonksiyonu (O proje içinde dediğimiz gibi ya da "karıştırma")

dışında hashCode anahtarın() itibaren, sen "bulaşması" bilmemiz gerekir. this list itibaren HashMap en bulaşması fonksiyonu eşdeğerdir: scramble(k1.hashCode()) == scramble(k2.hashCode()): Yani bir çarpışma bir HashMap meydana gelmesi için

public int scramble(int h) { 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

, gerekli ve yeterli koşul şudur.k1.hashCode() == k2.hashCode() (aksi takdirde, bulaşma/fonksiyonu şifreleme bir fonksiyonu olmadığı olurdu) eğer bir yeterli yüzden değil gerekli koşul çarpışma meydana gelmesi için Bu, her zaman doğrudur.

Düzenleme: Aslında yukarıda gerekli ve yeterli koşul compress(scramble(k1.hashCode())) == compress(scramble(k2.hashCode())) olmalıydı - compress işlevi bir tamsayı alır ve N kovalar sayıdır {0, ..., N-1}, onu eşler, bu yüzden temelde bir kova seçer. Genellikle, bu basit bir şekilde hash % N olarak uygulanır veya karma boyut ikiye eşit olduğunda (ve aslında ikiye çarpabilen boyutta güç elde etmek için bir motivasyon), hash & N (daha hızlı). ("sıkıştır", Goodrich ve Tamassia'nın bu adımı tanımlamak için kullandığı addır; Data Structures and Algorithms in Java). Sloganlığımı saptamak için ILMTitan'a git.

Diğer hashtable uygulamaları (ConcurrentHashMap, IdentityHashMap, vb.) Başka gereksinimlere sahiptir ve başka bir bulaşma/karıştırma işlevi kullanmaktadır, bu nedenle hangisini konuştuğunuzu bilmeniz gerekir.

(Örneğin, HashMap'in bulaşma işlevi yerine getirildi çünkü insanlar HashMap'in eski, karma, Hashme'nin iki masa üstü uygulaması için en kötü türde hashCode() nesnelerine sahip nesneler kullanıyordu. Bir kova seçmek için kullanılan düşük sıralı bitlerde - biraz ya da hiç değil - örneğin new Integer(1 * 1024), new Integer(2 * 1024) *, vs. Gördüğünüz gibi, HashMap'in smear fonksiyonu tüm bitlerini tüm bitleri etkilemeye çalışır. düşük sipariş bitleri).

Bunların hepsi, ortak durumlarda iyi çalışma anlamına gelir - belirli bir durum, sistemin hashCode() öğelerini devralan nesnelerdir.

PS: Gerçekte, uygulayıcıların bulama işlevini eklemeye zorlayan kesinlikle çirkin durum, Floats/Doubles'ın hashCode() öğesi ve değerlerin anahtarları olarak kullanımıdır: 1.0, 2.0, 3.0, 4.0 ..., hepsi aynı (sıfır) düşük dereceli bitlere sahip. Bu, ilgili eski hata raporu: Ben IMO iyi bakın http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4669519

Answer 2

Basit örnek: Long hashing. Açıkçası, 64 bit giriş ve sadece 32 bit çıktı vardır. Long karması olması belgelenmiştir:

(int)(this.longValue()^(this.longValue()>>>32)) 

yani o yanyana sıkışmış iki int değerlerini hayal ve bunları XOR.

Yani bütün bunlar 0'a bir hashcode sahip olacaktır:

0 
1L | (1L << 32) 
2L | (2L << 32) 
3L | (3L << 32) 

vb

Bunun "çarpışmaların çok sayıda" olarak sayılır mı bilmiyorum ama çarpışmalar olan bir örnek üretimi kolay.

Açıkçası orada çarpışmalar olacak 2'den fazla olası değerleri vardır, ancak birçok durumda ürettikleri zor konum herhangi karması. Örneğin, sadece ASCII değerlerini kullanarak String üzerinde karma çarpışmalar gördüğümde, bunların üretilmesi biraz daha zor.

Answer 3

diğer iki cevabı ama sadece en iyi yolu HashMap içinde hashCode() davranacağını aslında büyük bir sayı oluşturmak için ne kadar iyi test etmek paylaşmak istedim Sınıfınızdaki nesneleri, anahtar olarak HashMap uygulamasına yerleştirin ve CPU ve bellek yükünü test edin. 1 veya 2 milyon giriş, ölçülmesi gereken iyi bir sayıdır, ancak beklenen Harita boyutlarınızı test ederseniz en iyi sonuçları alırsınız.

Sadece karma işlevinden şüphe ettiğim bir sınıfa baktım. Bu yüzden, bir HashMap'i bu tip rastgele nesnelerle ve çarpışma sayısını test etmeye karar verdim. İnceleme altındaki sınıfın iki hashCode() uygulamasını test ettim. Bu yüzden HashMap'in çarpışma sayısını saymak için HashMap'in openjdk uygulamasının en alt kısmında gördüğünüz sınıfta yazdım (bkz. countCollidingEntries()). Bunların tüm karmaların çarpışmalarını değil, girişleri tutan dizideki çarpışmaların olmadığını unutmayın. Dizi dizini hash & (length-1) olarak hesaplanır, yani bu dizinin boyutu kısa olduğu için, daha fazla çarpışma olur. Bu dizinin boyutu initialCapacity ve HashMap'un loadFactor'una bağlıdır (put() daha fazla veri olduğunda artabilir).

Sonunda bu sayılara bakmanın pek mantıklı olmadığını düşündüm. HashMap'in kötü hashCode() yöntemiyle daha yavaş olması gerçeği, yalnızca Harita üzerinden verilerin eklenmesi ve alınmasıyla, hangi hashCode() uygulamasının daha iyi olduğunu bildiğiniz anlamına gelir.

public class TestHashMap extends HashMap { 

    public TestHashMap(int size) { 
     super(size); 
    } 

    public TestHashMap() { 
     super(); 
    } 

    public int countCollidingEntries() { 
     def fs = this.getClass().getSuperclass().getDeclaredFields(); 
     def table; 
     def count =0 ; 
     for (java.lang.reflect.Field field: fs) { 
     if (field.getName() == "table") { 
      field.setAccessible(true); 
      table = field.get(super); 
      break; 
     } 
     } 
     for(Object e: table) { 
     if (e != null) { 
      while (e.next != null) { 
       count++ 
       e = e.next; 
      } 
     } 
     } 
     return count; 
    } 
}