PHP ハッシュ アルゴリズムの概要_PHP チュートリアル

ハッシュテーブルはPHPの中核です。これは決して誇張ではありません。

PHP の配列、連想配列、オブジェクト プロパティ、関数テーブル、シンボル テーブルなどはすべて HashTable をコンテナとして使用します。

PHP の HashTable は競合を解決するためにジッパー メソッドを使用します。今日は主に PHP のハッシュ アルゴリズムと、アルゴリズム自体によって明らかにされるいくつかのアイデアに焦点を当てます。

PHP のハッシュは、最も一般的な DJBX33A (Daniel J. Bernstein、Times 33 with Addition) を使用します。このアルゴリズムは、Apache、Perl、Berkeley DB などの複数のソフトウェア プロジェクトで広く使用されており、現在知られている最良のハッシュ アルゴリズムです。その理由は、アルゴリズムが非常に高速で、分類が非常に優れているためです (衝突が少なく、均等に分散されています)。

アルゴリズムの中心となるアイデアは次のとおりです:

コードをコピーします コードは次のとおりです:

hash(i) = hash(i-1) * 33 + str[i]

zend_hash.h には、PHP の次のアルゴリズムがあります:

コードをコピー コードは次のとおりです:

static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
{
Register ulong hash = 5381;

/* ハッシュを 8 回展開したバリアント * /
for (; nKeyLength >= 8; nKeyLength -= {
hash = ((hash <
hash = ((hash < hash = ((hash < ; ハッシュ = ((ハッシュ ハッシュ = ((ハッシュ ハッシュ = ((ハッシュ ハッシュ = ((( ハッシュ }
switch (nKeyLength) {
case 7 : ハッシュ = ((ハッシュ << 5) + ハッシュ) + *arKey++; /* フォールスルー... */
ケース 6: ハッシュ = ((ハッシュ << 5) + ハッシュ) + *arKey++; * フォールスルー... */
ケース 5: ハッシュ = ((ハッシュ << 5) + ハッシュ) + *arKey++ /* フォールスルー... */
ケース 4: ハッシュ = ((ハッシュ << 5) + ハッシュ) + *arKey++; /* フォールスルー... */
ケース 3: ハッシュ = ((( ハッシュ < ケース2: ハッシュ = ((ハッシュ << 5) + ハッシュ) + *arKey++; /* フォールスルー... */
ケース 1: ハッシュ = ((ハッシュ << 5) + ハッシュ) + *arKey++;ブレーク;
ケース 0: ブレーク;
Apache および Perl で直接採用されている古典的な Times 33 アルゴリズムとの比較:




コードをコピー

コードは次のとおりです:

Perl 5.005で使用されるハッシュ関数:

# 文字列のハッシュ値を返します: $hash = perlhash("key")

# (PERL_HASHで定義) hv のマクロ .h) sub perlhash { $hash = 0; foreach (分割 //, シフト) {

$hash = $hash*33 + ord($_);

}
return $hash;
}



PHP のハッシュ アルゴリズムでは、非常に微妙な違いが見られます。

まず第一に、最も異なる点は、PHP では 33 による直接乗算が使用されず、次のものが使用されることです。



コードをコピーします

コードは次のとおりです。

もちろん、車に乗るよりも早くなります

次に、考慮すべき最も重要なことは、アンロールドの使用です。数日前に、Discuz のキャッシュ メカニズムに関する記事を読みました。その記事の 1 つは、Discuz は投稿の人気とユーザーの習慣に基づいてさまざまなキャッシュ戦略を採用すると述べていました。投稿の最初のページのみをキャッシュします (投稿を読む人がほとんどいないため)。

この考え方と同様に、PHP では 8 桁未満の文字インデックスを使用して効率を向上させています。

さらに、インライン変数やレジスタ変数もあり…PHP開発者がハッシュ最適化にも熱心に取り組んでいることがわかります

最後に、ハッシュの初期値は 5381 に設定されています。Apache のタイムズ アルゴリズムと Perl のハッシュ アルゴリズム (どちらも初期ハッシュが 0 を使用します) と比較して、なぜ 5381 を選択するのか、具体的な理由はわかりません。 5381 のいくつかの機能を発見しました:

コードをコピーします コードは次のとおりです:

Magic Constant 5381:
1. 奇数
2. 素数
3. これらを読んだ後、私は信じる理由があります。この初期値を選択すると、より適切な分類が可能になります。

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

www.bkjia.com

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