PHP中如何实现关联数组？

Question

有人能解释一下PHP如何实现关联数组吗？PHP使用什么底层数据结构？PHP会对键进行哈希处理并存储在某种哈希映射中吗？我很好奇，因为我想知道插入和搜索键时关联数组的性能如何。

- Y Pgjn

---

我会留下这个链接让其他人去研究，但你可以在http://svn.php.net/viewvc/php/php-src/查看PHP的实际C源代码。 - Kyle Hale

Answer 1

最高得票的答案链接已经损坏，没有提供太多解释。

PHP是用C语言编写的，底层结构只是一个C数组。C数组只是内存块。C数组中的索引必须连续，不能有一个索引为0，而另一个索引为1000。为了使关联数组键可以工作，在它们添加到C数组之前，它们通过哈希函数转换为适当的C索引。

如果你想要全面的解释，我发现这个链接更加详细。 http://nikic.github.io/2012/03/28/Understanding-PHPs-internal-array-implementation.html

- PressingOnAlways

---

底层C数组的大小是多少？如果数组随着时间增长而增加，键是否会重新哈希，例如在Java的HashMap中？谢谢！ - tonix

@tonix 你可以自己查看源代码 - https://github.com/php/php-src/blob/master/Zend/zend_hash.c。在php5中，它只使用`HashTable`数据类型，但现在一切都是Zen引擎，所以它们使用zend_hash，它仍然使用哈希表。你可以在这里阅读更多信息：https://www.phpinternalsbook.com/php5/hashtables.html - PressingOnAlways

@tonix 简而言之，是的。与大多数哈希表一样，如果插入的元素将容器的负载因子增加到实现定义的阈值之上，表格将为更大的数组分配内存并重新散列键。 - Cy Rossignol

@CyRossignol 感谢您的回复！重新哈希所有密钥听起来像是一个昂贵的 O(n) 操作。 - tonix

@tonix 你说得对，这是一个相对昂贵的操作。大多数通用哈希表通过分配比一个插入所需更大的数组来摊销这个成本，以便后续的插入不会产生额外开销。从算法分析的角度来看，插入的成本接近于O(1)。 - Cy Rossignol

@CyRossignol 感谢您的回复！在 Stack Overflow 和其他地方阅读到的信息的基础上，我自己实现了一个 PHP 中的链接哈希映射：https://github.com/tonix-tuft/linked-hash-map。在我的情况下，我从不重新散列键，但我使用多维数组来识别给定键的桶，而且该数组的每个维度都具有不同的质数长度，以最小化碰撞。这种实现允许使用任何 PHP 数据类型作为键（而内置的 PHP 数组仅允许 int 和 string）。希望有人能从这个数据结构中受益。 - tonix

Answer 2

这是一个哈希表。类型声明和哈希函数在这里：
http://svn.php.net/viewvc/php/php-src/trunk/Zend/zend_hash.h?view=markup 在spl（标准php库）中有一个轻量级数组和一个链表。

- chuck

---

源代码已经迁移到 GitHub：https://github.com/php/php-src/blob/master/Zend/zend_hash.h - David

Answer 3

其实，不管怎样，所有的PHP数组都是关联数组。

- EBGreen

Answer 4

@EBGreen是正确的。

这会给你带来一些有趣的性能问题，特别是当将数组视为列表并使用[]（数组添加）运算符时。PHP似乎没有缓存最大的数字键并加1，而是似乎遍历所有键以找到下一个数字键应该是什么。我已经因为PHP糟糕的数组作为列表性能而重写了Python脚本。

关联数组具有标准的字典/哈希性能开销。

- jcoby

---

你确定这个吗？我刚在一个包含 1000 个元素的测试数组上运行了基准测试（一个一个地复制到新数组），如果你不为新数组指定键，它会比较稳定地快 7%（在 PHP 5.2.6 上）。 - JamShady

可能他们最近已经改变了它。我在做这项工作时使用的是5.1版本。当你处理10k条或更多的条目时，PHP的数组非常糟糕。 - jcoby

据我所知，这不是这种情况，请比较：一个Zend哈希表有一个元素nNextFreeElement... - hakre

@RickyMason。通常情况下你可能不会这样做，但为了进行彻底的测试，计算10、100、1k和10k每个项目的时间将真正突出可扩展性性能问题，特别是如果有可能需要处理10k。 - Patanjali

Answer 5

据各个网络论坛的消息，所有都是哈希表实现的，具体可以参考以下链接：http://www.usenet-forums.com/php-language/15348-zend-engine-array-implementation.html。如果您想确保，可以查看源代码并编译，但请确保您可以信任您的编译器（警告：PDF格式，与此无关，但非常酷）。

- jakber