3

拡張可能なハッシュを書きたい。wikiで、Python での適切な実装を見つけました。しかし、このコードは最下位ビットを使用するため、値のハッシュ1101がd = 1で1あり、値のハッシュd = 2が01. 最上位ビットを使用したいと思います。例: ハッシュ1101、d = 1値は1、d = 2値は11です。それを行う簡単な方法はありますか？やってみましたが、できません。

最下位ビットを使用する理由を理解していますか?

多かれ少なかれ。配列を使用すると効率的になります。わかりましたので、ハッシュ関数の場合、4バイト整数の最小4ビットを左から右に使用したいと思います。

h = hash(k) 
h = h & 0xf #use mask to get four least bits
p = self.pp[ h >> ( 4 - GD)]

そして、それは機能しません。理由はわかりません。

4

1 に答える 1

2

最下位ビットを使用してハッシュを計算することは、ANDビット演算のみを必要とするため、ハッシュを計算するための最速の方法です。これは非常に人気があります。

最上位ビットを使用したハッシュの実装（C）を次に示します。最上位ビットを直接知る方法がないため、残りの値に指定されたビット数しかないことを繰り返しテストします。

int significantHash(int value, int bits) {
    int mask = (1 << bits) - 1;
    while (value > mask) {
        value >>= 1;
    }
    return value;
}

数値のすべてのビットを利用するオーバーラップハッシュをお勧めします。基本的に、同数のビットの部分に数を削減し、それらをXORします。最下位のハッシュよりは低速ですが、最下位のハッシュよりは高速です。何よりも、他の2つの方法よりも分散が優れているため、ハッシュする必要のある数値に特定のビット関連パターンがある場合に適しています。

int overlappingHash(int value, int bits) {
    int mask = (1 << bits) - 1;
    int answer = 0;
    do {
        answer ^= (value & mask);
        value >>= bits;
    } while (value > 0);
    return answer;
}
于 2013-02-01T18:38:37.403 に答える