3

私の計算が正しければ、各文字列の個別のハッシュ値が既にある場合は、2 つの文字列を連結するための新しいハッシュ値をすばやく生成できます。ただし、ハッシュ関数が次の形式の場合のみ:

hash(n) = k * hash(n-1) + c(n), and h(0) = 0.

この場合、

hash( concat(s1,s2) ) = k**length(s2) * hash(s1) + hash(s2)

例えば。

h1  = makeHash32_SDBM( "abcdef",          6 );
h2  = makeHash32_SDBM( "ghijklmn",        8 );
h12 = makeHash32_SDBM( "abcdefghijklmn", 14 );
hx  = mod32_powI( 65599, 8 ) * h1 + h2;

h1  = 2534611139
h2  = 2107082500
h12 = 1695963591
hx  = 1695963591

Note that h12 = hx so this demonstrates the idea.

では、SDBM hash k=65599. 一方、DJB hashhas k=33(またはおそらく31?) をh(0) = 5381機能させるために、h(0) = 0代わりに設定することができます。

ただし、各キャラクターを追加するのではなく、DJB hash用途を変更します。xor+

http://www.cse.yorku.ca/~oz/hash.html

xorハッシュ関数が代わりに使用する場合、連結された文字列のハッシュ値をすばやく計算する別の手法はあり+ますか?

4

1 に答える 1

0

2番目のハッシュがハッシュの初期状態の関数になる場合、それは当てはまります。一部の種類のハッシュ関数では、新しい初期状態 (xor'e 単語やその合計など) に従って簡単にシフトできます。しかし、一般的には、それはほとんど不可能です (それ以外の場合、パスワード マッチングで hash+"salt" を使用すると簡単に破ることができます)。

ただし、通常、最初の文字列のハッシュの結果を使用して、2 番目の文字列からデータをフィードし続けることができます。

更新:
次のものを見つける方法はないと思いますf(x,y):

h_abc = hashOf(h0, "abc")  
h_def = hashOf(h0, "def")  
(h_abcdef = f(h_abc, h_def)) == hashOf(h0, "abcdef")

ただし、次のことができます。 

h_abc = hashOf(h1, "abc")  
(h_abcdef = hashOf(h_abc, "def")) == hashOf(h0, "abcdef")

それができない理由の 1 つは、"33" が "2" の累乗ではないことです。"32" (2**5) を使用する場合: 

h_abcdef == (h_abc << (5*len(abc))) xor h_def
于 2010-04-04T10:53:15.603 に答える