PHP内核学习:PHP中的HashTable(二)

标签: php, hashtable, php内核

0x01 前言

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

0x02 PHP哈希表的实现

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

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

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开发组的才会做出这种优化策略吧,在往哈希表中插入数据时再去创建存储空间

哈希表的增删改查

未完待续...

评论已关闭