私は常に、優れたパフォーマンスとクリーンなコードに注意を払うようにしています。
150 文字のキーを持つ HashMap を持つことが正気かどうかを把握するのに苦労しています。
- HashMap キーの長さに対する不文律はありますか?
- 150文字の文字列キーを持つことは悪い習慣と考えられていますか?
- パフォーマンスに影響はありますか? どの長さで?
私は常に、優れたパフォーマンスとクリーンなコードに注意を払うようにしています。
150 文字のキーを持つ HashMap を持つことが正気かどうかを把握するのに苦労しています。
そうではありませんが、150 文字の文字列は比較的簡単にhashCode
for を計算できます。
そうは言っても、このような状況では、テストすることをお勧めします!
HashMap にデータを入力するルーチンを作成します。たとえば、5 文字の文字列をキーとして使用シナリオのランダム値を表すサイズをここに挿入します。かかる時間を測定します。次に、15 文字のキーに対して同じことを行い、どのようにスケーリングするかを確認します。
また、Java の文字列は不変です。つまりhashCode
、文字列定数プールに格納されている文字列ごとにキャッシュでき、同じ文字列オブジェクトで hashCode を呼び出すときに再計算する必要はありません。
これは、マップを作成するときに大きなハッシュ コードを計算していても、アクセス時にそれらの多くが事前に計算されてキャッシュされていることを意味し、元の文字列のサイズはさらに重要ではなくなります。
HashMap キーの長さに対する不文律はありますか?
あるとすれば、それも無言です。プロファイラーでユースケースを測定し、問題であると想像できるものではなく、問題として測定できるものだけを心配します。
150文字の文字列キーを持つことは悪い習慣と考えられていますか?
疑わしい。
パフォーマンスに影響はありますか? どの長さで?
すべてがパフォーマンスに影響し、通常は小さなものから重要なものまで、場合によっては測定することさえできます。問題は次のとおりです。150 文字のキーが必要ですか。もしそうなら、それらを使用してください。
hashCode() が 0 の文字列を追加するのが悪い考えである特殊なケースがあります。これは、Java 1.0 から 6 では、ゼロの hashCode のユース ケースが最適化されておらず、サービス拒否攻撃が予測される可能性があるためです。Java 7 では、予測しにくい二次ハッシュコードを使用することで、これを修正しています。
長い答え:のソース コードをざっと見てみるとString::hashCode()
、最初の呼び出しの後にハッシュがキャッシュされていることがわかります。一方、String::equals()
文字列が等しいが同一でない場合 (つまり、equals()
は true であるが==
、異なるアドレスに割り当てられているため false である) は O(n) です。
したがって、表示されるパフォーマンスへの影響は次のとおりです。
HashMap
関数の呼び出しでハッシュ化されたことのない文字列を渡す。ただし、多くの新しい文字列を生成すると、パフォーマンス自体に影響します。
HashMap に既に存在するキーと等しい文字列キーを呼び出してHashMap::get()
使用する (キーがコレクションにない場合は、ほとんどの場合、hashCode() のみが呼び出されます。しかし、ある場合は、equals() が比較されます)HashMap::put()
文字列が等しいと判断されるまで、すべての文字)。ただし、これらの関数に渡された文字列が HashMap に既に存在するオブジェクトと同じでない場合のみです。その場合equals()
は非常に高速であるためです。
さらに、文字列リテラル、文字列定数、および手動でintern()
'd 化された文字列は、すべての「等しい」文字列が同じアドレスを持つ同じオブジェクトである文字列定数プールに参加します。したがって、そのような文字列のみを使用する場合、hashCode
非常equals
に高速です。
もちろん、前述の操作をタイトなループで実行しない限り、パフォーマンスへの影響はまったく目立ちません (150 文字は長くなく、hashCode() と equals() は両方とも効率的であるため)。
簡単な答え:ベンチマーク。
まず、「不文律」はありません。キーとしての長い文字列がアルゴリズムの観点から理にかなっている場合は、それらを使用してください。プロファイリングで問題があることが示された場合は、最適化します。
では、長い文字列はハッシュ テーブルのパフォーマンスにどのように影響するのでしょうか?
長い文字列は短い文字列よりも多くのメモリを消費するため、ガベージ コレクション時間がかなり長くなる可能性があり、ハードウェア メモリ キャッシュ、TLB、および (潜在的に) 物理メモリ ページの競合に関連するその他の二次的なパフォーマンスへの影響が生じる可能性があります。
String のハッシュコード アルゴリズムは文字列のすべての文字を使用するため、そのコストは文字列の長さに比例します。これは、文字列ハッシュコードがキャッシュされるという事実によって軽減されます。(String を 2 回目以降に呼び出すとhashcode
、キャッシュされた値が取得されます。)ただし、これは (ここでは) 同じ String オブジェクトをキーとして複数のハッシュ テーブル操作を行う場合にのみ役立ちます。
ハッシュの競合が発生すると、ハッシュ テーブルはString.equals()
、選択したハッシュ チェーンの検索中にキーの比較に使用するようにフォール バックします。最悪の場合 (たとえば、文字列が であるequal
がそうでない場合==
)、String.equals()
2 つの文字列のすべての文字を比較する必要があります。
ご覧のとおり、これらの影響は実際のアプリケーションに固有のものになるため、予測が困難です。したがって、「不文律」は役に立たないでしょう。