私は、2 つの異なるが関連する引数の検証を探しています。つまり、Q の最初の行の行コメントの上(A)と下(B)です。
(A) HashMapの構造は次のとおりです。
HashMapはプレーンなテーブルです。それがダイレクト メモリ アクセス (DMA) です。
そもそもHashMap （または一般的なハッシュ）の背後にある全体的なアイデアは、この一定時間のメモリアクセスを使用することです
a.) DMA 内の位置 (テーブル インデックス) ではなく、独自のデータ コンテンツ (< K,V >) によってレコードにアクセスする
b.) 可変数のレコードの管理 -- 特定のサイズではなく、この構造体の使用中にサイズが一定のままである場合とない場合があるレコードの数。
したがって、Java ハッシュの全体的な構造は次のとおりです。
a table: table // HashMapで使用される識別子を使用しています
このテーブルの各セルはバケットです。
各バケットはエントリタイプのリンク リストです。つまり、このリンク リスト (Java/API のリンク リストではなく、データ構造) の各ノードは、< K,V > ペアである エントリタイプです。
新しいペアがハッシュに追加されると、この < K,V > ペアに対して一意のhashCodeが計算されます。このhashCodeは、テーブル内のこの < K,V > のインデックスへのキーです。これは、この < K,V > がハッシュに入るバケットを示します。注: hashCodeは、関数hash() (1 つはHashMap内)によって「正規化」され、テーブルの現在の長さにより適合します。indexFor()は、どのバケット、つまり < K,V > が入るテーブルのセルを決定するためにも使用されます。
バケットが決定されると、< K,V > がこのバケットのリンクされたリストの先頭に追加されます。その結果、これがこのバケットの最初の < K,V > エントリであり、リンクされたリストの最初のエントリになります。 -list-that-already-existed は、この新しく追加されたエントリが指す「次の」エントリになりました。
//================================================ ===============
(B) HashMapで 見たものから、テーブルのサイズ変更- ハッシュは、ハッシュのサイズと容量 (現在と最大) に基づいた決定に基づいてのみ行われます。ハッシュ全体の # エントリ。
「バケット内の最大エントリ数がそのようなものを超えた場合の resize()」のように、個々のバケット サイズに対する再構築やサイズ変更はありません。
可能性は低いですが、残りのハッシュがほとんど空である間に、かなりの数のエントリがバケットにまとめられる可能性があります。
これが事実である場合、つまり、各バケットのサイズに上限がない場合、ハッシュは一定ではなく、線形アクセスです。理論的には 1 つです。$n$ がエントリの総数であるハッシュ内のエントリを取得するには、$O(n)$ 時間かかります。しかし、そうであってはなりません。
//================================================ ===============
上記のパート (A) に欠けているものはないと思います。
パート (B) については完全にはわかりません。これは重大な問題であり、私はこの議論がどれほど正確かを知りたいと思っています。
両方の部分の検証を探しています。
前もって感謝します。
//================================================ ===============
編集：
最大バケット サイズは固定されています。つまり、バケット内のエントリ数が最大値に達するたびにハッシュが再構築され、それが解決されます。アクセス時間は、理論的にも使用中でも単純に一定です。
これは適切に構造化されたものではありませんが、迅速な修正であり、常にアクセスできるようにするためには問題なく機能します。
hashCode はバケット全体に均等に分散される可能性が高く、ハッシュの全体的なサイズのしきい値に達する前にバケットのいずれかがバケット最大値に達する可能性はあまりありません。これは、HashMap の現在のセットアップでも使用されている仮定です。
以下の Peter Lawrey の議論にも基づいています。