php中的變量是以符號(hào)表的方式進(jìn)行存儲(chǔ)的，實(shí)際上也是個(gè)HashTable，哈希表是通過(guò)特定的哈希算法將索引轉(zhuǎn)換成特定的index然后映射到對(duì)應(yīng)的槽中，然后采用拉鏈法，在一個(gè)槽中使用鏈表將數(shù)據(jù)進(jìn)行存儲(chǔ)，鏈表的時(shí)間復(fù)雜度為O(n)。

php中的hashtable的結(jié)構(gòu)定義在Zend/zend_hash.h文件中：

//保存數(shù)據(jù)的單鏈表結(jié)構(gòu)
typedef struct bucket {
   ulong h;                  /* Used for numeric indexing */
   uint nKeyLength;        //key長(zhǎng)度
   void *pData;        //指向bucket中保存的數(shù)據(jù)的指針
   void *pDataPtr;    //指針數(shù)據(jù)
   struct bucket *pListNext;    //指向hashtable桶列中下一個(gè)元素
   struct bucket *pListLast;    //指向hashtable桶列前一個(gè)元素
   struct bucket *pNext;        //指向具有同一個(gè)hash index的桶列的后一個(gè)元素
   struct bucket *pLast;        //指向具有同一個(gè)hash index的桶列的前一個(gè)元素
   const char *arKey;        //必須是最后一個(gè)成員，key的名稱(chēng)
} Bucket;

每個(gè)數(shù)據(jù)元素bucket有一個(gè)鍵名key，它在整個(gè)hashtable中是唯一的，不能重復(fù)；根據(jù)鍵名可以唯一確定hashtable中的數(shù)據(jù)元素
在php的數(shù)組中，鍵的值可以是整型或字符串，在這里也只有這兩種形式：

如果key為字符串的話：字符串arKey作為鍵名，該字符串的長(zhǎng)度為nKeyLength，h字段保存arKey對(duì)應(yīng)的hash值

索引方式： 這時(shí)nKeyLength為0，索引值存儲(chǔ)在h上，也就是數(shù)據(jù)元素的鍵名

bucket是保存在hashtable上的一個(gè)雙向鏈表，其向前和向后的元素分別用pLast和pNext來(lái)表示。新插入的Becket放在該桶的最前面
在Bucket中，實(shí)際上數(shù)據(jù)是保存在pData指針指向的內(nèi)存塊中的，通常這個(gè)內(nèi)存塊是系統(tǒng)額外分配的。但是存在例外，當(dāng)Bucket保存的數(shù)據(jù)是一個(gè)指針的時(shí)候，Hashtable不會(huì)另外請(qǐng)求系統(tǒng)分配空間來(lái)保存這個(gè)指針，而是直接將該指針保存到pDataPtr中，然后再將pData指向本結(jié)構(gòu)成員的地址

hashtable中所有的bucket通過(guò)pListNext，pListLast構(gòu)成了一個(gè)雙向鏈表。最新插入的Bucket放在雙向鏈表的最后面

//hashtable結(jié)構(gòu)體
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表的主要保存的數(shù)據(jù)包括兩部分：哈希表中存儲(chǔ)的數(shù)據(jù)的個(gè)數(shù)；保存數(shù)據(jù)的容器
在HashTable結(jié)構(gòu)中，nTableSize指定了HashTable的大小，同時(shí)也限定了哈希表中能保存的Bucket的數(shù)量，該數(shù)值越大，系統(tǒng)為HashTable分配的內(nèi)存就越多。為了提高計(jì)算效率， 系統(tǒng)自動(dòng)會(huì)將nTableSize調(diào)整到最小一個(gè)不小于nTableSize的2的整數(shù)次方，這個(gè)其實(shí)不太懂
arBuckets是HashTable的關(guān)鍵，HashTable會(huì)自動(dòng)向系統(tǒng)申請(qǐng)一塊內(nèi)存，并將其地址賦值給arBuckets，該內(nèi)存大小正好容納nTableSize指針。我們可以將arBuckets看作一個(gè)大小為nTableSize的數(shù)組，每個(gè)數(shù)組元素都是一個(gè)指針，用于指向存放數(shù)據(jù)的Buckets。在初始化的時(shí)候每個(gè)指針都為null

nTableMask的值永遠(yuǎn)是nTableSize - 1，引入這個(gè)字段的主要目的是為了提高計(jì)算效率，為了快速計(jì)算Buckets鍵名在arBuckets數(shù)組中的索引

nNumberOfElements記錄了HastTable當(dāng)前保存的數(shù)據(jù)元素的個(gè)數(shù)。當(dāng)nNumberOfElements大于nTableSize的時(shí)候，HashTable就自動(dòng)擴(kuò)展為原來(lái)的兩倍大小

nNextFreeElement記錄HashTable中下一個(gè)可用于插入數(shù)據(jù)元素的arBuckets索引

pListHead,pListTail分別表示Buckets雙向鏈表的第一個(gè)和最后一個(gè)元素，這些元素通常是根據(jù)插入的順序排列的。也可以根據(jù)對(duì)應(yīng)的排序函數(shù)對(duì)其進(jìn)行重新排列。pInternalPointer則用于在遍歷HashTable時(shí)記錄當(dāng)前遍歷的位置，它是一個(gè)指針，指向當(dāng)前遍歷到的Bucket，初始值是pListHead

pDestroyctor是一個(gè)函數(shù)指針，在HashTable的增加，修改，刪除Bucket時(shí)自動(dòng)調(diào)用，用于處理相關(guān)數(shù)據(jù)的清理工作

persistent標(biāo)志位指出了Bucket內(nèi)存分配的方式。如果persisient為T(mén)RUE，則使用操作系統(tǒng)本身的內(nèi)存分配函數(shù)為Bucket分配內(nèi)存，否則使用PHP的內(nèi)存分配函數(shù)。具體請(qǐng)參考PHP的內(nèi)存管理。

php中為了使用的哈希算法是DJBX33A

php中是使用單鏈表去存儲(chǔ)碰撞的數(shù)據(jù)的，所以實(shí)際上php在哈希表上的平均查找復(fù)雜度為O(L)，其中L為桶鏈表的平均長(zhǎng)度；而最壞的時(shí)間復(fù)雜度為O(N)，此時(shí)所以存儲(chǔ)到hashtable上的數(shù)據(jù)全部發(fā)生碰撞，哈希表退化成為單鏈表。

哈希表碰撞就是精心設(shè)計(jì)的數(shù)據(jù)使所有的數(shù)據(jù)發(fā)生碰撞。人為的將一個(gè)哈希表退化成為一個(gè)單鏈表，在哈希表上的各種操作的時(shí)間會(huì)提升一個(gè)數(shù)量級(jí)，大量消耗CPU，導(dǎo)致系統(tǒng)無(wú)法快速響應(yīng)請(qǐng)求，從而達(dá)到拒絕服務(wù)(DDOS)的目的

一般情況下很難直接修改php的代碼去制造哈希碰撞攻擊，但是在表單參數(shù)$_POST是一個(gè)Array，內(nèi)部就是通過(guò)Zend HashTable來(lái)實(shí)現(xiàn)的，攻擊者只要構(gòu)造一個(gè)含有大量碰撞的key的post請(qǐng)求，就可以達(dá)到ddos攻擊的目的

以上說(shuō)了通過(guò)http post請(qǐng)求中的表單數(shù)據(jù)進(jìn)行攻擊，防御的方式可以：

在php5.3以上的版本中，post參數(shù)的數(shù)量存在最大的限制max_input_vars => 1000

在web服務(wù)器層面進(jìn)行處理，如通過(guò)限制請(qǐng)求body大小和參數(shù)的數(shù)量等，這個(gè)也是目前使用最多的解決方案

其實(shí)以上的兩種解決方案并不能解決問(wèn)題，因?yàn)橹皇菃渭兊脑趨?shù)的數(shù)量上進(jìn)行限制了，但是入股請(qǐng)求的數(shù)據(jù)中包含json數(shù)據(jù)，但其中的數(shù)據(jù)就是碰撞的array。理論上，只要php代碼某處構(gòu)造array的數(shù)據(jù)依賴(lài)于外部輸入，則都可能造成這個(gè)問(wèn)題，因此徹底的解決方案是更改Zend底層的HashTable實(shí)現(xiàn)

限制每個(gè)桶鏈表的最長(zhǎng)長(zhǎng)度

使用其他數(shù)據(jù)結(jié)構(gòu)如紅黑樹(shù)取代鏈表組織碰撞哈希（并不解決哈希碰撞，只是減輕攻擊影響，將N個(gè)數(shù)據(jù)的操作時(shí)間從O(N^2)降至O(NlogN)，代價(jià)是普通情況下接近O(1)的操作均變?yōu)镺(logN)）

參考：

php內(nèi)核探索：http://www.nowamagic.net/libr...