php中的哈希表
php中的变量是以符号表的方式进行存储的，实际上也是个HashTable，哈希表是通过特定的哈希算法将索引转换成特定的index然后映射到对应的槽中，然后采用拉链法，在一个槽中使用链表将数据进行存储，链表的时间复杂度为O(n)。
php中的hashtable的结构定义在Zend/zend_hash.h文件中：
//保存数据的单链表结构typedef struct bucket { ulong h; /* Used for numeric indexing */ uint nKeyLength; //key长度 void *pData; //指向bucket中保存的数据的指针 void *pDataPtr; //指针数据 struct bucket *pListNext; //指向hashtable桶列中下一个元素 struct bucket *pListLast; //指向hashtable桶列前一个元素 struct bucket *pNext; //指向具有同一个hash index的桶列的后一个元素 struct bucket *pLast; //指向具有同一个hash index的桶列的前一个元素 const char *arKey; //必须是最后一个成员，key的名称} Bucket; 每个数据元素bucket有一个键名key，它在整个hashtable中是唯一的，不能重复；根据键名可以唯一确定hashtable中的数据元素
如果key为字符串的话：字符串
arKey作为键名，该字符串的长度为nKeyLength，h字段保存arKey对应的hash值索引方式： 这时
nKeyLength为0，索引值存储在h上，也就是数据元素的键名
bucket是保存在hashtable上的一个双向链表，其向前和向后的元素分别用pLast和pNext来表示。新插入的Becket放在该桶的最前面
Bucket中，实际上数据是保存在pData指针指向的内存块中的，通常这个内存块是系统额外分配的。但是存在例外，当Bucket保存的数据是一个指针的时候，Hashtable不会另外请求系统分配空间来保存这个指针，而是直接将该指针保存到pDataPtr中，然后再将pData指向本结构成员的地址 hashtable中所有的bucket通过pListNext，pListLast构成了一个双向链表。最新插入的Bucket放在双向链表的最后面
//hashtable结构体typedef struct _hashtable { uint nTableSize; uint nTableMask; uint nNumOfElements; ulong nNextFreeElement; Bucket *pInternalPointer; /* Used for element traversal */ Bucket *pListHead; Bucket *pListTail; Bucket **arBuckets; dtor_func_t pDestructor; zend_bool persistent; unsigned char nApplyCount; zend_bool bApplyProtection;#if ZEND_DEBUG int inconsistent;#endif} HashTable; hash表的主要保存的数据包括两部分：哈希表中存储的数据的个数；保存数据的容器
HashTable结构中，nTableSize指定了HashTable的大小，同时也限定了哈希表中能保存的Bucket的数量，该数值越大，系统为HashTable分配的内存就越多。为了提高计算效率， 系统自动会将nTableSize调整到最小一个不小于nTableSize的2的整数次方，这个其实不太懂arBuckets是HashTable的关键，HashTable会自动向系统申请一块内存，并将其地址赋值给arBuckets，该内存大小正好容纳nTableSize指针。我们可以将arBuckets看作一个大小为nTableSize的数组，每个数组元素都是一个指针，用于指向存放数据的Buckets。在初始化的时候每个指针都为null nTableMask的值永远是nTableSize - 1，引入这个字段的主要目的是为了提高计算效率，为了快速计算Buckets键名在arBuckets数组中的索引
nNumberOfElements记录了HastTable当前保存的数据元素的个数。当nNumberOfElements大于nTableSize的时候，HashTable就自动扩展为原来的两倍大小
nNextFreeElement记录HashTable中下一个可用于插入数据元素的arBuckets索引
pListHead,pListTail分别表示Buckets双向链表的第一个和最后一个元素，这些元素通常是根据插入的顺序排列的。也可以根据对应的排序函数对其进行重新排列。pInternalPointer则用于在遍历HashTable时记录当前遍历的位置，它是一个指针，指向当前遍历到的Bucket，初始值是pListHead
pDestroyctor是一个函数指针，在HashTable的增加，修改，删除Bucket时自动调用，用于处理相关数据的清理工作
persistent标志位指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。具体请参考PHP的内存管理。
php中为了使用的哈希算法是DJBX33A
哈希碰撞
php中是使用单链表去存储碰撞的数据的，所以实际上php在哈希表上的平均查找复杂度为O(L)，其中L为桶链表的平均长度；而最坏的时间复杂度为O(N)，此时所以存储到hashtable上的数据全部发生碰撞，哈希表退化成为单链表。
哈希表碰撞就是精心设计的数据使所有的数据发生碰撞。人为的将一个哈希表退化成为一个单链表，在哈希表上的各种操作的时间会提升一个数量级，大量消耗CPU，导致系统无法快速响应请求，从而达到拒绝服务(DDOS)的目的
一般情况下很难直接修改php的代码去制造哈希碰撞攻击，但是在表单参数$_POST是一个Array，内部就是通过Zend HashTable来实现的，攻击者只要构造一个含有大量碰撞的key的post请求，就可以达到ddos攻击的目的
哈希表碰撞的防御
以上说了通过http post请求中的表单数据进行攻击，防御的方式可以：
在php5.3以上的版本中，post参数的数量存在最大的限制
max_input_vars => 1000在web服务器层面进行处理，如
通过限制请求body大小和参数的数量等，这个也是目前使用最多的解决方案-
其实以上的两种解决方案并不能解决问题，因为只是单纯的在参数的数量上进行限制了，但是入股请求的数据中包含json数据，但其中的数据就是碰撞的array。理论上，只要php代码某处构造array的数据依赖于外部输入，则都可能造成这个问题，因此彻底的解决方案是更改Zend底层的
HashTable实现限制每个桶链表的最长长度
使用其他数据结构如红黑树取代链表组织碰撞哈希（并不解决哈希碰撞，只是减轻攻击影响，将N个数据的操作时间从O(N^2)降至O(NlogN)，代价是普通情况下接近O(1)的操作均变为O(logN)）
参考：
php内核探索：