数据的基本组织可以分为三种形式:
结构体(或对象)
数组
链表
其他任何的数据组织形式都可以看作是这三种数据组织形式的组合变体。就存取数据的速度而言,数组要远远优于链表，因为数组可以在O(1)的时间复杂内完成指定位置元素的读写操作。所以在理想状态，如果一个数组足够长，且存在一个函数可以将每一个key映射到唯一的一个数组下标，那么我们就可以很完美的解决问题。但往往资源都是有限的，我们没有那么大的空间，也不能设计一个无比负责的映射算法保证每一个key对应到一个唯一的数组下标。
hashtable便是为解决这类问题而存在的,hash操作其本质上就是将一个数据映射成另一个数据，通常情况下原数据的长度比hash后的数据容量大。这种映射的关系我们叫做哈希函数。一般情况下哈希函数的输入可能的总数要远远多于哈希值所能表示的总数，所以就有可能两个不同的输入对应同一个哈希值，比如著名的md5碰撞。
解决冲突的方式主要分两类：
开放定址法(Openaddressing)：这种方法就是在计算一个key的哈希的时候，发现目标地址已经有值了，即发生冲突了，这个时候通过相应的函数在此地址后面的地址去找，直到没有冲突为止。这个方法常用的有线性探测，二次探测，再哈希。
链接法(Separatechaining)：链接法是通过数组和链表组合而成的。当发生冲突的时候只要将其加到对应的链表中即可。
PHP使用链接法解决冲突，如果攻击者能够人为的制造大量hash冲突，将PHP底层保存
POST数据的Hash表退化成链表，造成性能的急剧下降。
PHP的Hash函数
PHP的Hash函数采用的是目前最为普遍的DJBX33A(DanielJ.Bernstein,Times33withAddition)，代码可以在这里查看：http://*******/PHP_5_2/Zend/zend_hash.h#zend_inline_hash_func
-----------------code-------------------------
staticinlineulongzend_inline_hash_func(char*arKey,uintnKeyLength)
255{
256
registerulonghash=5381;
113
257
258
259
260
261
262
263
264
265
266
267
268
269
270
/*variantwiththehashunrolledeighttimes*/
for(;nKeyLength=8;nKeyLength-=8){
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
}
switch(nKeyLength){
case7:hash=((hash5)+hash)+*arKey++;/*fallthrough...
*/
*/
*/
*/
*/
*/
271
272
273
274
275
case6:hash=((hash5)+hash)+*arKey++;/*fallthrough...
case5:hash=((hash5)+hash)+*arKey++;/*fallthrough...
case4:hash=((hash5)+hash)+*arKey++;/*fallthrough...
case3:hash=((hash5)+hash)+*arKey++;/*fallthrough...
case2:hash=((hash5)+hash)+*arKey++;/*fallthrough...
276
277
case1:hash=((hash5)+hash)+*arKey++;break;
case0:break;
278EMPTY_SWITCH_DEFAULT_CASE()
279
}
280
returnhash;
281}
-----------------------------------------------------核心算法是
hash=((hash5)+hash)+*arKey++;
hash5是一个简单的移位操作，可以换算成hash*32，该算法可以理解为hash=hash*33+*arKey++
同时如果提交的key超过7位，需要逐位进行运算。
构造冲突的key
为了方便计算，我们预期构造的两个key均设置为8位。从zend_inline_hash_func函数来分析，进行unrolled操作的时候，如果两个key的前面6位相同，是不影响结果的，只需要考虑碰撞后面两位字母。我们预期构造的两个key如下：
Key1：xa[1]a[2]
Key2：xb[1]b[2]
其中x是一个随机的6位的字符串。
根据算法hash=hash*33+*arKey++，如果需要计算出来的hash相同，我们需要满足如下的条件：
(5381*33+Ascii(a[1]))*33+Ascii(a[2])=(5381*33+Ascii(b[1])*33+Ascii(b[2])展开运算，得到如下结果
Ascii(a[1])*33+Ascii(a[2])=Ascii(b[1])*33+Ascii(b[2])剩下的工作就很简单了，查下Ascii表可以找出来很多组合，一组简单的结果如下：
a[1]=2b[1]=1
a[2]=2b[2]=S
通过以下的demo代码可以进行验证
-----------------code-------------------------
#includestdio.h
#includestdlib.h
#includestring.h
unsignedlongzend_inline_hash_func(char*arKey,intnKeyLength)
{
unsignedlonghash=5381;
for(;nKeyLength=8;nKeyLength-=8){
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
hash=((hash5)+hash)+*arKey++;
}
switch(nKeyLength){
case7:hash=((hash5)+hash)+*arKey++;/*fallthrough...*/
case6:hash=((hash5)+hash)+*arKey++;/*fallthrough...*/
case5:hash=((hash5)+hash)+*arKey++;/*fallthrough...*/
case4:hash=((hash5)+hash)+*arKey++;/*fallthrough...*/
case3:hash=((hash5)+hash)+*arKey++;/*fallthrough...*/
case2:hash=((hash5)+hash)+*arKey++;/*fallthrough...*/
case1:hash=((hash5)+hash)+*arKey++;break;
case0:break;
}
returnhash;
}
intmain()
{
unsignedlonghasha;
unsignedlonghashb;
char*a=abcdef22;
char*b=abcdef1S;
printf(PHPHashtablecollisionsDemo\r\nAuthor:Flyh4t\r\n\r\n);
hasha=zend_inline_hash_func(a,strlen(a)+1);
printf([+]String:%s\r\nPHP5HASHA:%ld\r\n,a,hasha);
hashb=zend_inline_hash_func(b,strlen(b)+1);
printf([+]String:%s\r\nPHP5HASHB:%ld\r\n,b,hashb);
return0;
}
-----------------------------------------------------结算结果如下：
PHPHashtablecollisionsDemo Author:Flyh4t [+]String:abcdef22 PHP5HASHA:1004317790 [+]String:abcdef1S PHP5HASHB:1004317790
达到了预期的效果。