PHP5.3里面数组的的实现方式

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› PHP›PHP编程经验

原作者: [db:作者] 来自: [db:来源] 收藏邀请

typedef struct _Bucket
{
    char *key;
    void *value;
    struct _Bucket *next;
} Bucket;
 
typedef struct _HashTable
{
    int size;        // 哈希表的大小
    int elem_num;    // 已经保存元素的个数
    Bucket **buckets;
} HashTable;

在 HashTable 里面存放这 Bucket 的指针数组，而 Bucket 本身的`*next`是用来解决 hash 冲突的，一个 key 下面对应多个值的情况，就放在一个链表上。

画了我好久，下面这张图

看到一篇文章，正好就是把 php 里面的 hashtable 给抽出来了：http://liuzhiqiangruc.iteye.com/blog/1871334

更加具体详细的介绍：http://www.php-internals.com/book/?p=chapt03/03-01-02-hashtable-in-php

下面是自己的笔记：

php 里所有的变量都存在了结构体_zval_struct中：

1 struct _zval_struct {
2 zvalue_value value; // 存储的变量的值
3 zend_unit refcount__gc; // 表示引用的次数 默认为1
4 zend_uchar type; // 变量具体的类型 IS_NULL、IS_BOOL、IS_LONG、IS_DOUBLE、IS_STRING、IS_ARRAY、IS_OBJECT和IS_RESOURCE 之一
5 zend_uchar is_ref_gc; // 表示是否为引用 默认为0
6 }

从上面的可以看出，存储的值又存储在联合体`zvalue_value`中：

typedef union _zvalue_value {
long lval; /* long value */
double dval; /* double value */
struct {
char *val;
int len;
} str;
HashTable *ht; /* hash table value */
zend_object_value obj;
} zvalue_value;

而在 php 中数组实际在`_zvalue_value`里存储的就是HashTable. 上面定义的简单的 hashtable 不足于满足 php 实际复杂业务逻辑的需求，我们需要的功能很多，比如count,array_pop,next,pre,current等。所以为了让这些操作更加高效，就选择了用空间换时间的做法，存储更多的字段，存储更多的关联关系。

typedef struct _hashtable {
uint nTableSize; // hash Bucket的大小，最小为8，以2x增长。
uint nTableMask; // nTableSize-1 ， 索引取值的优化
uint nNumOfElements; // hash Bucket中当前存在的元素个数，count()函数会直接返回此值
ulong nNextFreeElement; // 下一个数字索引的位置
Bucket *pInternalPointer; // 当前遍历的指针（foreach比for快的原因之一）
Bucket *pListHead; // 存储数组头元素指针
Bucket *pListTail; // 存储数组尾元素指针
Bucket **arBuckets; // 存储hash数组
dtor_func_t pDestructor; // 在删除元素时执行的回调函数，用于资源的释放
zend_bool persistent; //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;

然后 bucket 则如果有 hash 冲突，使得其相互之间是一个双向链表的结构

 1 typedef struct bucket {
 2 ulong h; // 对char *key进行hash后的值，或者是用户指定的数字索引值
 3 uint nKeyLength; // hash关键字的长度，如果数组索引为数字，此值为0
 4 void *pData; // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
 5 void *pDataPtr; //如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
 6 struct bucket *pListNext; // 整个hash表的下一元素
 7 struct bucket *pListLast; // 整个哈希表该元素的上一个元素
 8 struct bucket *pNext; // 存放在同一个hash Bucket内的下一个元素
 9 struct bucket *pLast; // 同一个哈希bucket的上一个元素
10 // 保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体
11 char arKey[1];
12 } Bucket;