php - php中的数组冲突

Question

小提示

正在阅读 max_input_vars变量让我阅读了很多关于 PHP 内部处理数组的内容。这不是真正的问题，而是answering my own question “为什么我们真的需要这个 max_input_var”。它没有本地化，实际上与许多其他编程语言相关，而不仅仅是 php。

一个问题:

比较这两个小的 php 脚本:

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

可以查看it here .一切正常，没有什么意外。执行时间接近于0。

这几乎是相同的(不同之处在于 1)

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

检查 it here .没有什么是正常的，一切都是出乎意料的。您超出了执行时间。所以它至少要慢 3000 倍!

问题是为什么会这样？

我将其与答案一起发布在这里，因为这极大地提高了我对 php 内部结构的了解，并且我学到了有关安全性的新知识。

Answer 1

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

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

之所以如此，是因为 php 数组在 C 中的实现方式。数组的大小是 2 的幂。(9 和 15 的数组> 元素将分配大小为 16 的数组)。此外，如果数组键是一个整数，则散列将是一个在其顶部带有掩码的整数。掩码是 数组的大小 - 1(二进制)。这意味着如果有人试图将以下键插入关联数组 0, 32, 64, 128, 256, ... 等等，它们都将映射到相同的键并且因此哈希将有一个链表。上面的示例正是这样创建的。

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

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

• res 1
• res 2
• res 3
• res 4
• res 5