Java HashMap performans optimizasyonu / alternatif

SORU

18 Kasım 2009, ÇARŞAMBA

Java HashMap performans optimizasyonu / alternatif

Büyük bir HashMap oluşturmak istiyorum ama put() performans yeterince iyi değil. Herhangi bir fikir?

Diğer veri yapısı önerilerinizi bekliyoruz ama Java Haritası arama özelliği istiyorum:

map.get(key)

Benim durumumda 26 milyon site ile bir harita oluşturmak istiyorum. Standart Java HashMap koymak hızını kullanarak olur dayanılmaz 2-3 milyon eklemeler sonra yavaş.

Ayrıca, eğer anahtarlar için farklı hash kod dağıtımları kullanarak yardımcı olabilir biliyor mu?

Hashcode benim yöntem:

byte[] a = new byte[2];
byte[] b = new byte[3];
...

public int hashCode() {
    int hash = 503;
    hash = hash * 5381   (a[0]   a[1]);
    hash = hash * 5381   (b[0]   b[1]   b[2]);
    return hash;
}

Ayrıca birleştirici özelliği eşit nesneler aynı hashcode sağlamak için kullanıyorum. Diziler aralığında değerler ile bayt 0 - 51. Değerler sadece bir kez ya da bir dizi kullanılır. Nesneleri bir dizi aynı değerleri içeriyorsa eşittir (ya da sırada) ve aynı b dizisi için de geçerli. {0,1} b = {45,12,33} ve {1,0} a = b = {33,45,12} eşittir.

DÜZENLEME, bazı notlar:

Bir kaç kişi karma harita veya diğer veri yapısı 26 milyon girdileri saklamak için kullanarak eleştirdi. Ben bu garip görünüyor neden göremiyorum. Bana klasik veri yapıları ve algoritmalar bir sorun gibi görünüyor. 26 milyon parça var ve hızlı bir şekilde onları içine yerleştirin ve onları bir veri yapısı aramak için güçlü olmak istiyorum: benim veri yapısı ve algoritmalar ver.
Varsayılan başlangıç kapasitesi ayarı HashMap için 26 milyon Javaazaltırperformans.
Bazı insanlar veritabanları, kesinlikle akıllı bir seçenek olduğu başka durumlarda kullanmayı önerdi. Ama ben gerçekten soran bir veri yapıları ve algoritmalar soru, tam bir veritabanı olurdu abartılı ve çok daha yavaş daha iyi bir çözüm datastructure (sonra tüm veritabanını sadece yazılım ama olurdu haberleşme ve muhtemelen hard disk gereklidir).

CEVAP

19 Kasım 2009, PERŞEMBE

Birçok kişi hashCode() yöntem suçlu olduğunu belirttim. Sadece 26 milyon farklı nesneler için yaklaşık 20.000 kodları üretiyor. Karma kova başına 1,300 nesneleri ortalama = çok ama çok kötü. Ancak eğer temel 52 sayı iki diziler çevirirsem her nesne için benzersiz bir hash kodu almak için garanti ediyorum:

public int hashCode() {       
    // assume that both a and b are sorted       
    return a[0]   powerOf52(a[1], 1)   powerOf52(b[0], 2)   powerOf52(b[1], 3)   powerOf52(b[2], 4);
}

public static int powerOf52(byte b, int power) {
    int result = b;
    for (int i = 0; i < power; i  ) {
        result *= 52;
    }
    return result;
}

Diziler yöntemleri eşit nesneler aynı karma kodu var hashCode() sözleşme yerine bunu sağlamak için sıralanır. 2,000,000 100,000 koyar, 100,000 ikinci bina ötede başına koyar sayısı ortalaması olduğu için eski yöntemi kullanarak:

Yeni yöntemi kullanarak verir:

Çok çok daha iyi. Eski yöntem yeni bir iyi bir işlem hacmi devam ederken çok hızlı bir şekilde kuyruklu kapalı.

Bunu Paylaş: