PHP作为一门简单而强大的语言，能够提供很多Web适用的语言特性。从实践出发，继弱类型变量原理探究后，王帅将继续带大家弄清PHP内核中的一些常用部分，本期则是内核利器哈希表与哈希碰撞攻击。

在PHP的Zend Engine（下面简称ZE）中，有一个非常重要的数据结构——哈希表（HashTable）。哈希表在ZE中有非常广泛的应用，PHP的复杂数据结构中数组和类的存储和访问就是用哈希表来组织，PHP语言结构中的常量、变量、函数等符号表也是用它来组织。

1. 哈希表的基本概念

什么是哈希表呢？哈希表在数据结构中也叫散列表。是根据键名经过hash函数计算后，映射到表中的一个位置，来直接访问记录，加快了访问速度。在理想情况下，哈希表的操作时间复杂度为O(1)。数据项可以在一个与哈希表长度无关的时间内，计算出一个值hash(key)，在固定时间内定位到一个桶(bucket，表示哈希表的一个位置)，主要时间消耗在于哈希函数计算和桶的定位。

在分析PHP中HashTable实现原理之前，先介绍一下相关的基本概念：

如下图例子，希望通过人名检索一个数据，键名通过哈希函数，得到指向bucket的指针，最后访问真实的bucket。

键名(Key)：在哈希函数转换前，数据的标识。

桶(Bucket)：在哈希表中，真正保存数据的容器。

哈希函数(Hash Function)：将Key通过哈希函数，得到一个指向bucket的指针。MD5，SHA-1是我们在业务中常用的哈希函数。

哈希冲突(Hash Collision)：两个不同的Key，经过哈希函数，得到同一个bucket的指针。

2. PHP的哈希表实现原理

哈希表的结构：

1)  nTableSize 哈希表的大小。最小容量是2^3(8)，最大容量是2^31(2147483648)。当如果进行一次操作后发现元素个数大于nTableSize，会申请当前nTableSize * 2的空间。假设当前nTableSize为8，当插入元素达到9个的时候，会申请nTableSize=16的空间。

2)  nTableMask 为nTableSize-1，用于调整最大索引值。当哈希后值大于索引值时候，把这个值映射到索引值范围内。

3)  nNumOfElements HashTable中的个数。数组操作中，sizeof和count函数获取的是这个值。

4)  nNextFreeElement 下一个空元素的地址。

5)  pInternalPointer 存储了HashTable当前指向的元素的指针，当我们使用一些内部循环函数的时候会用到这个指针比如reset(), current(), prev(), next(), foreach(), end()。相当于游标。

6)  pListHead和pListTail则具体指向了该哈希表的第一个和最后一个元素，对应就是数组的起始和结束元素。哈希表的pListHead、pListTail与Bucket的pListNext、pListLast维护了一个哈希表中Bucket的双向链表，按照插入的先后顺序，用于哈希表的遍历。

7)  arBuckets 实际存储Buckets的数组。

8)  pDestructor 是一个析构函数，当某个值被从哈希表删除的时候会触发此函数。他还有一个主要作用是用于变量的GC回收。在PHP里面GC是通过引用计数实现的，当一个变量的引用计数变为0，就会被PHP的GC回收。

9)  persistent 定义了hashtable是否能在多次request中获得持久存在。

10)  nApplyCount 和 bApplyProtection 是用来防止嵌套遍历的。

11)  inconsistent 是在调试模式下捕获对HT不正确的使用。

Bucket的结构：

通过下图来表示HashTable的原理：

我们先来看一下，ZE是如何创建一个hash表的。创建并初始化一个Hash比较容易，调用_zend_hash_init函数。PHP的哈希表最小容量8(2^3)，最大容量是0x80000000(2^31，即2147483648)。nTableSize会按照2的整数次幂圆整来增加，直到超过预设值的nSize。

Zend/zend_hash.c

1)  *ht 是哈希表的指针，这里既可以传入一个已存在的HashTable， 也可以通过内核宏ALLOC_HASHTABLE(ht)来自动申请一块HashTable内存。ALLOC_HASHTABLE(ht)相当于ht=emalloc(sizeof(HashTable))

2)  nSize 哈希表能拥有的最大数量。通过预先申请好内存的方式，减少哈希表rehash操作。

3)  pHashFunction 自定义哈希函数的钩子

4)  pDesctructor 哈希表析构的回调函数，当删除一个哈希表的时候，会调用。

5)  persistent 对应HashTable.persistent，当设置为true的时候，不会在RSHUTDOWN阶段自动销毁。

我们通过更新哈希表的操作方式，来分析哈希表的操作机制： 

1) 通过哈希算法  times33(Key) & (nTableSize-1) 

2)  判断arBuckets[A]是否存在，如果存在而且没有哈希冲突，进行数据update(UPDATE_DATA)。如果存在但是Key不相同说明有哈希冲突，在arBuckets[A]链表中寻找Key是否存在，如果存在，执行update操作(UPDATE_DATA)

3)  如果arBuckets[A]不存在，创建新的arBucket[A](INIT_DATA)。或哈希冲突情况下，在arBuckets[A]的链表中找不到Key。创建新的bucket(INIT_DATA)，并把新的buckets放在arBucket[A]链表头

4) 维护哈希表的逻辑链表(CONNECT_TO_GLOBAL_DLLIST)。

5) 如果发现新插入元素已经超过HashTable的nTableSize，自动扩容至2倍nTableSize，重新哈希后维护新的HashTable。

3. PHP使用的哈希函数

PHP的哈希表是用Times33哈希算法，又称为DJBX33A。这是一个使用比较广泛的对字符串的哈希算法，计算速度快，散列均匀，Perl和Apache都使用了这个算法。算法原理就是不断的乘以33，其算法原型如下：

为什么是33呢？对于33这个数，DJB注释中是说，1到256之间的所有奇数，都能达到一个可接受的哈希分布，平均分布大概是86%。而其中33，17，31，63，127，129这几个数在面对大量的哈希运算时有一个更大的优势，就是这些数字能将乘法用位运算配合加减法替换，这样运算速度会更高。gcc编译器开启优化后会自动将乘法转换为位运算。PHP实际算法如下：

PHP在哈希算法上有所优化，使用了(hash<<5)+hash，效率有所提高。至于hash的初始值为什么为一个大素数5381，要数学上来解释了，不是很理解。

4. 操作哈希表的内部函数

PHP的变量符号表是通过哈希表来维护，首先介绍一下再PHP扩展中如何创建一个新的变量。PHP变量介绍，请看我上一篇文章，《深入PHP内核 - 弱类型变量原理探究》。

这里的zend_hash_update会更新变量符号表。PHP的数组也是用哈希表来维护，下面通过操作一个array来解释如何使用哈希表来才做数组。

增加一个关联数组：

增加一个索引数组：

哈希表的增删改查

哈希表的遍历

数组操作函数reset(), each(), current(), next()会用这些函数来实现。

比较，排序 

哈希表有一套排序算法。sort(), asort(), resort(), arsort(), ksort(), krsort()

5. 哈希冲突（Hashtable Collisions）

因为任何一个哈希表的长度都是有限制的，所以一定会发生键名不同，hash函数计算后得到相同的bucket位置。也就是key1 != key2，但是HASH(key1) = HASH(key2)。如下图2，在发生哈希冲突时（Hash Collision），最坏情况下，所有的键名全部冲突，哈希表会退化成双向链表，操作时间复杂度为O(n)。

当发生了哈希冲突，会把当前bucket插入到哈希值所在链表的第一位，并插入HashTable的逻辑链表。

6. 哈希碰撞攻击及解决

在去年发现了PHP的哈希碰撞攻击漏洞，PHP5.3.9以下的版本都会受影响。我们在业务压力很重的情况下，还是最短时间内把运营服务器全部更新到5.3.13以上，防止通过PHP的哈希碰撞进行拒绝服务攻击。

如何哈希碰撞攻击呢？运用哈希冲突。在我们对PHP哈希算法足够了解以后，通过精心构造，可以让PHP的哈希表全部冲突，退化成链表，每插入元素时候，PHP都要遍历一遍链表，消耗大量的CPU，造成拒绝服务攻击。最简单的方法是利用掩码规律制造碰撞，我们知道HashTable的长度nTableSize会被圆整为2的整数次幂，假设我们构造一个长度为2^16的哈希表，nTableSize的二进制表示为：1 0000 0000 0000 0000，而nTableMask = nTableSize – 1为：0 1111 1111 1111 1111。这样我们只要保证后16位均为0，则与掩码与运算后得到的哈希值全部碰撞在位置0。

以下这个例子就是这个原理的实现，插入65535个数据需要消耗30秒，而正常情况下仅需要0.01秒。

结果是

;

对于哈希碰撞攻击有2中常见形式：通过POST攻击或通过反序列化攻击。PHP会自动把HTTP包中POST的数据解析成数组$_POST，如果我们构造一个无限大的哈希冲突的值，可以造成拒绝服务攻击。

PHP5.3.9+是通过增加一个限制来尽量避免被此类攻击影响：

反序列化同样是利用数组的哈希冲突，如果POST的数据有字段为数组serialize后的值，或数组json_encode后的值，在unserialize或json_decode后，会有可能造成哈希碰撞攻击。解决方法，尽量避免在公网上以数组的序列化形式传递数据，如果不可避免，请使用私有协议(TLV)增加供给难度，或使用加密协议(HTTPS)防止中间人攻击。

7. 总结

PHP的哈希表采用times33的哈希算法，通过HashTable数据结构维护Buckets，当有哈希冲突的时候，会将元素插入到该Buckets前形成双向链表。同时为了方便遍历，HashTable也会维护逻辑双向链表（按照插入顺序），通过内部游标指针可以遍历Hashtable。PHP的变量符号表、常量符号表和函数都是用哈希表维护，PHP的数组类型变量也是通过哈希表维护。

哈希表容易遭到哈希碰撞攻击，请更新PHP版本到5.3.9以上，可以解决POST数据的攻击问题；反序列化（把序列化字符串还原为Array）的哈希碰撞攻击，到目前位置PHP官方还没有彻底解决这个问题，请尽量避免用户篡改数据和中间人攻击。