今日は Java のソースコードの put 関数におけるハッシュテーブルのインデックス取得について理解できなかった。深く掘り下げてみたら、ようやくその理由がわかった。記録しておく。
今日は Java のソースコードの put 関数におけるハッシュテーブルのインデックス取得について理解できなかった。深く掘り下げてみたら、ようやくその理由がわかった。記録しておく。
まず理解すべきことは、HashMap のハッシュテーブルの長さは 2^n であるため、以下の公式がある：
(n - 1) & hash = hash % n
ここで n はハッシュテーブルの長さであり、2 の累乗である（順序に注意）。hash% n は、ハッシュ値を対応するテーブルの位置にマッピングするために使用する通常の方法であり、hash をテーブルの長さで割った余りを取ることで、必ずテーブルの長さより小さい数が得られる。そうすれば、value を対応する位置に置くだけでよい。重要なのは、
(n - 1) & hash という式で、これはテーブルの長さから 1 を引いて hash とビット AND 演算を行うものである。まず、ビット AND 演算について説明する：
AND 演算は二進数の演算である：
演算規則：0&0=0;0&1=0;1&0=0;1&1=1; つまり、両方が 1 でなければ 1 にはならず、他はすべて 0 になる。
例を挙げると：
01011（十進法の 11）
00111（十進法の 7）
-—–
00011（十進法の 3）
OK、資料を調べているときにビット演算に関する知識も調べた：
| 記号 | 説明 | 演算規則 |
|---|---|---|
| & | AND | 両方のビットが1のときだけ結果が1になる |
| | | OR | 両方のビットが0のときだけ結果が0になる |
| ^ | XOR | 両方のビットが同じなら0、異なれば1になる |
| ~ | NOT | 0は1に、1は0になる |
| << | 左シフト | 各ビットを左にシフトし、高位は捨て、低位は0で埋める |
| >> | 右シフト | 各ビットを右にシフトし、符号なし数の場合は高位を0で埋め、符号付き数は異なる |
左シフトは二進数にとって * 2 に相当し、右シフトは / 2 に相当する。
十進法の例を挙げると：10 を左シフトすると 100 になり、10 倍になる。右シフトすると 1 になり、10 で割ることに相当する；非常に面白い。驚くべきことだ。
さて、正伝を演じた後、余りの計算について話を戻すと、どうして余りの計算が AND 演算に変わるのか？
上記で述べた右シフトの演算は、二進数にとって右シフトは 2 で割ることに相当するが、しかし！重要な点がある。シフトアウトされた数は 2 の余りである！不思議ではないか！例を見てみよう：
101001>>1 = 10100 余り 1、これは 41%2 の余り 1 に対応する。次に進むと
101001>>2 = 1010 余り 01、これは 41%4 の余り 1 に対応する。続けて
101001>>3 = 101 余り 001、これは 41%8 の余り 1 に対応する。進め
101001>>4 = 10 余り 1001、これは 41%16 の余り 9 に対応する。
したがって、hash% x において、x が 2^n の場合、hash の二進数の低 n ビット数に等しい。
では、低 n ビット数をどうやって取得するのか？2^n の数は常に n+1 ビットが 1 で、残りは 0 である数であることがわかる。例えば
10 は 2、100 は 4、1000 は 8、10000 は 16 である。
それに対して、2^n-1 は n+1 ビットが 0 で、残りが 1 である数である。例えば：
01 は 1、011 は 3、0111 は 7、01111 は 15 である。この数が hash と AND 演算を行うと、ちょうど hash の低 n ビット数が保持される。これが驚くべきことである。
したがって、**hash% n=hash&(n-1)** は、2 が 2 の累乗であるときに成り立つ。では、これを行うことにどんな利点があるのか？それは効率を大幅に向上させることができる。ビット演算（&）の効率は、モジュロ演算（%）の代わりに使用する場合よりもはるかに高い。主な理由は、ビット演算が直接メモリデータを操作するため、十進法に変換する必要がなく、処理速度が非常に速いからである。HashMap のハッシュテーブルのインデックス取得は頻繁に実行される部分である。これにより、コストが大幅に節約される。
ある大物の言葉を引用すると、非常に的確に表現されている：
配列の長さが 2 の整数乗である場合、つまり偶数であるとき、length-1 は奇数であり、奇数の二進数の最後のビットは 1 であるため、hash (key) がいくらであっても、hash (key)&(length-1) の二進数の最後のビットは 0 である可能性もあれば 1 である可能性もあり、hash (key) に依存する。つまり、hash (key) が奇数であれば、配列の奇数番目の位置にマッピングされる。
もし length が奇数であれば、length-1 は偶数であり、偶数の二進数の最後のビットは 0 であるため、hash (key) が奇数であっても偶数であっても、その要素は配列の偶数番目の位置にマッピングされ、奇数の位置には何も要素がない！
したがって、配列の長さが 2 の整数乗であるとき、ハッシュ衝突の確率は少なくとも半分に減少し、すべての要素も配列に均等に分布することができる。
注：余りの計算：a % b は、a - (a /b) * b の計算に相当する。
この部分を理解するために、本当に多くの資料を探した。百度は本当にひどいと言わざるを得ない。会社では Google や StackOverFlow にアクセスできないため、資料を調べる効率に影響を与える。
しかし、以下のこの記事が私のトリガーとなった。
ビット AND 演算と余り