Saya ingin membuat HashMap yang besar tetapi put()kinerjanya tidak cukup baik. Ada ide?

Saran struktur data lainnya diterima, tetapi saya memerlukan fitur pencarian dari Peta Java:

map.get(key)

Dalam kasus saya, saya ingin membuat peta dengan 26 juta entri. Menggunakan Java HashMap standar, put rate menjadi sangat lambat setelah 2-3 juta penyisipan.

Juga, apakah ada yang tahu jika menggunakan distribusi kode hash yang berbeda untuk kunci dapat membantu?

Metode kode hash saya:

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;
}

Saya menggunakan properti asosiatif tambahan untuk memastikan bahwa objek yang sama memiliki kode hash yang sama. Array adalah byte dengan nilai dalam kisaran 0 - 51. Nilai hanya digunakan sekali dalam salah satu array. Objeknya sama jika array a berisi nilai yang sama (dalam urutan apa pun) dan hal yang sama berlaku untuk array b. Jadi a = {0,1} b = {45,12,33} dan a = {1,0} b = {33,45,12} adalah sama.

EDIT, beberapa catatan:

• Beberapa orang mengkritik penggunaan peta hash atau struktur data lain untuk menyimpan 26 juta entri. Saya tidak mengerti mengapa ini tampak aneh. Sepertinya masalah struktur data dan algoritme klasik bagi saya. Saya memiliki 26 juta item dan saya ingin dapat dengan cepat memasukkannya ke dalam dan mencarinya dari struktur data: beri saya struktur data dan algoritme.

• Menetapkan kapasitas awal Java HashMap default menjadi 26 juta menurunkan kinerja.

• Beberapa orang menyarankan untuk menggunakan database, dalam beberapa situasi lain yang pasti merupakan pilihan cerdas. Tapi saya benar-benar mengajukan pertanyaan tentang struktur data dan algoritme, database lengkap akan berlebihan dan jauh lebih lambat daripada solusi struktur data yang baik (setelah semua database hanyalah perangkat lunak tetapi akan memiliki komunikasi dan mungkin overhead disk).

Seperti yang ditunjukkan banyak orang hashCode() metode yang harus disalahkan. Itu hanya menghasilkan sekitar 20.000 kode untuk 26 juta objek berbeda. Artinya rata-rata 1.300 objek per ember hash = sangat sangat buruk. Namun jika saya mengubah dua array menjadi angka di basis 52, saya dijamin mendapatkan kode hash unik untuk setiap objek:

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;
}

Array diurutkan untuk memastikan metode ini memenuhi hashCode() kontrak bahwa objek yang sama memiliki kode hash yang sama. Dengan menggunakan metode lama, jumlah rata-rata put per detik di atas 100.000 put, 100.000 hingga 2.000.000 adalah:

168350.17
109409.195
81344.91
64319.023
53780.79
45931.258
39680.29
34972.676
31354.514
28343.062
25562.371
23850.695
22299.22
20998.006
19797.799
18702.951
17702.434
16832.182
16084.52
15353.083

Menggunakan metode baru memberikan:

337837.84
337268.12
337078.66
336983.97
313873.2
317460.3
317748.5
320000.0
309704.06
310752.03
312944.5
265780.75
275540.5
264350.44
273522.97
270910.94
279008.7
276285.5
283455.16
289603.25

Jauh lebih baik. Metode lama mundur dengan sangat cepat sementara yang baru mempertahankan hasil yang baik.

Satu hal yang saya perhatikan dalam hashCode()metode Anda adalah bahwa urutan elemen dalam array a[]dan b[]tidak penting. Dengan demikian (a[]={1,2,3}, b[]={99,100})akan memiliki nilai yang sama dengan (a[]={3,1,2}, b[]={100,99}). Sebenarnya semua kunci k1dan di k2mana sum(k1.a)==sum(k2.a)dan sum(k1.b)=sum(k2.b)akan mengakibatkan benturan. Saya sarankan untuk memberi bobot pada setiap posisi array:

hash = hash * 5381 + (c0*a[0] + c1*a[1]);
hash = hash * 5381 + (c0*b[0] + c1*b[1] + c3*b[2]);

di mana, c0, c1dan c3yang berbeda konstanta (Anda dapat menggunakan konstanta yang berbeda untuk bjika perlu). Itu akan meratakan hal-hal sedikit lebih banyak.

Untuk menguraikan Pascal: Apakah Anda memahami cara kerja HashMap? Anda memiliki beberapa slot di tabel hash Anda. Nilai hash untuk setiap kunci ditemukan, dan kemudian dipetakan ke entri dalam tabel. Jika dua nilai hash dipetakan ke entri yang sama - "benturan hash" - HashMap membuat daftar tertaut.

Tabrakan hash dapat mematikan kinerja peta hash. Dalam kasus ekstrim, jika semua kunci Anda memiliki kode hash yang sama, atau jika mereka memiliki kode hash yang berbeda tetapi semuanya dipetakan ke slot yang sama, maka peta hash Anda berubah menjadi daftar tertaut.

Jadi jika Anda melihat masalah kinerja, hal pertama yang akan saya periksa adalah: Apakah saya mendapatkan distribusi kode hash yang tampak acak? Jika tidak, Anda membutuhkan fungsi hash yang lebih baik. Nah, "lebih baik" dalam hal ini mungkin berarti "lebih baik untuk kumpulan data saya". Misalnya, Anda mengerjakan string, dan Anda mengambil panjang string untuk nilai hash. (Bukan cara kerja String.hashCode Java, tetapi saya hanya membuat contoh sederhana.) Jika string Anda memiliki panjang yang sangat bervariasi, dari 1 hingga 10.000, dan didistribusikan secara merata di seluruh rentang itu, ini bisa menjadi sangat bagus fungsi hash. Tetapi jika semua string Anda terdiri dari 1 atau 2 karakter, ini akan menjadi fungsi hash yang sangat buruk.

Edit: Saya harus menambahkan: Setiap kali Anda menambahkan entri baru, HashMap memeriksa apakah ini duplikat. Saat terjadi benturan hash, kunci masuk harus dibandingkan dengan setiap kunci yang dipetakan ke slot itu. Jadi dalam kasus terburuk di mana semua hash ke satu slot, kunci kedua dibandingkan dengan kunci pertama, kunci ketiga dibandingkan dengan # 1 dan # 2, kunci keempat dibandingkan dengan # 1, # 2, dan # 3 , dll. Pada saat Anda mencapai kunci # 1 juta, Anda telah melakukan lebih dari satu triliun perbandingan.

@ Oscar: Umm, saya tidak melihat bagaimana itu "tidak juga". Ini lebih seperti "biarkan saya menjelaskan". Tapi ya, memang benar bahwa jika Anda membuat entri baru dengan kunci yang sama dengan entri yang sudah ada, ini akan menimpa entri pertama. Itulah yang saya maksud ketika saya berbicara tentang mencari duplikat di paragraf terakhir: Setiap kali kunci hash ke slot yang sama, HashMap harus memeriksa apakah itu duplikat dari kunci yang ada, atau apakah mereka hanya di slot yang sama secara kebetulan dari fungsi hash. Saya tidak tahu bahwa itu adalah "inti" dari HashMap: Saya akan mengatakan bahwa "keseluruhan" adalah bahwa Anda dapat mengambil elemen dengan kunci dengan cepat.

Tapi bagaimanapun, itu tidak mempengaruhi "keseluruhan poin" yang saya coba buat: Ketika Anda memiliki dua kunci - ya, kunci yang berbeda, bukan kunci yang sama yang muncul lagi - itu memetakan ke slot yang sama dalam tabel , HashMap membuat daftar tertaut. Kemudian, karena harus memeriksa setiap kunci baru untuk melihat apakah itu benar-benar duplikat dari kunci yang ada, setiap upaya untuk menambahkan entri baru yang memetakan ke slot yang sama ini harus mengejar daftar tertaut yang memeriksa setiap entri yang ada untuk melihat apakah ini adalah duplikat dari kunci yang terlihat sebelumnya, atau jika itu adalah kunci baru.

Perbarui lama setelah posting asli

Saya baru saja mendapat suara positif untuk jawaban ini 6 tahun setelah posting yang membuat saya membaca ulang pertanyaan itu.

Fungsi hash yang diberikan dalam pertanyaan bukanlah hash yang bagus untuk 26 juta entri.

Ia menambahkan bersama a [0] + a [1] dan b [0] + b [1] + b [2]. Dia mengatakan nilai setiap byte berkisar dari 0 hingga 51, sehingga hanya memberikan (51 * 2 + 1) * (51 * 3 + 1) = 15.862 kemungkinan nilai hash. Dengan 26 juta entri, ini berarti rata-rata sekitar 1639 entri per nilai hash. Itu adalah banyak sekali benturan, membutuhkan banyak sekali pencarian berurutan melalui daftar tertaut.

OP mengatakan bahwa urutan yang berbeda dalam array a dan array b harus dianggap sama, yaitu [[1,2], [3,4,5]]. Sama dengan ([[2,1], [5,3,4] ]), dan untuk memenuhi kontrak mereka harus memiliki kode hash yang sama. Baik. Namun, ada lebih dari 15.000 kemungkinan nilai. Fungsi hash kedua yang diusulkannya jauh lebih baik, memberikan jangkauan yang lebih luas.

Meskipun seperti yang dikomentari orang lain, tampaknya fungsi hash tidak sesuai untuk mengubah data lain. Akan lebih masuk akal untuk "menormalkan" objek saat dibuat, atau meminta fungsi hash bekerja dari salinan array. Selain itu, menggunakan perulangan untuk menghitung konstanta setiap kali melalui fungsi tidak efisien. Karena hanya ada empat nilai di sini, saya akan menuliskannya

return a[0]+a[1]*52+b[0]*52*52+b[1]*52*52*52+b[2]*52*52*52*52;

yang akan menyebabkan kompilator melakukan kalkulasi sekali pada waktu kompilasi; atau memiliki 4 konstanta statis yang ditentukan di kelas.

Selain itu, draf pertama pada fungsi hash memiliki beberapa kalkulasi yang tidak melakukan apa pun untuk ditambahkan ke rentang keluaran. Perhatikan bahwa ia pertama kali menetapkan hash = 503 daripada mengalikan dengan 5381 bahkan sebelum mempertimbangkan nilai dari kelas. Jadi ... pada dasarnya dia menambahkan 503 * 5381 ke setiap nilai. Apa yang dicapai ini? Menambahkan konstanta ke setiap nilai hash hanya membakar siklus cpu tanpa menyelesaikan sesuatu yang berguna. Pelajaran di sini: Menambahkan kompleksitas ke fungsi hash bukanlah tujuannya. Tujuannya adalah untuk mendapatkan berbagai nilai yang berbeda, bukan hanya untuk menambah kompleksitas demi kompleksitas.

Ide pertama saya adalah memastikan Anda menginisialisasi HashMap dengan tepat. Dari JavaDocs untuk HashMap :

Sebuah instance dari HashMap memiliki dua parameter yang memengaruhi kinerjanya: kapasitas awal dan faktor beban. Kapasitas adalah jumlah keranjang dalam tabel hash, dan kapasitas awal hanyalah kapasitas pada saat tabel hash dibuat. Faktor beban adalah ukuran seberapa penuh tabel hash yang diperbolehkan sebelum kapasitasnya ditingkatkan secara otomatis. Ketika jumlah entri dalam tabel hash melebihi produk faktor beban dan kapasitas saat ini, tabel hash diulangi (yaitu, struktur data internal dibangun kembali) sehingga tabel hash memiliki kira-kira dua kali jumlah keranjang.

Jadi jika Anda memulai dengan HashMap yang terlalu kecil, maka setiap kali ukurannya perlu diubah, semua hash dihitung ulang ... yang mungkin Anda rasakan saat mencapai 2-3 juta titik penyisipan.

Saya menyarankan pendekatan bercabang tiga:

1. Jalankan Java dengan lebih banyak memori: java -Xmx256Mmisalnya untuk dijalankan dengan 256 Megabyte. Gunakan lebih banyak jika perlu dan Anda memiliki banyak RAM.

2. Cache nilai hash yang dihitung seperti yang disarankan oleh poster lain, jadi setiap objek hanya menghitung nilai hashnya satu kali.

3. Gunakan algoritme hashing yang lebih baik. Yang Anda posting akan mengembalikan hash yang sama di mana a = {0, 1} seperti di mana a = {1, 0}, semuanya sama.

Manfaatkan apa yang diberikan Java secara gratis.

public int hashCode() {
    return 31 * Arrays.hashCode(a) + Arrays.hashCode(b);
}

Saya cukup yakin ini memiliki peluang bentrok yang jauh lebih sedikit daripada metode hashCode Anda yang ada, meskipun itu tergantung pada sifat sebenarnya dari data Anda.

Masuk ke area abu-abu "on / off topic", tetapi perlu untuk menghilangkan kebingungan terkait saran Oscar Reyes bahwa lebih banyak tabrakan hash adalah hal yang baik karena mengurangi jumlah elemen di HashMap. Saya mungkin salah paham tentang apa yang dikatakan Oscar, tetapi sepertinya saya bukan satu-satunya: kdgregory, delfuego, Nash0, dan saya semua tampaknya memiliki pemahaman (mis) yang sama.

Jika saya mengerti apa yang dikatakan Oscar tentang kelas yang sama dengan kode hash yang sama, dia mengusulkan bahwa hanya satu contoh kelas dengan kode hash yang diberikan akan dimasukkan ke dalam HashMap. Misalnya, jika saya memiliki instance SomeClass dengan hashcode 1 dan instance kedua SomeClass dengan hashcode 1, hanya satu instance SomeClass yang dimasukkan.

Contoh Java pastebin di http://pastebin.com/f20af40b9 tampaknya menunjukkan dengan benar merangkum apa yang Oscar usulkan di atas.

Terlepas dari pemahaman atau kesalahpahaman, apa yang terjadi adalah contoh yang berbeda dari kelas yang sama tidak dimasukkan hanya sekali ke dalam HashMap jika mereka memiliki kode hash yang sama - tidak sampai ditentukan apakah kuncinya sama atau tidak. Kontrak kode hash mengharuskan objek yang sama memiliki kode hash yang sama; Namun, itu tidak mengharuskan objek yang tidak sama memiliki kode hash yang berbeda (meskipun ini mungkin diinginkan karena alasan lain) [1].

Contoh pastebin.com/f20af40b9 (yang dirujuk Oscar setidaknya dua kali) mengikuti, tetapi sedikit dimodifikasi untuk menggunakan pernyataan JUnit daripada printlines. Contoh ini digunakan untuk mendukung proposal bahwa kode hash yang sama menyebabkan benturan dan jika kelasnya sama, hanya satu entri yang dibuat (misalnya, hanya satu String dalam kasus khusus ini):

@Test
public void shouldOverwriteWhenEqualAndHashcodeSame() {
    String s = new String("ese");
    String ese = new String("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // AND equal
    assertTrue(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(2, map.size());

    assertEquals(2, map.get("ese"));
    assertEquals(3, map.get(some));

    assertTrue(s.equals(ese) && s.equals("ese"));
}

class SomeClass {
    public int hashCode() {
        return 100727;
    }
}

Namun, kode hash bukanlah cerita lengkapnya. Apa yang pastebin contoh mengabaikan adalah kenyataan bahwa kedua sdan esesama: mereka berdua string "ese". Jadi, memasukkan atau mendapatkan konten peta menggunakan satau eseatau "ese"sebagai kunci semuanya setara karenas.equals(ese) && s.equals("ese") .

Tes kedua menunjukkan bahwa adalah salah untuk menyimpulkan bahwa kode hash yang identik pada kelas yang sama adalah alasan kunci -> nilai s -> 1ditimpa ese -> 2ketika map.put(ese, 2)dipanggil dalam tes satu. Dalam pengujian kedua, sdan esemasih memiliki kode hash yang sama (sebagaimana diverifikasi oleh assertEquals(s.hashCode(), ese.hashCode());) DAN mereka adalah kelas yang sama. Namun, sdan esemerupakan MyStringinstance dalam pengujian ini, bukan Stringinstance Java - dengan satu-satunya perbedaan yang relevan untuk pengujian ini adalah sama: String s equals String esedalam pengujian satu di atas, sedangkan MyStrings s does not equal MyString esedalam pengujian dua:

@Test
public void shouldInsertWhenNotEqualAndHashcodeSame() {
    MyString s = new MyString("ese");
    MyString ese = new MyString("ese");
    // same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    // same class
    assertEquals(s.getClass(), ese.getClass());
    // BUT not equal
    assertFalse(s.equals(ese));

    Map map = new HashMap();
    map.put(s, 1);
    map.put(ese, 2);
    SomeClass some = new SomeClass();
    // still  same hash right?
    assertEquals(s.hashCode(), ese.hashCode());
    assertEquals(s.hashCode(), some.hashCode());

    map.put(some, 3);
    // what would we get?
    assertEquals(3, map.size());

    assertEquals(1, map.get(s));
    assertEquals(2, map.get(ese));
    assertEquals(3, map.get(some));
}

/**
 * NOTE: equals is not overridden so the default implementation is used
 * which means objects are only equal if they're the same instance, whereas
 * the actual Java String class compares the value of its contents.
 */
class MyString {
    String i;

    MyString(String i) {
        this.i = i;
    }

    @Override
    public int hashCode() {
        return 100727;
    }
}

Berdasarkan komentar selanjutnya, Oscar tampaknya membalikkan apa yang dia katakan sebelumnya dan mengakui pentingnya persamaan. Namun, tampaknya gagasan bahwa yang sama adalah yang penting, bukan "kelas yang sama", tidak jelas (penekanan dari saya):

Daftar dibuat hanya jika hashnya sama, tetapi kuncinya berbeda. Misalnya jika String memberikan kode hash 2345 dan dan Integer memberikan kode hash yang sama 2345, maka integer tersebut dimasukkan ke dalam daftar karena String. sama (Integer) salah. Tetapi jika Anda memiliki kelas yang sama (atau setidaknya .equals mengembalikan nilai benar) maka entri yang sama digunakan. Misalnya String baru ("satu") dan `String baru (" satu ") digunakan sebagai kunci, akan menggunakan entri yang sama. Sebenarnya ini adalah poin SELURUH HashMap di tempat pertama! Lihat sendiri: pastebin.com/f20af40b9 - Oscar Reyes "

versus komentar sebelumnya yang secara eksplisit membahas pentingnya kelas identik dan kode hash yang sama, tanpa menyebutkan sama dengan:

"@delfuego: Lihat sendiri: pastebin.com/f20af40b9 Jadi, dalam pertanyaan ini kelas yang sama sedang digunakan (tunggu sebentar, kelas yang sama sedang digunakan kan?) Yang menyiratkan bahwa ketika hash yang sama digunakan, entri yang sama digunakan dan tidak ada "daftar" entri. - Oscar Reyes "

atau

"Sebenarnya ini akan meningkatkan kinerja. Semakin banyak tabrakan eq lebih sedikit entri dalam persamaan hashtable. Lebih sedikit pekerjaan yang harus dilakukan. ciptaan yang kinerjanya merendahkan. - Oscar Reyes "

atau

"@kdgregory: Ya, tetapi hanya jika tabrakan terjadi dengan kelas yang berbeda, untuk kelas yang sama (yang merupakan kasus), entri yang sama digunakan. - Oscar Reyes"

Sekali lagi, saya mungkin salah paham tentang apa yang sebenarnya coba dikatakan Oscar. Namun, komentar aslinya telah menyebabkan kebingungan yang cukup sehingga tampaknya bijaksana untuk menjernihkan semuanya dengan beberapa tes eksplisit sehingga tidak ada keraguan yang tersisa.

[1] - Dari Java yang Efektif, Edisi Kedua oleh Joshua Bloch:

• Kapan pun itu dipanggil pada objek yang sama lebih dari sekali selama eksekusi aplikasi, metode hashCode harus secara konsisten mengembalikan bilangan bulat yang sama, asalkan tidak ada informasi yang digunakan dalam perbandingan yang sama pada objek yang dimodifikasi. Integer ini tidak perlu tetap konsisten dari satu eksekusi aplikasi ke eksekusi lain dari aplikasi yang sama.

• Jika dua objek sama menurut metode equal s (Obj ect), maka pemanggilan metode hashCode pada masing-masing objek harus menghasilkan hasil integer yang sama.

• Tidak diperlukan bahwa jika dua objek tidak sama menurut metode s (Object) yang sama, maka pemanggilan metode hashCode pada masing-masing dari dua objek harus menghasilkan hasil integer yang berbeda. Namun, programmer harus menyadari bahwa menghasilkan hasil integer yang berbeda untuk objek yang tidak sama dapat meningkatkan kinerja tabel hash.

Jika array dalam kode hash yang Anda posting adalah byte, maka kemungkinan besar Anda akan mendapatkan banyak duplikat.

a [0] + a [1] akan selalu antara 0 dan 512. menambahkan b akan selalu menghasilkan angka antara 0 dan 768. kalikan itu dan Anda mendapatkan batas atas 400.000 kombinasi unik, dengan asumsi data Anda terdistribusi sempurna di antara setiap nilai yang mungkin dari setiap byte. Jika data Anda sama sekali biasa, kemungkinan besar Anda memiliki keluaran yang jauh lebih unik dari metode ini.

HashMap memiliki kapasitas awal dan performa HashMap sangat bergantung pada hashCode yang menghasilkan objek yang mendasarinya.

Cobalah untuk menyesuaikan keduanya.

Jika kunci memiliki pola apa pun, Anda dapat membagi peta menjadi peta yang lebih kecil dan memiliki peta indeks.

Contoh: Kunci: 1,2,3, .... n 28 peta yang masing-masing berisi 1 juta. Peta indeks: 1-1.000.000 -> Peta1 1.000.000-2.000.000 -> Peta2

Jadi, Anda akan melakukan dua pencarian tetapi kumpulan kuncinya adalah 1.000.000 vs 28.000.000. Anda juga dapat melakukannya dengan mudah dengan pola sengatan.

Jika kunci benar-benar acak maka ini tidak akan berhasil

Jika array dua byte yang Anda sebutkan adalah seluruh kunci Anda, nilainya berada dalam kisaran 0-51, unik dan urutan dalam array a dan b tidak signifikan, matematika saya memberi tahu saya bahwa hanya ada sekitar 26 juta kemungkinan permutasi dan bahwa Anda mungkin mencoba mengisi peta dengan nilai untuk semua kemungkinan kunci.

Dalam hal ini, mengisi dan mengambil nilai dari penyimpanan data Anda tentu saja akan jauh lebih cepat jika Anda menggunakan array daripada HashMap dan mengindeksnya dari 0 hingga 25989599.

Saya terlambat di sini, tetapi beberapa komentar tentang peta besar:

1. Seperti yang dibahas panjang lebar di posting lain, dengan hashCode () yang baik, 26 juta entri dalam Peta bukanlah masalah besar.
2. Namun, masalah yang berpotensi tersembunyi di sini adalah dampak GC dari peta raksasa.

Saya berasumsi bahwa peta ini berumur panjang. yaitu Anda mengisinya dan mereka bertahan selama aplikasi. Saya juga berasumsi bahwa aplikasi itu sendiri berumur panjang - seperti semacam server.

Setiap entri di Java HashMap memerlukan tiga objek: kunci, nilai, dan Entri yang mengikatnya. Jadi 26 juta entri di peta berarti 26 juta * 3 == 78 juta objek. Ini bagus sampai Anda mencapai GC penuh. Maka Anda punya masalah jeda-dunia. GC akan melihat masing-masing 78 juta objek dan menentukan semuanya hidup. 78M + objek hanyalah banyak objek untuk dilihat. Jika aplikasi Anda dapat mentolerir jeda sesekali (mungkin beberapa detik), tidak ada masalah. Jika Anda mencoba mencapai jaminan latensi, Anda dapat mengalami masalah besar (tentu saja jika Anda menginginkan jaminan latensi, Java bukanlah platform yang dapat dipilih :)) Jika nilai di peta Anda berubah dengan cepat, Anda dapat berakhir dengan pengumpulan penuh yang sering yang memperparah masalah.

Saya tidak tahu solusi yang bagus untuk masalah ini. Ide ide:

• Terkadang mungkin untuk menyesuaikan GC dan ukuran heap ke "sebagian besar" mencegah GC penuh.
• Jika konten peta Anda banyak berputar, Anda dapat mencoba FastMap Javolution - itu dapat mengumpulkan objek Entri, yang dapat menurunkan frekuensi pengumpulan penuh
• Anda dapat membuat impl peta Anda sendiri dan melakukan manajemen memori eksplisit pada byte [] (yaitu, tukar cpu untuk latensi yang lebih dapat diprediksi dengan membuat serial jutaan objek menjadi satu byte [] - ugh!)
• Jangan gunakan Java untuk bagian ini - bicarakan dengan semacam DB dalam memori yang dapat diprediksi melalui soket
• Berharap kolektor G1 baru akan membantu (terutama berlaku untuk casing high-churn)

Sekadar pemikiran dari seseorang yang telah menghabiskan banyak waktu dengan peta raksasa di Jawa.

Dalam kasus saya, saya ingin membuat peta dengan 26 juta entri. Menggunakan Java HashMap standar, put rate menjadi sangat lambat setelah 2-3 juta penyisipan.

Dari percobaan saya (proyek siswa tahun 2009):

• Saya membangun Pohon Hitam Merah untuk 100.000 node dari 1 hingga 100.000. Butuh 785,68 detik (13 menit). Dan saya gagal membangun RBTree untuk 1 juta node (seperti hasil Anda dengan HashMap).
• Menggunakan "Prime Tree", struktur data algoritme saya. Saya bisa membangun pohon / peta untuk 10 juta node dalam waktu 21,29 detik (RAM: 1,97Gb). Biaya nilai kunci penelusuran adalah O (1).

Catatan: "Prime Tree" bekerja paling baik pada "kunci kontinu" dari 1 - 10 juta. Untuk bekerja dengan kunci seperti HashMap kita membutuhkan beberapa penyesuaian anak di bawah umur.

Jadi, apa itu #PrimeTree? Singkatnya, ini adalah struktur data pohon seperti Pohon Biner, dengan nomor cabang adalah bilangan prima (bukan biner "2").

Anda dapat mencoba menggunakan database dalam memori seperti HSQLDB .

SQLite memungkinkan Anda menggunakannya di memori.

Pernahkah Anda mempertimbangkan untuk menggunakan database sematan untuk melakukan ini. Lihatlah Berkeley DB . Ini open-source, dimiliki oleh Oracle sekarang.

Ini menyimpan semuanya sebagai Key-> Value pair, BUKAN RDBMS. dan itu bertujuan untuk menjadi cepat.

Pertama, Anda harus memeriksa apakah Anda menggunakan Map dengan benar, metode hashCode () yang baik untuk kunci, kapasitas awal untuk Map, implementasi Map yang benar, dll. Seperti yang dijelaskan oleh banyak jawaban lain.

Kemudian saya akan menyarankan menggunakan profiler untuk melihat apa yang sebenarnya terjadi dan di mana waktu eksekusi dihabiskan. Apakah, misalnya, metode hashCode () dieksekusi miliaran kali?

Jika itu tidak membantu, bagaimana jika menggunakan sesuatu seperti EHCache atau memcache ? Ya, ini adalah produk untuk penyimpanan cache tetapi Anda dapat mengkonfigurasinya sehingga memiliki kapasitas yang cukup dan tidak akan pernah mengeluarkan nilai apa pun dari penyimpanan cache.

Pilihan lain adalah beberapa mesin database yang bobotnya lebih ringan daripada SQL RDBMS penuh. Sesuatu seperti Berkeley DB , mungkin.

Perhatikan, bahwa saya pribadi tidak memiliki pengalaman dengan kinerja produk ini, tetapi mereka patut untuk dicoba.

Anda dapat mencoba menyimpan kode hash yang dihitung ke dalam cache ke objek kunci.

Sesuatu seperti ini:

public int hashCode() {
  if(this.hashCode == null) {
     this.hashCode = computeHashCode();
  }
  return this.hashCode;
}

private int computeHashCode() {
   int hash = 503;
   hash = hash * 5381 + (a[0] + a[1]);
   hash = hash * 5381 + (b[0] + b[1] + b[2]);
   return hash;
}

Tentu saja Anda harus berhati-hati agar tidak mengubah konten key setelah hashCode dihitung untuk pertama kali.

Sunting: Tampaknya caching memiliki nilai kode yang tidak berguna ketika Anda menambahkan setiap kunci hanya sekali ke peta. Dalam situasi lain, ini bisa berguna.

Poster lain sudah menunjukkan bahwa penerapan kode hash Anda akan menghasilkan banyak tabrakan karena cara Anda menambahkan nilai secara bersamaan. Saya bersedia menjadi itu, jika Anda melihat objek HashMap di debugger, Anda akan menemukan bahwa Anda mungkin memiliki 200 nilai hash yang berbeda, dengan rantai keranjang yang sangat panjang.

Jika Anda selalu memiliki nilai dalam rentang 0..51, masing-masing nilai tersebut akan membutuhkan 6 bit untuk diwakili. Jika Anda selalu memiliki 5 nilai, Anda dapat membuat kode hash 30-bit dengan pergeseran kiri dan penambahan:

    int code = a[0];
    code = (code << 6) + a[1];
    code = (code << 6) + b[0];
    code = (code << 6) + b[1];
    code = (code << 6) + b[2];
    return code;

Pergeseran kiri cepat, tetapi akan meninggalkan Anda dengan kode hash yang tidak terdistribusi secara merata (karena 6 bit menyiratkan kisaran 0..63). Alternatifnya adalah mengalikan hash dengan 51 dan menambahkan setiap nilai. Ini masih tidak akan terdistribusi sempurna (misalnya, {2,0} dan {1,52} akan bertabrakan), dan akan lebih lambat dari shift.

    int code = a[0];
    code *= 51 + a[1];
    code *= 51 + b[0];
    code *= 51 + b[1];
    code *= 51 + b[2];
    return code;

Seperti yang ditunjukkan, implementasi kode hash Anda memiliki terlalu banyak tabrakan, dan memperbaikinya akan menghasilkan kinerja yang layak. Selain itu, menyimpan kode hash dan menerapkan sama secara efisien akan membantu.

Jika Anda perlu mengoptimalkan lebih jauh:

Berdasarkan uraian Anda, hanya ada (52 * 51/2) * (52 * 51 * 50/6) = 29304600 kunci yang berbeda (26000000, yaitu sekitar 90%, akan hadir). Oleh karena itu, Anda bisa mendesain fungsi hash tanpa benturan, dan menggunakan array sederhana daripada hashmap untuk menyimpan data Anda, mengurangi konsumsi memori dan meningkatkan kecepatan pencarian:

T[] array = new T[Key.maxHashCode];

void put(Key k, T value) {
    array[k.hashCode()] = value;

T get(Key k) {
    return array[k.hashCode()];
}

(Secara umum, tidak mungkin untuk merancang fungsi hash yang efisien dan bebas benturan yang terkumpul dengan baik, itulah sebabnya HashMap akan mentolerir tabrakan, yang menimbulkan beberapa overhead)

Dengan asumsi adan bdiurutkan, Anda mungkin menggunakan fungsi hash berikut:

public int hashCode() {
    assert a[0] < a[1]; 
    int ahash = a[1] * a[1] / 2 
              + a[0];

    assert b[0] < b[1] && b[1] < b[2];

    int bhash = b[2] * b[2] * b[2] / 6
              + b[1] * b[1] / 2
              + b[0];
    return bhash * 52 * 52 / 2 + ahash;
}

static final int maxHashCode = 52 * 52 / 2 * 52 * 52 * 52 / 6;  

Saya pikir ini bebas tabrakan. Membuktikan hal ini dibiarkan sebagai latihan bagi pembaca yang cenderung matematis.

Dalam Java yang Efektif: Panduan Bahasa Pemrograman (Seri Java)

Bab 3 Anda dapat menemukan aturan yang baik untuk diikuti saat menghitung hashCode ().

Khususnya:

Jika bidang adalah larik, perlakukan seolah-olah setiap elemen adalah bidang yang terpisah. Artinya, hitung kode hash untuk setiap elemen penting dengan menerapkan aturan ini secara rekursif, dan gabungkan nilai-nilai ini per langkah 2.b. Jika setiap elemen dalam kolom array signifikan, Anda dapat menggunakan salah satu metode Arrays.hashCode yang ditambahkan dalam rilis 1.5.

Alokasikan peta besar di awal. Jika Anda tahu itu akan memiliki 26 juta entri dan Anda memiliki memori untuk itu, lakukan a new HashMap(30000000).

Yakin, Anda memiliki cukup memori untuk 26 juta entri dengan 26 juta kunci dan nilai? Ini terdengar seperti banyak kenangan bagi saya. Apakah Anda yakin bahwa pengumpulan sampah masih baik-baik saja di angka 2 hingga 3 juta? Saya bisa membayangkan itu sebagai hambatan.

Anda dapat mencoba dua hal:

Kedua tindakan itu akan sangat mengurangi jumlah pengulangan struktur yang dilakukan, dan menurut saya cukup mudah untuk diuji.

Jika tidak berhasil, pertimbangkan untuk menggunakan penyimpanan yang berbeda seperti RDBMS.

EDIT

Aneh bahwa pengaturan kapasitas awal mengurangi kinerja dalam kasus Anda.

Lihat dari javadocs :

Jika kapasitas awal lebih besar dari jumlah entri maksimum dibagi dengan faktor beban, operasi pengulangan tidak akan pernah terjadi.

Saya membuat microbeachmark (yang sama sekali tidak pasti tetapi setidaknya membuktikan hal ini)

$cat Huge*java
import java.util.*;
public class Huge {
    public static void main( String [] args ) {
        Map map = new HashMap( 30000000 , 0.95f );
        for( int i = 0 ; i < 26000000 ; i ++ ) { 
            map.put( i, i );
        }
    }
}
import java.util.*;
public class Huge2 {
    public static void main( String [] args ) {
        Map map = new HashMap();
        for( int i = 0 ; i < 26000000 ; i ++ ) { 
            map.put( i, i );
        }
    }
}
$time java -Xms2g -Xmx2g Huge

real    0m16.207s
user    0m14.761s
sys 0m1.377s
$time java -Xms2g -Xmx2g Huge2

real    0m21.781s
user    0m20.045s
sys 0m1.656s
$

Jadi, menggunakan kapasitas awal turun dari 21 detik menjadi 16 detik karena perulangan. Itu meninggalkan kami dengan milikmuhashCode metode sebagai "area peluang";)

EDIT

Bukankah HashMap tersebut

Sesuai edisi terakhir Anda.

Saya pikir Anda harus benar-benar membuat profil aplikasi Anda dan melihat di mana memori / cpu digunakan.

Saya telah membuat kelas yang menerapkan hal yang sama hashCode

Kode hash tersebut memberikan jutaan tabrakan, kemudian entri di HashMap berkurang secara dramatis.

Saya lulus dari 21s, 16s di tes saya sebelumnya menjadi 10s dan 8s. Alasannya adalah karena kode hash memicu sejumlah besar tabrakan dan Anda tidak menyimpan 26 juta objek yang Anda pikirkan tetapi jumlah yang jauh lebih rendah (sekitar 20k menurut saya) Jadi:

Masalahnya BUKAN HASHMAP ada di tempat lain dalam kode Anda.

Sudah waktunya untuk mendapatkan profiler dan mencari tahu di mana. Saya akan berpikir itu pada pembuatan item atau mungkin Anda menulis ke disk atau menerima data dari jaringan.

Inilah implementasi saya di kelas Anda.

perhatikan saya tidak menggunakan rentang 0-51 seperti yang Anda lakukan tetapi -126 hingga 127 untuk nilai saya dan mengaku berulang, itu karena saya melakukan tes ini sebelum Anda memperbarui pertanyaan Anda

Satu-satunya perbedaan adalah bahwa kelas Anda akan memiliki lebih banyak tabrakan sehingga lebih sedikit item yang disimpan di peta.

import java.util.*;
public class Item {

    private static byte w = Byte.MIN_VALUE;
    private static byte x = Byte.MIN_VALUE;
    private static byte y = Byte.MIN_VALUE;
    private static byte z = Byte.MIN_VALUE;

    // Just to avoid typing :) 
    private static final byte M = Byte.MAX_VALUE;
    private static final byte m = Byte.MIN_VALUE;


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

    public Item () {
        // make a different value for the bytes
        increment();
        a[0] = z;        a[1] = y;    
        b[0] = x;        b[1] = w;   b[2] = z;
    }

    private static void increment() {
        z++;
        if( z == M ) {
            z = m;
            y++;
        }
        if( y == M ) {
            y = m;
            x++;
        }
        if( x == M ) {
            x = m;
            w++;
        }
    }
    public String toString() {
        return "" + this.hashCode();
    }



    public int hashCode() {
        int hash = 503;
        hash = hash * 5381 + (a[0] + a[1]);
        hash = hash * 5381 + (b[0] + b[1] + b[2]);
        return hash;
    }
    // I don't realy care about this right now. 
    public boolean equals( Object other ) {
        return this.hashCode() == other.hashCode();
    }

    // print how many collisions do we have in 26M items.
    public static void main( String [] args ) {
        Set set = new HashSet();
        int collisions = 0;
        for ( int i = 0 ; i < 26000000 ; i++ ) {
            if( ! set.add( new Item() ) ) {
                collisions++;
            }
        }
        System.out.println( collisions );
    }
}

Menggunakan kelas ini memiliki kunci untuk program sebelumnya

 map.put( new Item() , i );

beri saya:

real     0m11.188s
user     0m10.784s
sys 0m0.261s


real     0m9.348s
user     0m9.071s
sys  0m0.161s

Mungkin coba gunakan jika Anda membutuhkannya untuk disinkronkan

http://commons.apache.org/collections/api/org/apache/commons/collections/FastHashMap.html

Saya melakukan tes kecil beberapa waktu yang lalu dengan daftar vs hashmap, lucunya iterasi melalui daftar dan menemukan objek mengambil jumlah waktu yang sama dalam milidetik seperti menggunakan fungsi get hashmaps ... hanya fyi. Oh ya, memori adalah masalah besar saat bekerja dengan hashmaps sebesar itu.

Metode hashing populer yang digunakan tidak terlalu bagus untuk set besar dan, seperti yang ditunjukkan di atas, hash yang digunakan sangat buruk. Lebih baik menggunakan algoritma hash dengan pencampuran dan cakupan yang tinggi seperti BuzHash (contoh implementasi di http://www.java2s.com/Code/Java/Development-Class/AveryefficientjavahashalgorithmbasedontheBuzHashalgoritm.htm )