1

長整数 (DWORD) を生成する、文字列の一意のハッシュ (最大長 = 255) にできるだけ近いハッシュ アルゴリズムを探しています。

26^255 >> 2^32 であることは理解していますが、英語の単語数は 2^32 よりはるかに少ないことも知っています。

「ハッシュ」する必要がある文字列は、ほとんどが 1 つの単語か、2 つか 3 つの単語を使用した単純な構造です。

答え：

FNV バリアントの 1 つが要件を満たす必要があります。それらは高速で、かなり均等に分散された出力を生成します。(クモ類の回答)

4

5 に答える 5

2

この質問（および回答）の以前の繰り返しについては、こちらを参照してください。

于 2008-09-24T10:26:38.783 に答える
1

1 つの手法は、よく知られたハッシュ アルゴリズム (たとえば、MD5 または SHA-1) を使用し、結果の最初の 32 ビットのみを使用することです。

ハッシュ衝突のリスクは、予想よりも速く増加することに注意してください。これについては、誕生日のパラドックスについてお読みください。

于 2008-09-24T10:27:39.967 に答える
1

Ronny Pfannschmidt は昨日、一般的な英語の単語でテストを行いましたが、Python 文字列ハッシュ関数でテストした 10000 単語の衝突は発生していません。自分でテストしたことはありませんが、そのアルゴリズムは非常にシンプルで高速で、一般的な単語に最適化されているようです。

ここで実装：

static long
string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;

    if (a->ob_shash != -1)
        return a->ob_shash;
    len = Py_SIZE(a);
    p = (unsigned char *) a->ob_sval;
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);
    if (x == -1)
        x = -2;
    a->ob_shash = x;
    return x;
}
于 2008-09-24T10:28:26.267 に答える
0

H(キー) = [GetHash(キー) + 1 + (((GetHash(キー) >> 5) + 1) % (ハッシュサイズ – 1))] % ハッシュサイズ

ハッシュコードに関する MSDN の記事

于 2008-09-24T10:32:34.790 に答える
0

Java の String.hash() はここで簡単に表示できます。そのアルゴリズムは次のとおりです。

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
于 2008-09-24T10:33:20.420 に答える