21

値をハッシュしようとしています

10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0

衝突を起こさずにサイズ13の配列にマップする関数が必要です。

私はこれを考えてグーグルで数時間を費やしましたが、これを理解することはできません。私は実行可能な解決策に近づいていません。

この種のハッシュ関数を見つけるにはどうすればよいですか？gperfで遊んだことがありますが、よくわからず、探していた結果が得られませんでした。

4

7 に答える 7

24

正確なキーがわかっている場合は、完全なハッシュ関数を作成するのは簡単です-

int hash (int n) {
  switch (n) {
    case 10:   return 0;
    case 100:  return 1;
    case 32:   return 2;
    // ...
    default:   return -1;
  }
}
于 2010-11-09T06:10:05.493 に答える
12

一つ見つかった

私はいくつかのことを試し、半手動で見つけました：

(n ^ 28) % 13

半手動の部分は、さまざまなパラメーターを使用して候補関数をテストするために使用した次のルビースクリプトでした。

t = [10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0]
(1..200).each do |i|
  t2 = t.map { |e| (e ^ i) % 13 }
  puts i if t2.uniq.length == t.length
end
于 2010-11-09T06:17:42.530 に答える
5

一部のプラットフォーム（組み込みなど）では、モジュロ演算はコストがかかるため、% 13回避することをお勧めします。ただしAND、下位ビットの演算は安価であり、2の累乗のモジュロと同等です。

11個のデータポイントの完全なハッシュを検索するための簡単なプログラム（Pythonで）を作成してみました。たとえば、((x << a) ^ (x << b)) & 0xF（は、& 0xFと同等で% 16、結果は0..15の範囲になります）などの簡単な形式を使用します。0..15の範囲のインデックス（Cマクロとして表される）を与える次の衝突のないハッシュを見つけることができました：

#define HASH(x)    ((((x) << 2) ^ ((x) >> 2)) & 0xF)

これが私が使用したPythonプログラムです：

data = [ 10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0 ]

def shift_right(value, shift_value):
    """Shift right that allows for negative values, which shift left
    (Python shift operator doesn't allow negative shift values)"""
    if shift_value == None:
        return 0
    if shift_value < 0:
        return value << (-shift_value)
    else:
        return value >> shift_value

def find_hash():
    def hashf(val, i, j = None, k = None):
        return (shift_right(val, i) ^ shift_right(val, j) ^ shift_right(val, k)) & 0xF

    for i in xrange(-7, 8):
        for j in xrange(i, 8):
            #for k in xrange(j, 8):
                #j = None
                k = None
                outputs = set()
                for val in data:
                    hash_val = hashf(val, i, j, k)
                    if hash_val >= 13:
                        pass
                        #break
                    if hash_val in outputs:
                        break
                    else:
                        outputs.add(hash_val)
                else:
                    print i, j, k, outputs

if __name__ == '__main__':
    find_hash()
于 2011-08-08T00:16:35.260 に答える
3

いくつかの準分析的なとりとめのないもの：

あなたの数のセットでは、全部で11、3は奇数、8は偶数です。最も単純な形式のハッシュ（％13）を見ると、次のハッシュ値が得られます：10-3、100-9、32-6、45-6、58-6、126-9、3-3、29-3 、200-5、400-10、0-0

もちろん、これは衝突の数のために使用できません。もっと手の込んだものが必要です。

なぜ明白なことを述べるのですか？数が非常に少ないことを考えると、複雑な（つまり「単純ではない」）アルゴリズムは、switchステートメントまたは（私が好む）サイズ11の位置の符号なしの短い/長いベクトルを検索して、一致のインデックス。

なぜベクトル検索を使用するのですか？

  1. 最も頻繁に発生する値をベクトルの先頭に配置することで、微調整できます。
  2. 目的は、ハッシュインデックスをスイッチに接続して、連続した番号を付けることだと思います。その観点から、最初にスイッチを使用してインデックスを見つけ、次にそれを別のスイッチに接続するのは無駄に思えます。たぶん、ハッシュをまったく使用しないことを検討し、最後のスイッチに直接進む必要がありますか？
  3. ハッシュのスイッチバージョンは微調整できず、値が大きく異なるため、コンパイラがバイナリ検索ツリーを生成し、多くの比較と条件付き/その他のジャンプ（特にコストがかかる）が発生し、時間がかかります（私はあなたがその速度のためにハッシュに目を向けたと仮定しました）そしてスペースを必要とします。
  4. ベクトル検索をさらに高速化し、x86システムを使用している場合は、アセンブラー命令repne scasw（短い）/ repne scasd（長い）に基づいてベクトル検索を実装できます。これははるかに高速です。いくつかの命令のセットアップ時間の後、1つの命令の最初のエントリと11の最後のエントリが見つかり、その後にいくつかの命令のクリーンアップが続きます。これは、5〜10命令が最良の場合、15〜20命令が最悪であることを意味します。これは、おそらく1つか2つの場合を除いて、スイッチベースのハッシュを打ち負かすはずです。
于 2010-11-09T09:28:07.503 に答える
2

ボブ・ジェンキンスにもこのためのプログラムがあります：http: //burtleburtle.net/bob/hash/perfect.html

運が良ければ、特定のデータセットに「優れた」完璧なハッシュ関数はありません。完全なハッシュアルゴリズムは通常、キーに対して単純なハッシュ関数を使用し（十分なビットを使用して衝突がないようにします）、テーブルを使用してそれを終了します。

于 2010-11-09T06:17:57.373 に答える
0

簡単なチェックをしてSHA256ハッシュ関数を使ってから、Mathematicaで試してみたところ、13によるモジュラー除算がうまくいきました。C ++の場合、この関数はopensslライブラリにある必要があります。この投稿を参照してください。

ただし、多くのハッシュとルックアップを実行している場合、モジュラー除算は繰り返し実行するにはかなりコストのかかる操作です。nビットのハッシュ関数をiビットのインデックスにマッピングする別の方法があります。Cでビットシフト操作を使用してそれを行う方法については、MichaelMitzenmacherによるこの投稿を参照してください。お役に立てば幸いです。

于 2010-11-09T06:17:52.740 に答える
0

n値を0から12までの一意のインデックスにマップする次のことを試してください（1369％（n + 1））％13

于 2013-09-21T19:43:58.947 に答える