[解決済み] Java HashMapのパフォーマンス最適化/代替案

質問

大きなHashMapを作りたいのですが、HashMapの中の put() のパフォーマンスが十分ではありません。何かアイデアはありますか？

他のデータ構造の提案も歓迎しますが、私はJava Mapのルックアップ機能が必要です。

map.get(key)

私の場合、2600万のエントリを持つマップを作成したいと思います。標準的なJava HashMapを使用すると、2～300万件の挿入の後、putレートが耐えられないほど遅くなります。

また、キーに異なるハッシュコード分布を使用することが役に立つかどうか、誰か知っていますか？

私のハッシュコード方式です。

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

同じオブジェクトが同じハッシュコードを持つようにするために、加算の連想特性を使用しています。配列は0から51の値を持つバイトで、値はどちらの配列でも一度だけ使用されます。オブジェクトは、a 配列が同じ値 (どちらの順番でも) を含んでいれば等しく、b 配列も同様です。つまり、a = {0,1} b = {45,12,33} と a = {1,0} b = {33,45,12} は等しいということです。

EDIT、いくつかの注意点です。

• 2600万のエントリを格納するためにハッシュマップや他のデータ構造を使用することを批判する人が何人かいました。なぜこれが奇妙に思えるのか、私にはわかりません。 私には、古典的なデータ構造とアルゴリズムの問題のように見えます。2600 万の項目があり、それらをデータ構造にすばやく挿入し、データ構造から調べることができるようにしたいのですが、そのデータ構造とアルゴリズムを教えてください。

• デフォルトのJava HashMapの初期容量を2600万に設定する が減少します。 性能を低下させます。

• 何人かの人は、データベースを使用することを提案し、いくつかの他の状況では、それは間違いなくスマートな選択肢です。しかし、私は本当にデータ構造とアルゴリズムの質問をしているのです。完全なデータベースはやりすぎで、優れたデータ構造ソリューションよりもはるかに遅いでしょう (結局のところ、データベースは単なるソフトウェアですが、通信とおそらくディスク オーバーヘッドがあります)。

どのように解決するのですか？

多くの人が指摘しているように hashCode() メソッドが原因でした。2600 万個の異なるオブジェクトに対して、約 20,000 個のコードしか生成していなかったのです。これは、ハッシュバケットあたり平均1,300個のオブジェクトということです。しかし、2 つの配列を 52 進数の数値に変換すると、すべてのオブジェクトに対して一意のハッシュ コードが得られることが保証されます。

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

配列をソートすることで、このメソッドが hashCode() 契約を満たすように配列がソートされます。古い方法を使用すると、100,000 プットのブロックにわたる 1 秒あたりの平均プット数は、100,000 から 2,000,000 でした。

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

新しいメソッドを使用すると、次のようになります。

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

ずっとずっと良くなりました。 古い方法はすぐに停止してしまいましたが、新しい方法は良好なスループットを維持します。