1

私はQuora の問題を解決していましたが、私の特定のソリューションでは、値をキャッシュするためのハッシュテーブル (長いキー、int 値) が必要でした。キーと値のデータ型を知っていて、それらはプリミティブであり、問​​題空間でもあったため、Java HashMap が改善されることを望みました。「array-oflinkedlist」構造を使用して単純なハッシュテーブルを単純に実装することにしました (linkedList でさえ、私が実装した独自の Node クラスでした)。しかし、私自身の単純な実装は、一般的な Java HashMap よりも約 4 倍遅いことに気付きました。また、 Trove の LongToIntMapライブラリを使用して、その機能を確認しようとしました。Java HashMap を大幅に上回るカスタムの Long から Int へのハッシュテーブルを Java で構築するための良い提案はありますか?

4

2 に答える 2

1

Javolution のFastMapを見てください。ソースコードはこちらから入手できます。

于 2011-08-20T06:37:01.840 に答える
1

また、Trove の LongToIntMap ライブラリを使用して、その機能を確認しようとしました。

コードを見て、彼らがどのようにそれを行うかを確認しましたか?

コードを見ずに、実装で何が間違っていたかを確実に言うことはできません。ただし、考えられる改善の 1 つは、リストを表すためLinkedList<Integer>に使用するカスタムの「整数のリスト」タイプに置き換えることint[]です。Integerハッシュ テーブル API によっては、値をオブジェクト (特にs)として表すコストを回避できるはずです。(結果として、キーおよび/または値の型のジェネリック型を持つ API を実装しないことで、パフォーマンスとスペースの使用率が向上します。)

パフォーマンスの低下につながる可能性のある間違いの 1 つは、ハッシュテーブルのサイズ変更の実装を怠ることです。サイズを変更しないと、ハッシュ チェーンの長さがハッシュ テーブル エントリの数に比例して大きくなるため、テーブルに対する操作getと操作の複雑さは ...ではなくなります。putO(N)O(1)

最後に、パフォーマンスまたはスペース使用率のどちらを最適化するかを明確にする必要があります。最適解は違うだろう…。

于 2011-08-20T06:40:51.097 に答える