皆知PHP的数组是由HashTable和双链表实现的,为了方便大家查看数组的数据结构,开发一个遍历PHP的数组生成Dot描述的PHP插件,生成dot描述以后可以通过一些渲染工具生成图像,本例用的是 Graphviz。
扩展的实现很简单,PHP数组源码是由下面的两种结构体实现的,扩展就是将这两种结构体和各个结构体的关系遍历一遍,生成对应的Dot描述即可。
typedef struct bucket {
ulong h;
uint nKeyLength;
void * pData;
void * pDataPtr;
struct bucket * pListNext;
struct bucket * pListLast;
struct bucket *pNext ;
struct bucket * pLast;
const char *arKey ;
} Bucket;
typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer;
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets;
dtor_func_t pDestructor;
zend_bool persistent;
unsigned char nApplyCount ;
zend_bool bApplyProtection;
} HashTable;
扩展里边函数说明
---------------------------------------------------------------------------------------------
string dotarray( array $input [, int $flag] )
生成数组数据结构的dot描述
参数
input 需要操作的数组
flag 查看那些数据结构,是扩展提供的3个常量或操作,分别是
DOTARAAY_HASH_TABLE 表示显示HashTable结构
DOTARRAY_DOUBLE_LIST 显示数组的双链表结构
DOTARRAY_CURRENT_POSITION 显示数组现在的内部指针的位置
返回值
成功返回dot描述字符串,错误(非数组等情况)返回false
---------------------------------------------------------------------------------------------
显示双链表结构例子
<?php
$items = array(1,2,8=>'lalala',16=>'hahaha','name'=>'shiki',30=>'wooooo...');
next($items);/*将内部指针移到下一位*/
$result = dotarray($items,DOTARRAY_DOUBLE_LIST|DOTARRAY_CURRENT_POSITION);
echo $result;
得到的dot描述:
digraph html {label = "Structure of array";
node[shape = record];
===========部分内容省略============
edge [color=black];
edge [color=green];
sk_array:f5:s -> sk_item_1:f0;
edge [color=black];
}
通过graphviz渲染得到下面的图片
需要解释一下,红色实线为结构中双链表的next指针,红色点线为上一个元素指针。同时提供了DOTARRAY_CURRENT_POSITION标志,出现绿线指向数组内部指针指向key为1的元素(第一个元素key为0)
显示HashTable结构例子
<?php
$items = array(1,2,8=>'lalala',16=>'hahaha','name'=>'shiki',30=>'wooooo...');
next($items);
next($items);
$result = dotarray($items,DOTARAAY_HASH_TABLE|DOTARRAY_CURRENT_POSITION);
echo $result;
生成的结构图片如下:
hash冲突的例子
具体可以参考 PHP hash碰撞拒绝服务漏洞原理
http://www.laruence.com/2011/12/29/2412.html,简单介绍即是:Hash表因为”冲突”(碰撞)而退化成链表,如果数据量足够大, 使得php在计算, 查找, 插入的时候, 造成大量的CPU占用, 从而实现拒绝服务攻击。下面是简单的碰撞生成代码:
<
?php
/*会生出pow(2,$n)个数字*/
$n= 3;
$capacity = pow(2,$n);
$array =array();
for($i=0;$i<$capacity;$i++){
$key = $i<<$n;
$array[$key] =1;
}
$str = dotarray($array,DOTARRAY_DOUBLE_LIST|DOTARAAY_HASH_TABLE);
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/
- 大小: 45.1 KB
- 大小: 40.7 KB
- 大小: 82.5 KB
分享到:
相关推荐
Two demos illustrate use of SimPowerSystems for modeling a PV array connected to a utility grid. PVarray_Grid_IncCondReg_det.mdl is a detailed model of a 100-kW array connected to a 25-kV grid via a ...
Yet another implementation of a lock-free circular array queue
该资源主要介绍了android数组资源string-array integer-array的用法 包括int类型、string类型、文件类型的使用
按副本更改数组向Array.prototype提供其他... start, end) -> Array Array.prototype.popped() -> Array Array.prototype.pushed(values...) -> Array Array.prototype.reversed() -> Array Array.prototype.shifted
前端开源库-ml-array-rescaleml数组重新缩放,将数组重新缩放到一个范围内
前端开源库-simple-array-diff简单数组diff,查找在两个数组或元素或对象之间显式添加和删除的元素。
Laravel开发-multi-level-array-iterator 提供了一种在任意深度的嵌套数组之间循环的方法
leetcode-tag-array
is-whole-number-array-源码.rar
前端开源库-object-to-array对象到数组,将对象转换为数组,其中每个项都是键和值的数组
is-shared-array-buffer 这个值是JS SharedArrayBuffer吗? 尽管有ES6 Symbol.toStringTag,该模块仍可跨领域/ iframe运行,不依赖于instanceof或可变属性。例子var assert = require ( 'assert' ) ;var ...
基于matlab实现带论文sound-localization-intensity-mic-array.rar
服务器 HPE-Smart-Array-磁盘控制器用户指南 P410,P420 P430 P440 P820 P840
d3-array, array 操作,排序,搜索,汇总等 d3-arrayJavaScript中的数据通常由 array 表示,因这里可以以在可以视化或者分析数据时操作数组。 一些常见的操作形式包括采用一个连续的切片( 子集),使用谓词函数过滤一...
前端大厂最新面试题-cycle-sorted-array.docx
flower-daffodil-array模板.ppt
C语言-二维数组two-dimensional-array-master.zip
2007-ZENIC-Agile-Beam Phased Array Radar for Weather Observations
前端开源库-is-any-array是任何数组,请检查toString.Call是否以数组结尾