Java のハッシュ テーブルの詳細な紹介

ハッシュ テーブルとは

ハッシュ テーブルは、ハッシュ テーブル (ハッシュ テーブル) とも呼ばれます。 a キーと値の間のマッピング関係を提供するデータ構造。キーが与えられている限り、一致する値を効率的に見つけることができ、時間計算量は O(1) に近くなります。

java ビデオ

ハッシュ テーブルの仕組みハッシュ テーブルは本質的には配列です。 a[0]、a[1]、a[2]、a[3]、a[4] などの添字に基づいて配列にランダムにアクセスできることがわかっており、クエリ効率が非常に高くなります。ハッシュ テーブルでは、キーを与えると、対応する値をすぐにクエリできます。このとき、Keyと配列の添字を何らかの方法で変換するための「転送ステーション」が必要になりますが、この転送ステーションがハッシュ関数です。

言語が異なれば、ハッシュ関数の実装方法も異なります。 Java で使用されるのは

です。 Java およびほとんどのオブジェクト指向言語では、各オブジェクトには、異なるオブジェクトを区別するための独自の

があり、このハッシュコードは整数変数です。このとき、この整数変数を配列の添え字に変換する必要がありますが、最も簡単な変換方法は配列の長さの剰余を取ることです。 式は次のとおりです:

index = HashCode(key) % Array.length

例:

長さ 8 の配列が与えられた場合、キー「001121」に対応する値を見つけたいとします。 、「 001121 のハッシュコード」は 1420036703 である場合、まず次の計算を通じて配列の添字を取得できます。

index = HashCode("001121")%Array.length = 1420036703 % 8 = 7

書き込み操作は、ハッシュ テーブル (jdk では Entry と呼ばれます) に新しいキーと値のペアを挿入することです。

具体的な方法は次のとおりです。ハッシュ関数を使用してキー値を配列添字に変換し、配列内のその位置にエントリを挿入します (単なるエントリ キー値ペアではなく、エントリ キー値のペアであることに注意してください)値）。異なるキー値が同じ添え字に変換され、ハッシュの競合が発生することが考えられます。

ハッシュの競合を解決するために一般的に使用される方法は、オープン アドレス指定方法とリンク リスト方法です。

オープン アドレッシング方式の基本的な考え方は、ハッシュの競合が発生すると、エントリが配列内の次の空の位置に配置される、つまり 1 つずつ戻されるというものです。

リンク リスト メソッド (Java の HashMap コレクション クラスに適用される) の基本的な考え方は、配列内の各要素が Entry オブジェクトであるだけでなく、リンク リストのヘッド ノードでもあるということです。各 Entry オブジェクトは、次のポインタを介して次の Entry ノードを指します。新しい Entry オブジェクトが競合する配列位置にマップされる場合、そのオブジェクトを対応するリンク リストに挿入するだけで済みます。

読み取り操作は書き込み操作に対応しており、競合状況のみを特別に処理する必要があります。 。

具体的なアイデアは、ハッシュ関数を使用して、検索する Key 値を配列の添字に変換し、配列内のその位置にある Key 値が探している Key であるかどうかを確認するというものです。 Entry の Value 値を返すこともできますが、それ以外の場合は、リンクされたリストの検索を続けて、対応する Key 値があるかどうかを確認します。

たとえば、キー 002936 に対応する値を見つけたい場合、まずキーを配列の添え字に変換し、添え字 2 を取得します。要素を確認すると、要素のキーが 002947 であることがわかります。キーをクエリする場合は、リンクされたリストを下方向に検索し続けます。

配列内の要素数が最大長に達した場合、配列の拡張が必要であることがわかります。配列 配列を拡張する場合、ハッシュ テーブルはいつ拡張されますか?

複数の要素を挿入した後、ハッシュ テーブルがある程度飽和状態に達すると、配列の同じ添字位置に多数の要素が密集し、ハッシュ競合が発生する可能性が高くなります。ポストオーダーの影響は挿入やクエリのパフォーマンスに大きく影響するため、この際ハッシュテーブルを拡張する必要があります。

Capacity，即HashMap的当前长度

LoadFactor，即HashMap的负载因子，默认值为0.75

扩容需要满足的条件：

HashMap.Size >= Capacity X LoadFactor

简单解释为：当哈希表中的条目数超出了当前容量与其加载因子的乘积时，并且要存放的位置已经有元素了（哈希碰撞），这两个条件满足时，需要进项扩容，会将容量扩大为原来的两倍。加载因子默认值0.75，是在空间和时间上的一个折中，加载因子过高（发生冲突可多存放在链表），虽然减少了空间成本，但也增加了查询成本。