HashTable/HashMapは配列ですか？

Question

私はハッシングに混乱しています：

私はHashtable/HashMap（key、value）を使うとき、最初に私は内部データ構造が（メモリに既に割り当てられている）配列であると理解しました。

Javaのhashcode（）メソッドはint型の戻り値を持っているので、このハッシュ値は配列のインデックスとして使用され、この場合、配列には2つの32のエントリが必要です実際に何が起こるかではない。

Javaはhashcode（）からインデックスを作成するので、範囲が狭いですか？

回答：

人は、ドキュメントの下から指摘したように：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java

HashMapのアレイです。 hashcode（）は再びハッシュされますが、整数であり、配列内のインデックスは次のようになります：h &（length-1）;配列の長さが2^nならば、インデックスは再ハッシュ値から最初のnビットを取ると思います。

Answer 1

一般に、基本データ構造は実際には配列になります。

エントリを見つける必要のあるメソッド（または新しいオブジェクトを追加する場合は空のギャップ）は、ハッシュコードを（通常はモジュロで）配列のサイズに合うものに縮小し、これをその配列へのインデックス

もちろん、多くのオブジェクトが同じインデックスに縮小されるハッシュコードを持つ可能性があるため、衝突の可能性が高くなります（複数のオブジェクトが全く同じハッシュコードを持つ可能性が高いためです。これに対処するための戦略は、通常、リンクリストのような構造を使用するか、一致した最初のスロットが非等価キーで占有されていた場合に別のスロットを選択する仕組みです。

これはコストがかかるため、このような衝突はより遅いものになり、悪いケースでは実際にはO（n）になります（O（n）も同様に遅くなります）。

内部ストアのサイズを大きくすると、一般的にはこれが改善されます（特に、以前のサイズの倍数でない場合）。そのため、インデックスを見つけるためにハッシュコードを減らした操作では、同じインデックスに衝突した後、再び同じインデックスを与える）。いくつかのメカニズムは、ある特定のケースでは（完全なハッシュコードを持たないオブジェクトとの特定のパーセンテージ、特定の数の衝突など）、絶対に必要となる前に内部サイズを増加させます（空き領域が残ります）。

これは、ハッシュコードが非常に悪い場合を除き（実際にはまったく同じであることが最も明白です）、操作の順序はO（1）のままです。

Answer 2

Java HashMapの構造は単なる配列ではありません。これは配列ですが、2^31のエントリ（intは符号付きタイプです）ではなく、初期値では16のバケット数が少数です。 HashMapのJavadocsではそのことを説明しています。

エントリ数が容量の特定の画分（「負荷率）を超えると、アレイはより大きなサイズに成長する。

配列の各要素は、唯一つのエントリを保持していません。配列の各要素は、エントリの構造（現在は赤黒のツリー、以前はリスト）を保持しています。構造体の各エントリには、配列内の同じバケット位置に内部的に変換されるハッシュコードがあります。

あなたはこのタイプのドキュメントを読んでいますか？ http://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

あなたは本当にすべきです。