PHP 7中新的Hashtable实现和性能改进

本文主要是介绍PHP 7中新的Hashtable实现和性能改进，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PHP 7中新的Hashtable实现和性能改进

这篇文章是翻译自nikic的最新大作，我从他的blog中学到了很多东西。这篇文章貌似是他半年多来发的第一篇文章，文章主要是讲PHP 7中的新的Hashtable的实现，Hashtable是PHP中非常核心的部分，数组就是基于此实现的，而数组在PHP中的使用是如此之频繁，所以一个好的Hashtable的实现必然会带来性能的极大提升，从文章来看，事实也确实如此。

大概三年前，我写一篇名为“分析数组的内存使用量”（这篇文章也得相当不错，值得一读）的文章，那篇文章分析的是PHP 5中的数组使用内存的情况。作为我所参与的PHP 7的开发工作中的一部分，我专注于改进了一些小的数据结构的内存分配情况，为此重写了Zend Engine的大部分代码。在这篇文章中，我会大概说明一下新的hashtable的实现，以及为什么它会比之前的实现更高效。

我使用下面的代码来测试内存的使用情况：

$startMemory = memory_get_usage();
$array = range(1, 100000);
echo memory_get_usage() - $startMemory, " bytes\n";

这段代码测试了创建一个含有100000个不同整数的数组所消耗的内存空间大小。

下面这个表格是上面的代码分别在PHP 5.6和PHP 7中的执行结果，包括32位和64位系统两种情况：

| 32 bit | 64 bit
----------------------------------------
PHP 5.6 | 7.37 MiB | 13.97 MiB
----------------------------------------
PHP 7.0 | 3.00 MiB | 4.00 MiB

我们可以说32系统中PHP 7中的数组所占的内存比PHP 5.6节省了2.5倍，64位系统则是3.5倍。这是一个相当不错的改进。

Hashtable简介

PHP中数组的本质是顺序字典，它可以表示一个包含键值对的顺序列表，键值对的映射就是使用Hashtable实现的。

Hashtable是非常常见的数据结构，它被设计出来解决计算机只能直接表示以连续的整数作为索引的数组的问题。使用Hashtable，程序员才能使用字符串或者其他的复合类型作为数组的键。

Hashtable的概念实际上非常简单：字符串的键先会被传递给一个hash函数（hashing function，中文也翻译为散列函数，本文统一使用hash函数）,然后这个函数会返回一个整数（我们把它叫做hash值），而这个整数就是“通常”的数组的索引。问题是对于两个不同的字符串，调用hash函数会得到同一个hash值，而现实情况是任意字符串都可以作为键，所以键会有无数个，而数组的大小必须是提前设定好的，因为hash值必须小于数组索引的最大值，所以可以生成的hash值必须是有限的。这样用有限的hash值表示无限的键，必然会导致冲突。我们把两个不同的键的hash值是一样的情况称为冲突，任何Hashtable算法都必须提供某种机制解决这种冲突。

有两种主要的处理冲突的方法。开放定址法，当冲突发生的时候，冲突的元素会被保存到一个不同的索引中；链接法，所有拥有相同的hash值的元素，它们都会被保存到一个链表中。PHP使用的就是第二种方法。

另外通常情况下，Hashtable并非是显式排序的：最终底层数组中保存的元素的顺序是跟hash函数相关的，并且这个顺序一般都是随机的。这个行为显然跟PHP数组的语义不符：PHP的数组的迭代顺序跟数组中元素的插入顺序完全一致。这也意味着，PHP中的Hashtable的实现必须有一种额外的机制记住数组中元素的插入顺序。

老的Hashtable的实现方式

在此我只会大概介绍一下老的hashtable的实现方式，如果你想要更进一步的了解，可以参加PHP内部机制这本书的hashtable这一章。下面这张图高度概括了PHP5中的hanshtable：

“冲突处理（collision resolution）”链表中的元素被称为”buckets”。每一个bucket都是单独分配的。这个图片没有展示的是每个元素实际的值也是保存在这些buckets中的（图片中只展示了键）。值会存放zval结构，这些结构是分开单独分配内存的，它们的大小是16字节（32位）或者24个字节（64位）。

另外一点上面的图片没有展示出来的是，冲突处理链表实际上是一个双向链表（方便元素的删除）。在冲突处理链表的旁边有另外一个双向链表，它用于保存数组中元素的顺序。对于一个包含的键为”a”,”b”,”c”（而且这是它们的插入顺序）的数组，这个链表会是下面这个样子：