Java は Hashtable クラスを実装するためにどのようなハッシュ関数を使用しますか? 質問する

OpenJDK の HashMap にキーが追加されたり、HashMap からキーが要求されたりする場合、実行フローは次のようになります。

1. キーは、開発者が定義した方法を使用して 32 ビット値に変換されますhashCode()。
2. 32ビットの値は、2番目のハッシュ関数(Andrew の回答にはソース コードが含まれています) をハッシュ テーブル内のオフセットに挿入します。この 2 番目のハッシュ関数は HashMap の実装によって提供され、開発者がオーバーライドすることはできません。
3. ハッシュ テーブルの対応するエントリには、リンク リストへの参照が含まれます。キーがハッシュ テーブルにまだ存在しない場合は、null が含まれます。衝突がある場合 (同じオフセットを持つ複数のキー)、キーとその値は、単一のリンク リストに単純に収集されます。

ハッシュテーブルのサイズが適切に大きく選ばれると、衝突の回数は制限されます。したがって、1回の検索には平均して一定の時間しかかかりません。これを予想される定数時間ただし、攻撃者がハッシュ テーブルに挿入されたキーを制御し、使用されているハッシュ アルゴリズムに関する知識を持っている場合、ハッシュ衝突を多数引き起こして、線形検索時間を強制することができます。そのため、最近、ハッシュ テーブルの実装の一部が変更され、どのキーが衝突を引き起こすかを攻撃者が予測しにくくするランダム要素が含まれるようになりました。

いくつかのASCIIアート

key.hashCode()
     |
     | 32-bit value
     |                              hash table
     V                            +------------+    +----------------------+
HashMap.hash() --+                | reference  | -> | key1 | value1 | null |
                 |                |------------|    +----------------------+
                 | modulo size    | null       |
                 | = offset       |------------|    +---------------------+
                 +--------------> | reference  | -> | key2 | value2 | ref |
                                  |------------|    +---------------------+
                                  |    ....    |                       |
                                                      +----------------+
                                                      V
                                                    +----------------------+
                                                    | key3 | value3 | null |
                                                    +----------------------+