longたとえば、値がLong.MIN_VALUE = 0x80...0(-2^63) とLong.MAX_VALUE = 0x7f...f(2^63 - 1)の間の整数型があります。Long.MAX_VALUEきれいで効率的な方法で、同じ型 (つまり 1 と の間) の正の整数に ~50% の衝突でハッシュしたいと考えています。
私の最初の試みは次のようなものでした：
Math.abs(x) + 1(x & Long.MAX_VALUE) + 1しかし、それらおよび同様のアプローチには、特定の値、つまりxis 0/ Long.MIN_VALUE/の場合に常に問題がありますLong.MAX_VALUE。もちろん、単純な解決策は 2 つの if ステートメントを使用することですが、よりクリーンで、より短く、より高速なものを探しています。何か案は？
注: ブール値への暗黙的な変換がなく、シフト セマンティクスが定義されている Java で作業していると仮定します。
最も簡単なアプローチは、符号ビットをゼロにしてから、ゼロを他の値にマップすることです。
Long y = x & Long.MAX_VALUE;
return (y == 0)? 42: y;
これは単純で、if / 二項演算子を1つだけ使用し、平均で最大50％の衝突率を示します。1つの欠点があります。それは、4つの異なる値（0、42、MIN_VALUE、MIN_VALUE + 42）を1つの値（42）にマップします。したがって、この値の場合は75％の衝突が発生しますが、他の値の場合は正確に50％です。
衝突をより均等に分散させることが望ましい場合があります。
return (x == 0)? 42: (x == Long.MIN_VALUE) ? 142: x & Long.MAX_VALUE;
このコードは、2つの値に対して67％の衝突を与え、他の値に対して50％の衝突を与えます。衝突をより均等に分散することはできませんが、これら2つの最も衝突する値を選択することは可能です。欠点は、このコードが2つのif/ternary演算子を使用することです。
1つのif/三項演算子のみを使用しながら、単一の値で75％の衝突を回避することができます。
Long y = x & Long.MAX_VALUE;
return (y == 0)? 42 - (x >> 7): y;
このコードは、2つの値に対して67％の衝突を与え、他の値に対して50％の衝突を与えます。これらの最も衝突する値を選択する自由は少なくなります。0は42にマップされます（代わりにほとんどすべての値を選択できます）。MIN_VALUEはにマップされ42 - (MIN_VALUE >> 7)ます（MIN_VALUEは1から63までの任意の値でシフトできますが、A - (MIN_VALUE >> B)オーバーフローしないように注意してください）。
条件演算子なしで（ただし、より複雑なコードで）同じ結果（2つの値で67％の衝突、他の値で50％の衝突）を取得することは可能です。
Long y = x - 1 - ((x >> 63) << 1);
Long z = y + 1 + (y >> 63);
return z & Long.MAX_VALUE;
これにより、値「1」と「MAX_VALUE」に対して67％の衝突が発生します。他のいくつかの値に対してほとんどの衝突を取得する方が便利な場合は、このアルゴリズムをに適用するだけですx + A。ここで、「A」は任意の数値です。
このソリューションの改良版：
Long y = x + 1 + ((x >> 63) << 1);
Long z = y - (y >> 63);
return z & Long.MAX_VALUE;
すべての値を正のスペースに折りたたむと仮定して、符号ビットをゼロにしないのはなぜですか？
MAX_VALUEがゼロ符号ビットの後に1が続くという事実を利用することにより、単一のビット演算でこれを行うことができます。
int positive = value & Integer.MAX_VALUE;
または長い間：
long positive = value & Long.MAX_VALUE;
疑似ランダム品質の「より良い」ハッシュが必要な場合は、最初に別のハッシュ関数を使用して値をpssすることをお勧めします。私のお気に入りの高速ハッシュは、 GeorgeMarsagliaによるXORshiftファミリーです。これらには、int / long数値空間全体を完全にマップするという優れた特性があるため、符号ビットをゼロにした後でも、正確に50％の衝突が発生します。
JavaでのXORshiftの簡単な実装は次のとおりです。
public static final long xorShift64(long a) {
a ^= (a << 21);
a ^= (a >>> 35);
a ^= (a << 4);
return a;
}
public static final int xorShift32(int a) {
a ^= (a << 13);
a ^= (a >>> 17);
a ^= (a << 5);
return a;
}
符号なしシフト演算子を使用することにより、条件なしで単一の式でそれを行うことができます。
public static int makePositive(int x) {
return (x >>> 1) + (~x >>> 31);
}
値が正の場合は、おそらく直接使用できます。それ以外の場合は、すべてのビットを反転します。
x >= 0 ? hash = x : hash = x ^ Long.MIN_VALUE
xただし、の値が相関している場合（つまり、類似したオブジェクトがの類似した値を生成する場合x）、この値をもう少しスクランブルする必要があります。
hash = a * (hash + b) % (Long.MAX_VALUE) + 1
いくつかの正の定数aとbについてaは、かなり大きくする必要があり、それが常ににマップされるのをb防ぎます。これにより、全体が[0、Long.MAX_VALUE]ではなく[1、Long.MAX_VALUE]にマップされます。の値を変更することで、2つの異なるハッシュ関数を必要とするクックハッシュなどのより複雑なハッシュ関数を実装することもできます。01ab
このようなソリューションは、使用するたびに同じ値に対して「奇妙な衝突分布」を提供するソリューションではなく、間違いなく好まれるはずです。
情報理論の観点から、2^64値にマッピングする2^63-1値があります。
そのため、モジュラス演算子を使用したマッピングは、常に非負の結果になるため、自明です。
y = 1 + x % 0x7fffffffffffffff; // the constant is 2^63-1
これはかなり高価になる可能性があるので、他に何が可能ですか？
簡単な計算2^64 = 2 * (2^63 - 1) + 2では、2 つのソース値が 1 つのターゲット値にマッピングされることになりますが、2 つの特殊なケース (3 つが 1 つになる) を除きます。これらを 2 つの特別な 64 ビット値と考えて、x1と と呼びx2、それぞれが他の 2 つのソース値とターゲットを共有します。上記のmod式では、これは「ラッピング」によって発生します。ターゲット値y=2^31-2にy=2^31-3は 3 つのマッピングがあります。他はすべて2つです。とにかくもっと複雑なものを使わなければならないのでmod、低コストで好きな場所に特別な値をマッピングする方法を探しましょう
説明のために、[-8..7] の 4 ビット符号付き intを64 ビット空間ではなく x[1..7] にマッピングしてみましょう。y
簡単なコースは、[1..7]xの値をそれ自体にマップすることです。その後、問題xは [-8..0] の [1..7] へのマッピングに縮小されyます。上記のように、ここには 9 つのソース値があり、ターゲットは 7 つしかないことに注意してください。
明らかに多くの戦略があります。この時点で、おそらくガジリオンを見ることができます。特に簡単なものを 1 つだけ説明します。
y = 1 - x特殊なケースを除くすべての値をみましょうx1 == -8およびx2 == -7. したがって、ハッシュ関数全体は次のようになります
y = x <= -7 ? S(x) : x <= 0 ? 1 - x : x;
以下は、とがマップされS(x)ている場所を示す単純な関数です。データについて知っていることに基づいて選択します。たとえば、目標値が高い可能性が低いと思われる場合は、 を使用してそれらを 6 と 7 にマッピングします。x1x2SS(x) = -1 - x
最終的なマッピングは次のとおりです。
-8: 7 -7: 6 -6: 7 -5: 6 -4: 5 -3: 4 -2: 3 -1: 2
0: 1 1: 1 2: 2 3: 3 4: 4 5: 5 6: 6 7: 7
このロジックを 64 ビット空間にすると、次のようになります。
y = (x <= Long.MIN_VALUE + 1) ? -1 - x : x <= 0 ? 1 - x : x;
このフレームワーク内では、他にも多くの種類のチューニングが可能です。
私は、最も単純でありながら完全に時間を浪費するわけではないバージョンを選択します。
public static long postiveHash(final long hash) {
final long result = hash & Long.MAX_VALUE;
return (result != 0) ? result : (hash == 0 ? 1 : 2);
}
この実装は、 2 つの可能な入力 (0 と MIN_VALUE)を除くすべてに対して 1 つの条件演算を支払います。これら 2 つには、2 番目の条件で異なる値のマッピングが割り当てられます。(コードの) シンプルさと (計算上の) 複雑さのより良い組み合わせが得られるとは思えません。
もちろん、より悪いディストリビューションで暮らすことができれば、それはずっと簡単になります. スペースを 1/2 -1 ではなく 1/4 に制限すると、次のようになります。
public static long badDistribution(final long hash) {
return (hash & -4) + 1;
}
入力値をLong.MAX_VALUEとAND演算し、1とORするだけです。他に何も必要ありません。
元：
long hash = (input & Long.MAX_VALUE) | 1;
念のために言っておきますが、あなたは長いので、それをintにハッシュしたいですか？
あなたができる...
(int) x // This results in a meaningless number, but it works
(int) (x & 0xffffffffl) // This will give you just the low order bits
(int) (x >> 32) // This will give you just the high order bits
((Long) x).hashcode() // This is the high and low order bits XORed together
あなたが長く保ちたいなら、あなたはすることができます...
x & 0x7fffffffffffffffl // This will just ignore the sign, Long.MIN_VALUE -> 0
x & Long.MAX_VALUE // Should be the same I think
0を取得するのは良くない場合...
x & 0x7ffffffffffffffel + 1 // This has a 75% collision rate.
大声で考えているだけ...
((x & Long.MAX_VALUE) << 1) + 1 // I think this is also 75%
私はあなたが75％で大丈夫であるか、少し醜くなる必要があると思います：
(x > 0) ? x : (x < 0) ? x & Long.MAX_VALUE : 7
これは最も単純なようです：
(x % Long.MAX_VALUE) + 1
与えられたすべての方法の速度比較に興味があります。