嗨,老铁,欢迎来到我的博客!

如果觉得我的内容还不错的话,可以关注下我在 segmentfault.com 上的直播。我主要从事 PHP 和 Java 方面的开发,《深入 PHP 内核》作者之一。

[视频直播] PHP 进阶之路 - 亿级 pv 网站架构的技术细节与套路 直播中我将毫无保留的分享我这六年的全部工作经验和踩坑的故事,以及会穿插着一些面试中的 考点难点加分点

周梦康 发表于 2015-06-25 8735 次浏览 标签 : php

免费领取阿里云优惠券 我的直播 - 《PHP 进阶之路》

最简陋的用 C 语言实现的 hashtable

https://github.com/reeze/tipi/blob/master/book/sample/chapt03/03-01-01-hashtable/hashtable.h

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 下面对应多个值的情况,就放在一个链表上。

画了我好久,下面这张图

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

看到一篇文章,正好就是把 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中:

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

从上面的可以看出,存储的值又存储在联合体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 冲突,使得其相互之间是一个双向链表的结构

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

PHP 内部的 hashtable 的示意图(来源于网络):

嗨,老铁,欢迎来到我的博客!

如果觉得我的内容还不错的话,可以关注下我在 segmentfault.com 上的直播。我主要从事 PHP 和 Java 方面的开发,《深入 PHP 内核》作者之一。

[视频直播] PHP 进阶之路 - 亿级 pv 网站架构的技术细节与套路 直播中我将毫无保留的分享我这六年的全部工作经验和踩坑的故事,以及会穿插着一些面试中的 考点难点加分点

评论列表