3

特定のプロパティを持つデータ構造に対して衝突のないハッシュ関数を作成することは可能ですか？

  1. データ構造はint[][][]です。
  2. 重複は含まれていません
  3. それに含まれる整数の範囲が定義されます。それが0..1000であるとしましょう、最大整数は間違いなく10000以下です。

大きな問題は、このハッシュ関数も非常に高速である必要があることです。そのようなハッシュ関数を作成する方法はありますか？整数の範囲に応じて、実行時にたぶん？

追加：このハッシュ関数の目的は、特定の組み合わせが処理されたかどうかを簡単にチェックすることです。したがって、データ構造内の数値の組み合わせが処理されるときに、ハッシュ値を計算して保存します。次に、データ構造内の数値の別の組み合わせを処理するときに、ハッシュ値を比較します。

4

3 に答える 3

6

あなたが欲しいのは「完璧なハッシュ」あるいは「最小限の完璧なハッシュ」だと思います。

http://en.wikipedia.org/wiki/Perfect_hash_function

編集：そうは言っても、[0 ... 1000]を超えることは決してないだろうと確信している場合は、何をする必要があるかに応じて、結果を配列に直接「バケット化」することができます。多くの要素がない場合、その配列はまばらになります（したがって、少し無駄になります）が、[0 ...1000]からオブジェクト[1001]（またはint[1001]または何でも）おそらくするでしょう。

于 2010-04-21T20:34:43.810 に答える
0

64ビット値を使用し、階層の各レベルの場所をビットの1つのセクションに格納するとどうなりますか？

（頭のてっぺんから）のようなもの：hash = (a << 34) | (b << 17) | (c)

于 2010-04-21T20:38:30.237 に答える
0

データセット用のハッシュを見つけるには多くの計算時間がかかる可能性があるため、完全なハッシュは実現できない可能性があります。

特定のx、y、zの組み合わせが処理されたことを意味しますbool[][][]か？true以下は、3次元ビット配列のプロトタイプです。Int32の制限により、これは最大インデックスが約1,024までしか機能しません（ただし、128 MB以内に収まります）。BitArray [] []を作成すると、10,000に達する可能性があります。ただし、116 GBを超えるRAMを占有するため、このサイズではおそらく実用的ではありません。

正確な問題のサイズとニーズによっては、（衝突のある）単純な古いハッシュテーブルが最善の策かもしれません。そうは言っても、プロトタイプコードは次のとおりです。

public class ThreeDimensionalBitArray
{
    // todo: consider making the size configurable
    private const int MAX_INDEX = 1000;

    private BitArray _bits = new BitArray(MAX_INDEX * MAX_INDEX * MAX_INDEX);

    public bool this[int x, int y, int z]
    {
        get { return _bits[getBitIndex(x, y, z)]; }
        set { _bits[getBitIndex(x, y, z)] = value; }
    }

    public ThreeDimensionalBitArray()
    {
    }

    private static int getBitIndex(int x, int y, int z)
    {
        // todo: bounds check x, y, and z

        return (x * MAX_INDEX * MAX_INDEX) + (y * MAX_INDEX) + z;
    }
}


public class BitArrayExample
{
    public static void Main()
    {
        ThreeDimensionalBitArray bitArray = new ThreeDimensionalBitArray();
        Console.WriteLine(bitArray[500, 600, 700]); // "false"
        bitArray[500, 600, 700] = true;
        Console.WriteLine(bitArray[500, 600, 700]); // "true"
    }
}
于 2016-05-15T03:54:23.903 に答える