The principle of hash method in HashMap

Hash (ハッシュ) は、一般に「ハッシュ」と訳され、「哈希」と直接音訳されることもあります。これは、ハッシュアルゴリズムを通じて任意の長さの入力を固定長の出力に変換するもので、その出力がハッシュ値です。この変換は圧縮マッピングであり、すなわちハッシュ値の空間は通常入力の空間よりもはるかに小さく、異なる入力が同じハッシュ値にマッピングされる可能性があります。したがって、ハッシュ値から入力値を一意に特定することはできません。簡単に言えば、任意の長さのメッセージを一定の長さのメッセージダイジェストに圧縮する関数です。

すべてのハッシュ関数には以下の基本性質があります。同じハッシュ関数に従って計算されたハッシュ値が異なる場合、入力値も必ず異なります。ただし、同じハッシュ関数で計算されたハッシュ値が同じであっても、入力値が同じとは限りません。

異なる 2 つの入力値が同じハッシュ関数に従って計算された結果、同じハッシュ値を持つ現象を衝突 (コリジョン) と呼びます。

一般的なハッシュ関数の手法は以下の通りです。
直接アドレス法：キーワード k または k に一定の定数 (k+c) を加えた値を直接ハッシュアドレスとして使用します。
数字分析法：キーワードの中から比較的均一な分布を持つ数字を抽出し、ハッシュアドレスとします。
除算剰余法：キーワード k をハッシュテーブルの長さ m 以下の数 p で除算し、その剰余をハッシュテーブルのアドレスとして使用します。
分割重畳法：ハッシュテーブルのアドレスの桁数に合わせてキーワードを同じ桁数の複数の部分に分割します。最後の部分は短くなる場合があります。その後、これらの部分を加算し、最上位の繰り上がりを破棄した結果がハッシュアドレスとなります。
二乗法：キーワードの各部の分布が不均一な場合、まずその二乗値を計算し、必要に応じて中間の桁をハッシュアドレスとして取り出します。
疑似乱数法：疑似乱数関数をハッシュ関数として使用します。

衝突については前述の通りです。ハッシュ関数の品質を測る重要な指標は、衝突の発生確率とその解決策です。基本的には、あらゆるハッシュ関数も衝突を完全に回避することはできません。衝突を解決する一般的な方法は以下の通りです。

オープンアドレス法：

オープンアドレス法は、衝突が発生するたびに次の空きハッシュアドレスを探索します。ハッシュテーブルが十分に大きければ、空きハッシュアドレスを必ず見つけてレコードを格納できます。
連鎖アドレス法

ハッシュテーブルの各ユニットを連結リストのヘッドノードとして使用し、ハッシュアドレスが i であるすべての要素が同義語連結リストを形成します。つまり、衝突が発生した場合、そのユニットをヘッドノードとする連結リストの末尾にキーワードを連結します。
リハッシュ

ハッシュアドレスの衝突が発生した場合、別の関数を使用して新しいハッシュアドレスを計算し、衝突が発生しなくなるまで繰り返します。
共通オーバーフロー領域の作成

ハッシュテーブルを基本テーブルとオーバーフローテーブルの 2 つの部分に分割し、衝突した要素をオーバーフローテーブルに格納します。

HashMap のデータ構造
Java には、データを格納するための比較的シンプルな 2 つのデータ構造があります。配列と連結リストです。配列の特徴は、アドレッシングが容易だが挿入と削除が困難であることです。連結リストの特徴は、アドレッシングが困難だが挿入と削除が容易であることです。前述の通り、ハッシュ関数の衝突解決手法の 1 つに連鎖アドレス法があります。これは、配列と連結リストを組み合わせて両方の利点を活かす手法です。連結リストの配列として理解できます。


上記の図からわかるように、左側は明らかに配列であり、配列の各メンバーは連結リストです。このデータ構造が保持するすべての要素には、要素間を連結するためのポインターが含まれています。要素の特徴に基づいて異なる連結リストに割り当て、その特徴を通じて正しい連結リストを特定し、さらにその連結リストから正しい要素を見つけます。ここで、要素の特徴から配列のインデックスを計算する方法がハッシュアルゴリズムであり、すなわち本稿の主人公である hash() 関数 (もちろん indexOf() 関数も含む) です。

hash メソッド
JDK 1.7 の HashMap を例に説明します。ここでは final int hash(Object k) メソッドが定義されており、主に以下のメソッドから参照されます。

まず、JDK の同じバージョン内でも、HashMap、HashTable、ConcurrentHashMap の hash メソッドの実装は異なります。また、JDK の異なるバージョン間 (Java 7 と Java 8) でも違いがあります。これらをすべて包括的に説明します。本稿を読了すれば、hash メソッドを完全に理解できるはずです。

上記のメソッドは主に要素の追加・削除に関連するもので、理解は難しくありません。連結リスト配列に要素を追加または削除する際、まずその要素が連結リスト配列内のどこに格納されるか、すなわちこの配列内のインデックスを特定する必要があります。hash() メソッドの役割は、Key に基づいて HashMap 内の位置を特定することです。HashTable や ConcurrentHashMap でも同様です。

ソースコード分析
まず、JDK の同じバージョン内でも、HashMap、HashTable、ConcurrentHashMap の hash メソッドの実装は異なります。また、JDK の異なるバージョン間 (Java 7 と Java 8) でも違いがあります。これらをすべて包括的に説明します。本稿を読了すれば、hash メソッドを完全に理解できるはずです。

コードの前に、簡単な分析を行いましょう。hash メソッドの役割は、Key に基づいて K-V ペアが連結リスト配列内のどの位置に格納されるかを特定することです。つまり、hash メソッドの入力は Object 型の Key で、出力は int 型の配列インデックスである必要があります。このメソッドを設計するとしたら、どのように実装しますか。

実際にはシンプルで、Object オブジェクトの hashCode() メソッドを呼び出して整数値を取得し、その値を HashMap または HashTable の容量で剰余演算するだけです。その通り、基本原理はこれだけです。具体的な実装では、int hash(Object k) と int indexFor(int h, int length) という 2 つのメソッドで実現されています。ただし、効率などの考慮事項があるため、HashMap の実装はもう少し複雑になっています。

hash：このメソッドは主に Object を整数に変換します。

indexFor：このメソッドは主に hash が生成した整数を連結リスト配列のインデックスに変換します。

Java 7 の HashMap
前述の通り、indexFor メソッドは主に hash が生成した整数を連結リスト配列のインデックスに変換するものです。では、return h & (length-1); は何を意味するのでしょうか。これは実際には剰余演算を行っています。Java では、剰余演算 (%) の代わりにビット演算 (&) を使用します。主な考慮事項は効率です。**ビット演算 (&) の効率は剰余演算 (%) よりもはるかに高いです。主な理由は、ビット演算がメモリ上のデータを直接操作し、10 進数への変換が不要なため、処理速度が非常に速いからです。
**

では、なぜビット演算 (&) で剰余演算 (%) を実現できるのでしょうか。この実現の原理は以下の通りです。

X % 2^n = X & (2^n - 1)

2^n は 2 の n 乗を意味します。つまり、ある数を 2^n で割った剰余は、その数と (2^n - 1) のビット AND 演算と等しくなります。

たとえば n が 3 の場合、2^3 = 8 で、バイナリ表記では 1000 です。2^3 - 1 = 7 で、0111 です。

このとき、X & (2^3 - 1) は X のバイナリの下位 3 ビットを取り出すことに相当します。

バイナリの観点から見ると、X / 8 は X >> 3、すなわち X を右に 3 ビットシフトすることと等しく、このとき X / 8 の商が得られ、取り除かれた部分 (下位 3 ビット) が X % 8、すなわち剰余となります。

上記の説明が理解できなくても問題ありません。このテクニックを覚えておくだけで十分です。いくつかの例で試してみることをお勧めします。

したがって、return h & (length-1); は、length の長さが 2 のべき乗であることを保証しさえすれば、剰余演算を実現できます。HashMap の length は実際に 2 の倍数であり、初期値は 16 で、その後は毎回 2 倍に拡張されます。

indexFor メソッドの分析が完了したので、次は hash メソッドの具体的な原理と実装を分析します。ここまでの内容をまとめます。

HashMap のデータは連結リスト配列に格納されています。HashMap に対して挿入や削除などの操作を行う際、K-V ペアのキー値に基づいて配列のどのインデックスに格納すべきかを特定する必要があります。このキー値からインデックスを求める操作をハッシュ化と呼びます。HashMap の配列には長さがあり、Java ではこの長さは 2 の倍数でなければならず、初期値は 16 と定められています。単純な方法は、まずキー値の hashcode を取得し、hashcode から得られる int 値を配列の長さで剰余演算することです。パフォーマンスを考慮し、Java では剰余演算の代わりに常にビット AND 演算を使用します。

次に、剰余演算もビット演算も、衝突の問題を直接解決できないことがわかります。たとえば、CA11 0000 と 0001 0000 は 0000 1111 に対してビット AND 演算を行うと同じ値になります。

異なる 2 つのキー値が、配列の長さに対してビット AND 演算を行った結果が同じになる。これが衝突でなくて何でしょうか。では、この衝突をどのように解決するのでしょうか。Java の実装を見てみましょう。

このコードは、key の hashCode の計算に摂動を加え、異なる hashCode の上位ビットが異なり下位ビットが同じ場合に生じるハッシュ衝突を防止するためのものです。簡単に言うと、上位の特性と下位の特性を組み合わせてハッシュ衝突の確率を下げるのです。つまり、任意の 1 ビットの変化が最終結果に影響を与えるようにします。

たとえば、「hollishuang」という値の Key を持つ K-V ペアを HashMap に格納する場合を考えます。単純に hashCode を取得すると、「1011000110101110011111010011011」という値が得られます。現在の HashTable のサイズが 16 の場合、すなわち摂動計算なしの場合、最終的に得られるインデックスは 11 です。15 を 32 ビットに拡張したバイナリは「0000000000000000000000000001111」であり、これとビット AND 演算を行うと、最初の 28 ビットが何であっても計算結果は同じになります (0 と任意の数の AND 演算の結果は常に 0 になるため)。

後者の 2 つの hashCode の値もビット演算後に 11 となることがわかります。上記の例の 2 つがどのキーの hashCode かは不明ですが、このようなキーが必ず存在するため、衝突が発生します。

次に、摂動アルゴリズムを適用した場合の最終的な計算結果を確認します。

Java 7 の HashTable

上記は Java 7 の HashMap の hash メソッドと indexOf メソッドの実装です。次は、スレッドセーフな HashTable の実装と、HashMap との違い、そしてその理由を分析します。以下は Java 7 の HashTable の hash メソッドの実装です。

非常にシンプルで、実質的には k に単純なハッシュ化を施して hashCode を取得するだけであることがわかります。また、HashTable には indexOf メソッドがなく、代わりに「int index = (hash & 0x7FFFFFFF) % tab.length;」というコードが使用されています。つまり、HashMap と HashTable は配列インデックスの計算に異なる方法を使用しています。HashMap はビット演算を使用するのに対し、HashTable は直接剰余演算を使用します。

ハッシュ値と 0x7FFFFFFF のビット AND 演算を行う理由は、主に取得するインデックスの最上位ビットを 0 にして正の数を確保するためです。符号付き数では先頭ビットが 0 なら正の数、1 なら負の数を表すからです。

前述の通り、HashMap が剰余演算を使用しない理由は効率向上のためです。HashTable はスレッドセーフなクラスで本質的に遅いため、Java は効率の問題を考慮せずに直接剰余アルゴリズムを使用しているという意見もありますが、実際には完全にそうではありません。Java の設計にも一定の配慮がありますが、効率は確かに HashMap より遅くなっています。

実際、HashTable が単純な剰余演算を使用するのには理由があります。これは HashTable のコンストラクターと拡張関数に関係しますが、紙面の関係上コードは省略し、結論を直接示します。

HashTable のデフォルト初期サイズは 11 で、毎回 2n+1 に拡張されます。

つまり、HashTable の連結リスト配列のデフォルトサイズは素数かつ奇数であり、その後の拡張結果も常に奇数です。

HashTable は可能な限り素数と奇数を容量のサイズとして使用します。ハッシュテーブルのサイズが素数の場合、単純な剰余演算によるハッシュ化の結果がより均一になります (これは数学的に証明できますが、本稿の焦点ではないため詳細は省略します。参考：http://zhaox.github.io/algorithm/2015/06/29/hash)。

ここまでの分析をまとめます。

HashMap のデフォルト初期サイズは 16 で、毎回 2 倍に拡張されます。

HashTable のデフォルト初期サイズは 11 で、毎回 2n+1 に拡張されます。

ハッシュテーブルのサイズが素数の場合、単純な剰余演算によるハッシュ化の結果がより均一になるため、この観点からは HashTable のハッシュテーブルサイズ選択の方が優れているように見えます。ハッシュ結果の分散が大きいほど、効果が良くなるからです。

剰余演算の計算において、法が 2 のべき乗の場合、ビット演算を直接使用して結果を取得できるため、除算よりもはるかに効率的です。そのため、ハッシュ計算の効率では HashMap が優れています。

ただし、HashMap は効率向上のためにビット演算をハッシュ化の代わりに使用しているため、ハッシュ分布が不均一になる問題が生じます。この問題を解決するために、HashMap はハッシュアルゴリズムを改良し、摂動計算を導入しています。