php-perl ハッシュ アルゴリズムの実装 (times33 ハッシュ アルゴリズム)_PHP チュートリアル
- WBOYオリジナル
- 2016-07-13 10:42:47988ブラウズ
apr_ssize_t *klen)
{
unsigned int hash = 0;
const unsigned char *key = (const unsigned char *)char_key;
const unsigned char *p;
apr_ssize_t i;
/*
* これは、
* perl で使用され、Berkeley DB にも登場する人気のある `times 33' ハッシュ アルゴリズムです。これは、文字列に対する最良のハッシュ関数の 1 つです
* 非常に高速に計算
* され、非常によく分散されるためです。
*
* 発案者は Dan Bernstein かもしれませんが、Berkeley DB のコードでは Chris Torek が引用されています
*ソース。私が見つけた最高の引用
* は、「Chris Torek、C でのテキストのハッシュ関数、Usenet メッセージ
* <27038@mimsy.umd.edu> in comp.lang.c 、1990 年 10 月」です。 Rich
* INN に関する Salz の USENIX 1992 論文は、
* .
*
* 33 という数字の魔法、つまり、なぜそれが他の多くの
* 定数よりもうまく機能するのか、素数であろうとなかろうと、これまで十分に説明されたことはありません。
* 誰でも。そこで私は説明を試みます。1 から 256 までのすべての
* 乗算器を実験的にテストすると (以前、低レベルの
* データ構造ライブラリを作成したときに行ったように)、偶数の
* 数値はまったく使用できないことが検出されます。残りの 128 個の奇数
* (数字 1 を除く) は、多かれ少なかれすべて同じように機能します。
* これらはすべて許容可能な方法で分散され、この方法でハッシュ
* テーブルを平均約 100 パーセントで埋めます。 86%.
*
* バリアントの chi^2 値を比較すると (
* Bob Jenkins の「ハッシュに関するよくある質問」
* http://burtleburtle.net/bob/hash/hashfaq.html を参照) chi^2) の説明
* では、数値 33 は最適な値ですらない。しかし、
* 数値 33 と、17、31、63、
* 127 および 129 などの他のいくつかの同等の数値は、可能な乗算器の大規模なセットの残りの
* 数値に対して大きな利点を持っています。それらの乗算
* 演算は、 1 つの
* シフトと 1 つの加算または減算演算のいずれかに基づいた、より高速な演算に置き換えることができます。そして
* ハッシュ関数は適切な分散を行う必要があり、かつ_ 計算が非常に高速でなければならないため、これらの少数の数値が優先されるべきです。
* -- Ralf S. Engelschall
*/
if (*クレン = = APR_HASH_KEY_STRING) {
for (p = key; *p; p++) {
hash = hash * 33 + *p;
}
*klen = p - key;
}
else {
for (p = キー、i = *klen; i--, p++) {
ハッシュ = *p;
}
}
リターンハッシュ;
}
関数コメント部分の翻訳: これはよく知られているtimes33ハッシュアルゴリズムです。このアルゴリズムはperl言語で採用されており、Berkeley DBに登場する最もよく知られたハッシュアルゴリズムの1つであり、When aの処理に使用されます。文字列はキー値のハッシュであり、計算効率が非常に高く、ハッシュ分散が優れています。このアルゴリズムを最初に提案したのは Dan Bernstein ですが、ソース コードは Berkeley DB の Clris Torek によって実装されました。正確な引用は、「Chris Torek、Text Hash Functions in C、Usenet News <<27038@mimsy.umd.edu> in comp.lang.c、1990 年 10 月」となります。Rich Salz が 1992 年に発行した INN についての記事で言及されています。この記事は、なぜ 33 という素晴らしい数字が他の数値よりも優れているのでしょうか? 重要かどうかに関係なく、その理由を完全に説明できる人はいません。ここで説明してみましょう。誰かが 1 から 256 までのすべての数値をテストしようとした場合 (私が少し前に書いた低レベルのデータ構造ライブラリのように)、単一の数値のパフォーマンスが特に優れているということはないことがわかりました。 128 個の奇数 (1 を除く) のパフォーマンスは同様で、すべて許容可能なハッシュ分散を達成できます。これらの 128 個の分散値 (テナガザル: 統計用語) を比較すると、平均分散率は約 86% になります。奇数間の確率変数とその数学的期待値の間の平均偏差を示します (Bob Jenkins の <ハッシュに関するよくある質問> http://burtleburtle.net/ bob/hash/hashfaq.html、二乗差の説明を参照) 、数値 33 は最良のものではありません (テナガザル: ここでの私の理解によれば、いつものように、分散は小さいほど安定するはずですが、ここでは明確ではないため、著者の分散の計算式、およびハッシュ分散表では、分散が大きいほど優れているため、ここでの良好なパフォーマンスが大きな分散値を指すのか、小さな分散値を指すのかは不明ですが、数値 33 とその他のいくつかは同じ良い数値です残りの数値に関しては、多数のハッシュ演算に直面する場合に大きな利点があります。つまり、これらの数値は、乗算を加算と減算を組み合わせたビット演算に置き換えることができます。結局のところ、優れたハッシュ アルゴリズムには、優れた分散と高い計算速度の両方が必要です。これらの点を同時に達成できる数値はほとんどありません。
)