HashMapのindexFor方法

844 ワード

HashMapのIndexOf方法については、なぜ&を使うのか、そしてlength-1と演算するのか、今まで考えてみました。
static int indexFor(int h, int length) {  
     return h & (length-1);  
 } 
前提
まず、一般的なHash散逸のアルゴリズムはすべてmod表の長さであることを知っています。例えば、h% lengthですが、HashMapはビット演算を使います。
分析
HashMapの初期サイズと拡張容量は2の二乗で行います。言い換えれば、length-1をバイナリに変換すると、容量が16なら、length-1は1111となります。ビット演算の'と'ルールは2つの1が1で、0に遭遇すると0になります。つまり、length-1のいずれかが1となります。対応する位置の計算結果は、hにおける対応する位置(hにおいては対応するビットが0、対応するビット結果が0、hに対応するビットが1、対応するビット結果が1となります。このように2つの結果があります。ただし、length-1のいずれかが0であれば、hの中の対応桁の数に関わらず、対応ビットの結果は0であるため、2つのhを同じ結果にします。これはhash衝突です。チャレングス-1は全部1の数です。結果として自然にhash衝突を最小化します。
比較
よく観察してみると、古い方法であるh% lengthとh&( length-1)で得られた結果は実は値ですが、なぜshmapでは後者を使うのですか?
1.length(2の整数乗)の特殊性は、length-1の特殊性(バイナリはすべて1)をもたらします。
2.ビット演算は10進数演算より早く、hashmap拡張もビット拡張であるため、比較して後者を選択しました。