14

int のベクトルを入力し、内積と同様に機能する単一の int を出力する既知のハッシュ アルゴリズムはありますか?

つまり、C++ で次のようなハッシュ アルゴリズムを考えています。

// For simplicity, I'm not worrying about overflow, and assuming |v| < 7.
int HashVector(const vector<int>& v) {
  const int N = kSomethingBig;
  const int w[] = {234, 739, 934, 23, 828, 194};  // Carefully chosen constants.
  int result = 0;
  for (int i = 0; i < v.size(); ++i) result = (result + w[i] * v[i]) % N;
  return result;
}

私がこれに興味を持っているのは、同様のハッシュに関する以前の研究から恩恵を受けるアルゴリズムに関する論文を書いているからです。特に、このようなハッシュ アルゴリズムの衝突特性について何か知られていることがあれば、それは素晴らしいことです。

私が興味を持っているアルゴリズムは整数ベクトルをハッシュしますが、浮動小数点ベクトルの何かもクールです。

明確化

ハッシュは、高速なキー/値検索用のハッシュ テーブルで使用することを目的としています。ここにはセキュリティ上の懸念はありません。

望ましい答えは、このようなハッシュに対して特にうまく機能することが証明されている一連の定数のようなものです。疑似乱数ジェネレーターとして他のものよりもうまく機能する乗数とモジュロに似ています。

たとえば、線形合同疑似乱数発生器の定数のいくつかの選択は、最適なサイクル長を与え、計算しやすいモジュロを持つことが知られています。おそらく誰かが研究を行って、ベクトルハッシュ内の特定の乗法定数のセットとモジュロ定数が、近くの整数ベクトル間の衝突の可能性を減らすことができることを示しています。

4

4 に答える 4

3

さまざまな文字列ハッシュ アルゴリズムをテストして、いくつかの (未公開の実用的な) 実験を行いました。(文字列に対する Java のデフォルトのハッシュ関数は最悪であることが判明しました。)

簡単な実験は、英語の辞書をハッシュして、アルゴリズム A とアルゴリズム B で発生した衝突の数を比較することです。

同様の実験を構築できます: 長さ 7 以下の可能性のあるベクトルの $BIG_NUMBER をランダムに生成します。それらをアルゴリズム A でハッシュし、アルゴリズム B でハッシュしてから、衝突の数と重大度を比較します。

それができるようになったら、シミュレートされたアニーリングまたは同様の手法を使用して、適切に機能する「マジック ナンバー」を見つけることができます。私の研究では、特定の対象語彙と厳密に制限されたハッシュ サイズに対して、「マジック ナンバー」を変化させることで、一般的なアルゴリズムをいくつかの人間の言語でうまく機能させることができました。

于 2008-11-12T08:42:23.113 に答える
2

定数のサイズによっては、入力ベクトルの混乱の程度が結果に影響を与えると言わざるを得ません。ただし、投稿の簡単な定性分析は、良いスタートを切ったことを示唆しています。

  • 入力が乗算されるため、反復ごとの同様の入力値間の分離度が高くなります (たとえば、65 + 66 は 65 * 66 よりもはるかに小さい)。これは良いことです。
  • ベクトルをシーケンスではなくセットと見なす必要がない限り、これは決定論的です。わかりやすくするために、v = { 23, 30, 37 } は v = { 30, 23, 37 } とは異なるべきですか?
  • 分布の均一性は、v の入力値の範囲とカオスに基づいて変化します。ただし、これは一般化された整数ハッシュ アルゴリズムにも当てはまります。

好奇心から、既存のハッシュ アルゴリズムを整数に使用し、その結果に対して興味深い計算を実行してみませんか?

于 2008-11-12T07:28:43.730 に答える
1

この方法でタプルをハッシュするために使用される Python ( source ):

class tuple:
    def __hash__(self):
        value = 0x345678
        for item in self:
            value = c_mul(1000003, value) ^ hash(item)
        value = value ^ len(self)
        if value == -1:
            value = -2
        return value

あなたの場合、item常にこのアルゴリズムを使用する整数になります。

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value == -2
        return value

ただし、これは内積とは何の関係もありません...だから、あまり役に立たないかもしれません。

于 2008-11-12T08:13:50.053 に答える
0

私はあなたを完全に誤解しているかもしれませんが、ベクターをバイトストリームとして扱い、それに対していくつかの既知のハッシュ、つまりSHA1またはMD5を実行することをお勧めします。

明確にするために、これらのハッシュは優れたハッシュ特性を持つことが知られているため、自転車を再発明して新しいハッシュを実装する理由はないと私は信じています。もう 1 つの可能性は、既知の CRC アンゴリズムを使用することです。

于 2008-11-12T07:34:49.320 に答える