JavaのHashMapでハッシュ競合問題を解決する方法

1. ハッシュ アルゴリズムとハッシュ テーブル

ハッシュの競合を理解するには、まずハッシュ アルゴリズムとハッシュ テーブルを理解します

• #ハッシュ アルゴリズムは、ハッシュ アルゴリズムを通じて任意の長さの入力を固定長の出力に変換します。出力結果はハッシュ値です。特定の実装では、メモリ格納場所のデータ構造にアクセスするには、ハッシュ関数を使用します。キーをテーブル内の特定の場所にマップして、その場所のデータを取得することで、データ検索を高速化します

• 2. ハッシュの競合

ハッシュの競合が発生していますハッシュアルゴリズムに従う 計算されるデータは無限であり、計算結果の範囲は限られている 常に異なるデータが存在する 計算後に得られた値が同じである場合、いわゆるハッシュ競合が発生するこの場合、

#3. ハッシュ競合を解決するには 4 つの方法があります。

オープン アドレッシング法は線形検出法とも呼ばれ、競合が発生している位置から開始し、空き領域を見つけます。 Java では、ThreadLocal はハッシュの競合を解決するために線形検出を使用します。

に示すように、ハッシュ テーブルから特定の順序で競合する要素をこの位置に保存します。図では、key=name がハッシュ テーブルのインデックス 1 に格納されており、計算されたインデックスも 1 であると仮定してそれに key=hobby が追加されると、ハッシュの競合が発生し、オープン オープン アドレッシング方法は空きアドレスを見つけることになります。競合するキーを保存するための場所

#チェーン アドレス指定方法。これは一般的な方法です。簡単に理解すると、ハッシュ競合のあるキーは、HashMap などの一方向のリンク リストに保存されます

図に示すように、競合するキーは一方向リンク リストに直接格納されます

ハッシュ方式とは、特定のハッシュ関数を通じてキーを計算することです。競合がある場合は、競合が発生しなくなるまで、別のハッシュ関数を使用してキーをハッシュできます。この方法では計算時間が増加します。時間がかかり、パフォーマンスに多少の影響があります。

公開削除領域を確立するには、ハッシュ テーブルを基本テーブルと利点テーブルの 2 つの部分に分割します。競合する要素はすべて利点テーブルに配置されます。

4. JDK1.8 バージョンでの HashMap の最適化

HashMap JDK1.8バージョンでは、チェーンアドレッシング方式と赤黒ツリーによりハッシュ競合の問題を解決しており、その中でも赤黒ツリーはハッシュテーブルの長いリンクリストによる時間の増大の問題を最適化するものです。リンク リストの長さが 8 以上で、ハッシュ テーブルの容量が 64 より大きい場合、リンク リストに要素を追加すると、リンク リストが赤黒ツリーに変換されます。

以上がJavaのHashMapでハッシュ競合問題を解決する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。