27

一般的な問題: ドットがまばらに配置された大きな 2 次元ポイント空間があります。黒い点がちりばめられた大きな白いキャンバスと考えてください。これらのドットを何度も繰り返して検索する必要があります。キャンバス (ポイント スペース) は、int の制限に接する巨大なサイズになる可能性があり、そこにポイントを設定する前にそのサイズは不明です。

それはハッシュのアイデアに私をもたらしました：

理想: 2D ポイントを取り、一意の uint32 を返すハッシュ関数が必要です。衝突が起こらないように。Canvas 上のドットの数は、uint32 で簡単に数えられると想定できます。

重要:キャンバスのサイズを事前に知ることは不可能です (変更される場合もあります)。

キャンバス幅 * y + x

悲しいことに問題外です。

私も非常に素朴なことを試しました

abs(x) + abs(y)

しかし、それでは衝突が多すぎます。

妥協:衝突の可能性が非常に低い キーを提供するハッシュ関数。

アイデアはありますか？助けてくれてありがとう。

よろしく、 アンドレアス T.

編集:質問テキストで何かを変更する必要がありました:「uint32でキャンバスのポイント数をカウントできる」という仮定を「キャンバス上のドットをカウントできる(または保存する座標ペアの数)」に変更しましたsqrt(max(uint32))xsqrt(max(uint32)) サイズのキャンバスがあり、16 ビット シフトと OR で一意に表現できるため、元の質問はあまり意味がありませんでした。

すべての答えは、更新された仮定で最も理にかなっているので、これで問題ないことを願っています

そのために残念。

4

11 に答える 11

36

対のカントール列挙 

   n = ((x + y)*(x + y + 1)/2) + y

元のキャンバス幅 * y + x に最も近いため、興味深いかもしれませんが、任意の x または y に対して機能します。しかし、実際の int32 ハッシュの場合は、整数のペアを整数にマッピングするのではなく、Bob Jenkin のmixなどのビット操作を行い、x、y およびソルトでそれを呼び出す方がよいでしょう。

于 2009-03-25T17:28:43.970 に答える
18

衝突のないことが保証されているハッシュ関数は、ハッシュ関数ではありません:)

ハッシュ関数を使用する代わりに、バイナリ スペース パーティション ツリー (BSP) または XY ツリー (密接に関連) の使用を検討できます。

2 つの uint32 を 1 つの uint32 にハッシュしたい場合は、ビットの半分が破棄されるため、Y & 0xFFFF などを使用しないでください。次のようなことをします

(x * 0x1f1f1f1f) ^ y

(ハッシュ関数が可換でないことを確認するために、最初に変数の 1 つを変換する必要があります)

于 2009-03-25T16:57:00.553 に答える
6

Emil と同様ですが、16 ビット オーバーフローをx、衝突が少なく、計算に必要な命令が少ない方法で処理します。

hash = ( y << 16 ) ^ x;
于 2009-03-25T16:56:12.410 に答える
2

あなたの「理想」は不可能です。

マッピング (x, y) -> i が必要です。ここで、x、y、および i はすべて 32 ビットの量であり、i の重複値を生成しないことが保証されています。

理由は次のとおりです。hash(x, y) が異なる整数値を与える関数 hash() があるとします。x には 2^32 (約 40 億) の値があり、y には 2^32 の値があります。したがって、hash(x, y) には 2^64 (約 1600 万兆) の可能な結果があります。しかし、32 ビット int には 2^32 の可能な値しかないため、hash() の結果は 32 ビット int に収まりません。

http://en.wikipedia.org/wiki/Counting_argumentも参照してください。

一般に、衝突に対処できるようにデータ構造を常に設計する必要があります。(ただし、ハッシュが非常に長く (少なくとも 128 ビット)、非常に優れており (暗号化ハッシュ関数を使用)、幸運を感じている場合を除きます)。

于 2009-03-25T18:38:02.073 に答える
1

できるよ

a >= b ? a * a + a + b : a + b * b

ここから撮影。

これは、正の平面のポイントに対して機能します。座標が負の軸にもある場合は、次のことを行う必要があります。

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

ただし、出力を制限するにuintは、入力の上限を維持する必要があります。もしそうなら、あなたは境界を知っていることがわかります。言い換えれば、プログラミングでは、入力と出力が可能な整数型について考えずに関数を書くことは非現実的であり、そうであれば、すべての整数型に下限と上限が確実に存在します。

public uint GetHashCode(whatever a, whatever b)
{
    if (a > ushort.MaxValue || b > ushort.MaxValue || 
        a < ushort.MinValue || b < ushort.MinValue)
    {    
        throw new ArgumentOutOfRangeException();
    }

    return (uint)(a * short.MaxValue + b); //very good space/speed efficiency
    //or whatever your function is.
}

未知の範囲の入力に対して厳密に出力したい場合はuint、その範囲に応じて妥当な量の衝突が発生します。私が提案するのは、オーバーフローする可能性があるがチェックされない関数を持つことです。Emil のソリューションは、C# で優れています。

return unchecked((uint)((a & 0xffff) << 16 | (b & 0xffff)));

多数のオプションについては、一意かつ決定論的な方法で 2 つの整数を 1 つにマッピングするを参照してください。

于 2012-12-27T08:37:11.277 に答える
1

多分？

hash = ((y & 0xFFFF) << 16) | (x & 0xFFFF);

x と y を 16 ビット整数として格納できる限り機能します。ただし、これがより大きな整数に対してどのくらいの衝突を引き起こすかについてはわかりません。1 つの考えとしては、この方式を引き続き使用するが、2^16 のモジュラスを取得するなどの圧縮方式と組み合わせることが考えられます。

于 2009-03-25T16:53:33.477 に答える
1

ユースケースによっては、 Quadtreeを使用してポイントをブランチ名の文字列に置き換えることができる場合があります。これは実際にはポイントのまばらな表現であり、キャンバスからポイントを追加するときにブランチを追加してキャンバスを拡張するカスタム Quadtree 構造が必要になりますが、衝突を回避し、迅速な最近傍検索などの利点があります。

于 2014-08-29T10:18:16.097 に答える
1

できる場合 = ((y & 0xffff) << 16) | (x & 0xffff) その後、Thomas Wang のような可逆的な 32 ビット ミックスを a に適用できます。

uint32_t hash( uint32_t a)
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
}

こうすることで、一方の次元の上位ビットと他方の次元の下位ビットではなく、ランダムに見える結果が得られます。

于 2010-08-05T04:59:01.840 に答える
0

すべてのオブジェクト (整数などのプリミティブなものも含む) に組み込みのハッシュ関数が実装されている言語またはプラットフォームを既に使用している場合 (Java プラットフォーム Java などの言語、C# などの .NET プラットフォーム言語、Python、Ruby など)。ビルトインのハッシュ値を構成要素として使用し、独自の「ハッシュ フレーバー」をミックスに追加できます。お気に入り：

// C# code snippet 
public class SomeVerySimplePoint { 

public int X;
public int Y;

public override int GetHashCode() {
   return ( Y.GetHashCode() << 16 ) ^ X.GetHashCode();
}

}

また、計算時間、必要なメモリ、キーの衝突数、エッジ ケース (大きすぎる値または小さすぎる値) などのさまざまな側面について、考えられるハッシュ生成アルゴリズムの比較ごとに「事前定義された百万点セット」のようなテスト ケースを実行すると便利な場合があります。

于 2012-11-04T08:18:05.997 に答える