PHP配列のハッシュ競合の例

PHP 配列でのハッシュ競合の例。構築されたキー値を持つ 65536 個の要素を PHP 配列に挿入すると、通常、このプロセスには 0.1 秒しかかかりません。

次の例を参照してください:

$size = pow(2, 16);

$startTime = microtime(true);

$array = array();

for ($key = 0, $maxKey = ($size - 1) * $size; $key

}$endTime = microtime(true);

echo 'Insert ', $size, ' 悪意のある要素は必要です ', $endTime - $startTime, ' 秒', "n"; $startTime = microtime(true);

$array = array();

for ($key = 0, $maxKey = $size - 1;

$key

echo 'Insert ', $size, ' 通常の要素は require ', $endTime - $startTime, ' 秒', "n";

上記の例、私のマシンでの実行結果は次のとおりです:

65536 個の悪意のある要素を挿入するには 43.1438360214 秒かかり、65536 個の通常の要素を挿入するには 0.0210378170013 秒かかります

この違いは誇張されていませんか?!

前回の記事で、特別に構築されたキー値は、PHP がキー値を挿入するたびにハッシュ競合を引き起こし、PHP の配列の基礎となるハッシュ テーブルがリンク リストに縮退することを紹介しました。

ハッシュ衝突

このように、PHP はリンク リストを挿入するたびにそのリストを走査する必要があります。ご想像のとおり、最初の挿入では 0 個の要素を走査する必要があり、2 回目は 1、3 回目は 3、そして 65536 回目は走査する必要があります。 65535. 、合計 65534*65535/2=2147385345 回の走査が必要です…

では、このキー値はどのように構築されるのでしょうか?

PHP では、キー値が数値の場合、ハッシュは数値そのものであり、通常はインデックスとテーブルマスクになります。テーブルマスクは、数値インデックスが配列が保持できる要素の数を超えないようにするために使用されます。 、配列 Number-1.

PHP のハッシュテーブルのサイズは 2 の指数です。たとえば、10 個の要素の配列を保存する場合、配列の実際のサイズは 16 です。20 個の要素を保存する場合、実際のサイズは 32 です。63 個の要素を保存する場合、実際のサイズは 64 です。保存する要素の数が配列内の現在の最大要素数を超えると、PHP は配列を拡張して再ハッシュします。

ここで、64 個の要素を保存すると仮定します (途中で展開される可能性がありますが、最終的な配列サイズが 64 で、対応する tableMask が 63:0111111 であることだけを知っておく必要があります)。 1 回目はキー値が 0 で、次はハッシュ値が 0 です。2 回目は 64 を保存し、ハッシュ (1000000 & 0111111) の値も 0 です。3 回目は 128 を使用し、4 回目は 192 を使用します。 ... これにより、基礎となる PHP 配列はすべての要素をバケット番号 0 にハッシュし、ハッシュ テーブルをリンク リストに縮退します。

もちろん、キー値が文字列の場合は少し面倒になりますが、PHP のハッシュ アルゴリズムはオープンソースで既知なので、その気になれば誰でも実行できます...

この記事のURL：http://www.laruence.com/2011/12/30/2435.html