58

DJBハッシュ関数で5381という番号が使用されている理由を誰かに教えてもらえますか？

DJBハッシュ関数は次のように定義されます。

  • h 0 = 5381

  • h i = 33h i-1 + s i

Cの実装は次のとおりです。

unsigned int DJBHash(char* str, unsigned int len)
{
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {   
      hash = ((hash << 5) + hash) + (*str);
   }   

   return hash;
}
4

3 に答える 3

77

DJBが何をしているのかを明らかにするコメントに出くわしました。

/*
* DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
*
* This is Daniel J. Bernstein's popular `times 33' hash function as
* posted by him years ago on comp.lang.c. It basically uses a function
* like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
* known hash functions for strings. Because it is both computed very
* fast and distributes very well.
*
* The magic of number 33, i.e. why it works better than many other
* constants, prime or not, has never been adequately explained by
* anyone. So I try an explanation: if one experimentally tests all
* multipliers between 1 and 256 (as RSE did now) one detects that even
* numbers are not useable at all. The remaining 128 odd numbers
* (except for the number 1) work more or less all equally well. They
* all distribute in an acceptable way and this way fill a hash table
* with an average percent of approx. 86%.
*
* If one compares the Chi^2 values of the variants, the number 33 not
* even has the best value. But the number 33 and a few other equally
* good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
* advantage to the remaining numbers in the large set of possible
* multipliers: their multiply operation can be replaced by a faster
* operation based on just one shift plus either a single addition
* or subtraction operation. And because a hash function has to both
* distribute good _and_ has to be very fast to compute, those few
* numbers should be preferred and seems to be the reason why Daniel J.
* Bernstein also preferred it.
*
*
* -- Ralf S. Engelschall <rse@engelschall.com>
*/

これは、5381のマジックナンバーを使用しますが、現在見ているものとは少し異なるハッシュ関数です。リンクターゲットでのそのコメントの下のコードが展開されました。

それから私はこれを見つけました：

Magic Constant 5381:

  1. odd number

  2. prime number

  3. deficient number

  4. 001/010/100/000/101 b

djb2ハッシュ関数の背後にあるロジックを誰かが説明できますか？に対するこの答えもあります。 これは、DJB自身による5381に言及しているメーリングリストへの投稿を参照しています（ここから抜粋した回答からの抜粋）。

[...]実質的にどんな良い乗数でも機能します。cとdが0から255の間の場合、31c + dが妥当な範囲のハッシュ値をカバーしないという事実を心配していると思います。そのため、33ハッシュ関数を発見し、コンプレッサーで使用し始めました。 、私は5381のハッシュ値から始めました。これは261の乗数と同じように機能することがわかると思います。

于 2012-12-10T21:08:49.253 に答える
36

5381は、テストで衝突が少なくなり、なだれが改善された数値です。ほぼすべてのハッシュアルゴに「魔法の定数」があります。

于 2012-05-22T07:22:33.217 に答える
31

この数の非常に興味深い特性がその理由である可能性があることがわかりました。

5381は709番目の素数です。
709は127番目の素数です。
127は31番目の素数です。
31は11番目の素数です。
11は5番目の素数です。
5は3番目の素数です。
3は2番目の素数です。
2は1番目の素数です。

5381は、これが8回発生する最初の番号です。5381stプライムはsignedintの制限を超える可能性があるため、チェーンを停止することをお勧めします。

于 2017-01-25T11:07:13.153 に答える