转载

PHP内核学习：PHP中的HashTable（二）

0x01 前言

之前说过了哈希表的一些基础概念，下面我们看下PHP中哈希表的实现。首先要明确的是PHP5.*和PHP7的哈希实现是不同的，本文先分析php5.5.28为基础。

0x02 PHP哈希表的实现

了解了哈希表的实现原理之后，要看PHP的哈希表是如何实现的就很容易了，只需要注意下面三点：

哈希函数如何构造
哈希冲突如何解决
操作接口如何实现

PHP哈希表的哈希函数

DJBX33A 又叫 time33 ，PHP的哈希函数就是用的time33，经典是经过实践检验的。很多开源软件的哈希函数用的就是time33，比如apache、Berkeley DB。对于字符串而言这是目前所知道的最好的哈希算法，该算法的速度非常快，而且冲突小,分布均匀。

算法的核心思想是：

hash(i) = hash(i-1) * 33 + str[i]

PHP的time33实现：

static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength) { register ulong hash = 5381; /* variant with the hash unrolled eight times */ for (; nKeyLength >= 8; nKeyLength -= 8) {  hash = ((hash << 5) + hash) + *arKey++;  hash = ((hash << 5) + hash) + *arKey++;  hash = ((hash << 5) + hash) + *arKey++;  hash = ((hash << 5) + hash) + *arKey++;  hash = ((hash << 5) + hash) + *arKey++;  hash = ((hash << 5) + hash) + *arKey++;  hash = ((hash << 5) + hash) + *arKey++;  hash = ((hash << 5) + hash) + *arKey++; } switch (nKeyLength) {  case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */  case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */  case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */  case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */  case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */  case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */  case 1: hash = ((hash << 5) + hash) + *arKey++; break;  case 0: break; EMPTY_SWITCH_DEFAULT_CASE() } return hash; }

相对于apache等其他软件使用的time33算法而言，PHP并没有直接乘33，而是使用的hash << 5 + hash，这样比乘法速度更快。从这个函数可以看出来PHP鼓励hash字符串的长度小于等于8位，一般也不会有人把key的长度设置的超过8位吧。说白了就是以空间换时间，哈希的字符串长度大于8位时一次for循环就执行了8次hash

hash的初始值设置成了5381, 相比在Apache中的times算法和Perl中的Hash算法(都采用初始hash为0), 为什么是5381?这是个神奇的数字，集素数、奇数、缺数为一身，而且它的二进制也很独特。在测试中，3581可以导致哈希碰撞更少，避免雪崩。

PHP哈希表的结构：

PHP实现HashTable主要是通过两个数据结构Bucket(桶)和HashTable。具体结构定义在php-src/Zend/zend_hash.h

Bucket 槽

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

HashTable：需要注意的是，nTableSize和nNumOfElements的区别，nTableSize表示哈希表中槽的数量，nNumOfElements表示哈希表中存储数据元素的总个数。

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

哈希表的初始化

首先看下哈希表的初始化函数：

ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC) { uint i = 3; SET_INCONSISTENT(HT_OK);//和debug有关 if (nSize >= 0x80000000) {  /* 防止溢出，哈希表最大限制 */  ht->nTableSize = 0x80000000; } else {   /* 1U即无符号整数1，默认初始容量为8（1<<3），每次扩大均为2的整数次方 */  while ((1U << i) < nSize) {   i++;  }  ht->nTableSize = 1 << i; }  //初始化值 ht->nTableMask = 0; /* 0 means that ht->arBuckets is uninitialized */ ht->pDestructor = pDestructor; ht->arBuckets = (Bucket**)&uninitialized_bucket;//实际的数据存储空间还未创建，uninitialized_bucket的值是NULL ht->pListHead = NULL; ht->pListTail = NULL; ht->nNumOfElements = 0;//尚未存储元素 ht->nNextFreeElement = 0; ht->pInternalPointer = NULL; ht->persistent = persistent; ht->nApplyCount = 0; ht->bApplyProtection = 1; return SUCCESS; }

为什么将哈希表槽的数量调整为2的整数次方？先看下PHP的哈希表将哈希值映射到槽位的方法：

h = zend_inline_hash_func(arKey, nKeyLength); nIndex = h & ht->nTableMask;

从上面的zend_hash_do_resize()函数中可知，ht->nTableMask的大小为ht->nTableSize -1。这里使用&操作而不是使用取模，这是因为是相对来说取模操作的消耗和按位与的操作大很多。

nTableMask的作用就是将哈希值映射到槽位所能存储的索引范围内。例如：某个key的索引值是21，哈希表的大小为8，则mask为7，则求与时的二进制表示为： 10101 & 111 = 101 也就是十进制的5。因为2的整数次方-1的二进制比较特殊：后面N位的值都是1，这样比较容易能将值进行映射，如果是普通数字进行了二进制与之后会影响哈希值的结果。那么哈希函数计算的值的平均分布就可能出现影响。

为什么初始化哈希表时没有创建数据存储空间？我认为这是优化的一种方式，为了节省内存，因为有时候我们写代码的时候会先定义一个变量为数组，但是数组并没有值。所以PHP开发组的才会做出这种优化策略吧，在往哈希表中插入数据时再去创建存储空间