深入PHP-直覺觀察array的擴充

      皆知PHP的數組是由HashTable和雙連結清單實作的，為了友善大家檢視數組的資料結構，開發一個周遊PHP的數組生成Dot描述的PHP插件，生成dot描述以後可以通過一些渲染工具生成圖像，本例用的是 Graphviz。 

        擴充的實作很簡單，PHP數組源碼是由下面的兩種結構體實作的，擴充就是将這兩種結構體和各個結構體的關系周遊一遍，生成對應的Dot描述即可。 

Java代碼  

1. typedef struct bucket {  
2.      ulong h;                           
3.      uint nKeyLength;  
4.      void * pData;  
5.      void * pDataPtr;  
6.      struct bucket * pListNext;  
7.      struct bucket * pListLast;  
8.      struct bucket *pNext ;  
9.      struct bucket * pLast;  
10.      const char *arKey ;  
11. } Bucket;  
12. typedef struct _hashtable {  
13.      uint nTableSize;  
14.      uint nTableMask;  
15.      uint nNumOfElements;  
16.      ulong nNextFreeElement;  
17.      Bucket *pInternalPointer;      
18.      Bucket *pListHead;  
19.      Bucket *pListTail;  
20.      Bucket **arBuckets;  
21.      dtor_func_t pDestructor;  
22.      zend_bool persistent;  
23.      unsigned char nApplyCount ;  
24.      zend_bool bApplyProtection;  
25. } HashTable;  

擴充裡邊函數說明  

--------------------------------------------------------------------------------------------- 

string    dotarray( array $input [, int $flag] ) 

生成數組資料結構的dot描述 

參數  

input   需要操作的數組 

flag   檢視那些資料結構，是擴充提供的3個常量或操作，分别是 

     DOTARAAY_HASH_TABLE 表示顯示HashTable結構 

     DOTARRAY_DOUBLE_LIST 顯示數組的雙連結清單結構 

     DOTARRAY_CURRENT_POSITION 顯示數組現在的内部指針的位置 

傳回值  

成功傳回dot描述字元串，錯誤（非數組等情況）傳回false 

--------------------------------------------------------------------------------------------- 

顯示雙連結清單結構例子  

Java代碼  

1. <?php  
2. $items = array(1,2,8=>'lalala',16=>'hahaha','name'=>'shiki',30=>'wooooo...');  
3. next($items);  
4. $result = dotarray($items,DOTARRAY_DOUBLE_LIST|DOTARRAY_CURRENT_POSITION);  
5. echo  $result;  

得到的dot描述： 

Java代碼  

1. digraph html {label = "Structure of array";  
2. node[shape = record];  
3. ===========部分内容省略============  
4. edge [color=black];  
5. edge [color=green];  
6. sk_array:f5:s -> sk_item_1:f0;  
7. edge [color=black];  
8. }  

通過graphviz渲染得到下面的圖檔 

需要解釋一下，紅色實線為結構中雙連結清單的next指針，紅色點線為上一個元素指針。同時提供了DOTARRAY_CURRENT_POSITION标志，出現綠線指向數組内部指針指向key為1的元素（第一個元素key為0） 

顯示HashTable結構例子  

Java代碼  

1. <?php  
2. $items = array(1,2,8=>'lalala',16=>'hahaha','name'=>'shiki',30=>'wooooo...');  
3. next($items);  
4. next($items);  
5. $result = dotarray($items,DOTARAAY_HASH_TABLE|DOTARRAY_CURRENT_POSITION);  
6. echo $result;  

生成的結構圖檔如下： 

hash沖突的例子  

       具體可以參考 PHP hash碰撞拒絕服務漏洞原理 http://www.laruence.com/2011/12/29/2412.html ，簡單介紹即是：Hash表因為”沖突”(碰撞)而退化成連結清單，如果資料量足夠大, 使得php在計算, 查找, 插入的時候, 造成大量的CPU占用, 進而實作拒絕服務攻擊。下面是簡單的碰撞生成代碼： 

< Java代碼  

1. ?php  
2. $n= 3;  
3. $capacity = pow(2,$n);  
4. $array =array();  
5. for($i=0;$i<$capacity;$i++){  
6.     $key = $i<<$n;  
7.     $array[$key] =1;  
8. }  
9. $str = dotarray($array,DOTARRAY_DOUBLE_LIST|DOTARAAY_HASH_TABLE);  
10. echo $str,PHP_EOL;  

這次将hashtable和雙線表同時展示出來，傳遞的flag為DOTARRAY_DOUBLE_LIST|DOTARAAY_HASH_TABLE，同時展示雙連結清單和HashTable 

關于 dot語言 傳送門:http://zh.wikipedia.org/wiki/DOT%E8%AF%AD%E8%A8%80 

關于 dot渲染工具Graphviz 傳送門：http://www.graphviz.org/

擴充源碼:https://github.com/Himer/dotarray