php中的数组冲突

Question

小备注

阅读有关max_input_vars变量的信息使我阅读了很多有关 PHP 处理数组的内部结构的信息。这不是一个真正的问题，而是回答我自己的问题“为什么我们真的需要这个 max_input_var”。它没有本地化，实际上与许多其他编程语言有关，而不仅仅是 php。

一个问题：

比较这两个小的 php 脚本：

$data = array();
for ($key = 0; $key <= 1073709056; $key += 32767){
    $data[$key] = 0;
}

可以在这里检查。一切正常，没有意外。执行时间接近于0。

这几乎是相同的（不同之处在于 1）

$data = array();
for ($key = 0; $key <= 1073709056; $key += 32768){
    $data[$key] = 0;
}

在这里检查。没有什么是正常的，一切都是出乎意料的。你超过了执行时间。所以它至少慢了 3000 倍！

问题是为什么会发生？

我把它和一个答案一起贴在这里，因为这极大地提高了我对 php 内部结构的了解，并且我学到了关于安全的新知识。

Answer 1

问题不在循环中，问题在于 PHP 和许多其他语言（Java、Python、ASP.Net）如何在哈希数据结构中存储键/值对。PHP 使用哈希表来存储数组（这使得它们在理论上非常快速地从该数组存储和检索数据O(1)）。当多个值映射到同一个键从而产生哈希冲突时，就会出现问题。将元素插入这样的键变得更加昂贵O(n)，因此插入 n 个键从 O(n) 跳转到 O(n^2)。

这正是这里发生的事情。当数字从32767变为 时，32768它会将键从无碰撞更改为所有碰撞到同一个键。

这是这种情况，因为它在 C 中实现 php 数组的方式。数组的大小是 2 的幂。（数组9和15元素将使用大小数组分配16）。此外，如果数组键是整数，则散列将是一个整数，上面有一个掩码。掩码是size of the array - 1二进制的。这意味着如果有人尝试在关联数组中插入以下键0, 32, 64, 128, 256, ...，依此类推，它们都将映射到相同的键，因此哈希将具有链表。上面的例子正是创建了这个。

这需要大量 CPU 来处理，因此您会看到大量的时间增加。这意味着开发人员在接受来自外部的一些数据并将其解析为数组时应该非常小心（人们可以轻松制作数据并对服务器进行 DOS 处理）。此数据可以是$_GET、$_POST请求（这就是您可以使用 限制数量的原因max_input_vars）、XML、JSON。

以下是我用来了解这些事情的资源：

• 资源 1
• 资源 2
• 资源 3
• 资源 4
• 资源 5