PHP_PHP チュートリアルのハッシュ アルゴリズム

ハッシュ テーブルは PHP の中核です。これは決して誇張ではありません。
PHP の配列、連想配列、オブジェクト プロパティ、関数テーブル、シンボル テーブルなどはすべて HashTable をコンテナとして使用します。
言うまでもなく、PHP の HashTable は競合を解決するためにジッパー メソッドを使用します。今日の私の主な焦点は、PHP のハッシュ アルゴリズムと、アルゴリズム自体によって明らかにされるいくつかのアイデアです。 PHP のハッシュは、最も一般的な DJBX33A (Daniel J. Bernstein、Times 33 with Addition) を使用します。このアルゴリズムは、Apache、Perl、Berkeley DB などの複数のソフトウェア プロジェクトで広く使用されており、現在知られている最良のハッシュ アルゴリズムです。なぜなら、それは非常に高速で、非常によく分類されるからです (衝突が少なく、均等に分散されます
)。 アルゴリズムの核となる考え方は次のとおりです:
1. ハッシュ(i) = ハッシュ(i-1) * 33 + str[i]

zend_hash.h には、PHP のこのアルゴリズムがあります:
1. 静的インライン ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
2. {
3. ulong ハッシュ = 5381;
を登録します 4.
5. /* ハッシュを 8 回展開したバリアント */
6. for (; nKeyLength >= 8; nKeyLength -= {
7. ハッシュ = ((ハッシュ 8. ハッシュ = ((ハッシュ 9. ハッシュ = ((ハッシュ 10. ハッシュ = ((ハッシュ 11. ハッシュ = ((ハッシュ 12. ハッシュ = ((ハッシュ 13. ハッシュ = ((ハッシュ 14. ハッシュ = ((ハッシュ 15. }
16. スイッチ (nKeyLength) {
17. ケース 7: ハッシュ = ((ハッシュ 18. ケース 6: ハッシュ = ((ハッシュ 19. ケース 5: ハッシュ = ((ハッシュ ; 20. ケース 4: hash = ((hash ; 21. ケース 3: hash = ((hash ; 22. ケース 2: hash = ((hash ; 23. ケース 1: ハッシュ = ((ハッシュ 25. EMPTY_SWITCH_DEFAULT_CASE()
26. }
27. ハッシュを返す;
28. } Apache と Perl で直接採用されている古典的な Times 33 アルゴリズムとの比較:
1. Perl 5.005で使用されるハッシュ関数:
2. # 文字列のハッシュ値を返します: $hash = perlhash("key")
3. # (hv.h の PERL_HASH マクロによって定義)
4. サブパールハッシュ
5. {
6. $hash = 0;
7. foreach (分割 //、シフト) {
8. $hash = $hash*33 + ord($_);
9. }
10. return $hash;
11. } PHP のハッシュ アルゴリズムでは、非常に微妙な違いが見られます。
まず第一に、最も異なる点は、PHP は 33 による直接乗算を使用せず、次のものを使用することです。 1. ハッシュ もちろん、車に乗るよりも早くなります
次に、考慮すべき最も重要なことは、Discuz のキャッシュ メカニズムに関する記事を数日前に読みました。その記事の 1 つは、Discuz は投稿の人気に応じて異なるキャッシュ戦略を採用すると述べています。 、投稿の最初のページのみをキャッシュします (投稿を読む人がほとんどいないため)。
この考え方と同様に、PHP では 8 桁未満の文字インデックスを使用して、効率を向上させています。 さらにインライン変数やレジスタ変数もあり…PHP開発者がハッシュ最適化にも熱心に取り組んでいることがわかります
最後に、ハッシュの初期値は 5381 に設定されます。Apache のタイムズ アルゴリズムと Perl のハッシュ アルゴリズム (どちらも初期ハッシュが 0 を使用します) と比較して、なぜ 5381 を選択するのか、具体的な理由はわかりません。 5381 のいくつかの機能を発見しました:
1. 魔法定数 5381:
2. 1. 奇数
3. 2. 素数
4. 3. 不足数
5. 4. 001/010/100/000/101
これを読んだ後、この初期値を選択するとより適切な分類ができると信じる理由ができました。
なぜ Times 33 が Times の他の数字ではなく Times 33 なのかについては、PHP ハッシュ アルゴリズムのコメントにいくつかの説明があります。興味のある学生にとって役立つと幸いです。 1. DJBX33A (ダニエル・J・バーンスタイン、タイムズ33、追加)
2.
3. これは、ダニエル J. バーンスタインの人気のある「33 倍」ハッシュ関数です
4. 数年前に彼が comp.lang.c に投稿したもので、基本的には関数を使用します
5. 「hash(i) = hash(i-1) * 33 + str[i]」のように、これは最高の 1 つです
。 6. 文字列の既知のハッシュ関数は両方とも非常に計算されるためです
。 7. 高速で非常によく配布されます。
8.
9. 33 という数字の魔法、つまり、なぜ他の数字よりもうまく機能するのか
10. 定数は、素数であろうとなかろうと、
によって適切に説明されたことはありません。 11. 誰でもいいので、実験的にすべてをテストした場合の説明を試みます
12. 1 から 256 までの乗数 (RSE が今行ったように) は偶数であることを検出します
13. 残りの128個の奇数は全く使えません
14. (1 番を除いて) 彼らは多かれ少なかれ全員同じようにうまく働きます
。 15. すべて許容可能な方法で配布し、この方法でハッシュ テーブルを埋めます
16. 平均パーセントは約 86% です。 17.
18. バリアントの Chi^2 値を比較すると、数値 33 は一致しません
19. 最高の値もありますが、33 とその他の数も同等です
20. 17、31、63、127、129 などの良い数字には、素晴らしい効果があります
21. 可能性のある大きなセットの残りの数字に有利
22. 乗算器: 乗算演算はより高速な乗算演算に置き換えることができます
23. 1 つのシフトと 1 つの追加のいずれかをベースにした運用
24. または減算演算。ハッシュ関数は両方を行う必要があるためです
25. 優れた配布は、_そして_ 計算が非常に高速でなければなりません、それらの少数の
26. 数字は優先されるべきであり、それがダニエル J.
の理由のようです 27. バーンスタインもそれを好んでいました
28.
29. www.2cto.com -- ラルフ S. エンゲルシャル

• 著者: ラルーエンス
• この記事のアドレス: http://www.laruence.com/2009/07/23/994.html


http://www.bkjia.com/PHPjc/478471.html

www.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/478471.html技術記事ハッシュ テーブルは PHP の核です。これは決して誇張ではありません。PHP の配列、連想配列、オブジェクト プロパティ、関数テーブル、シンボル テーブルなどはすべて、ジッパーを使用します。