澳门新浦京电子游戏PHP 源代码分析 Zend HashTable详解第1/3页_php技巧_脚本之家

在PHP内核中,其中一个很重要的数据结构就是HashTable。我们常用的数组,在内核中就是用HashTable来实现。那么,PHP的HashTable是怎么实现的呢?最近在看HashTable的数据结构,但是算法书籍里面没有具体的实现算法,刚好最近也在阅读PHP的源码,于是参考PHP的HashTable的实现,自己实现了一个简易版的HashTable,总结了一些心得,下面给大家分享一下。

最近看了篇关于php内的hashtable的文章,PHP数据存储的核心,各种常量、变量、函数、类、对象等都用它来组织的。转载地址 ,源码还没看,看了第一部分的逻辑讲解,先转载一下

HashTable在通常的数据结构教材中也称作散列表,哈希表。其基本原理比较简单(如果你对其不熟悉,请查阅随便一本数据结构教材或在网上搜索),但PHP的实现有其独特的地方。理解了HashTable的数据存储结构,对我们分析PHP的源代码,特别是Zend
Engine中的虚拟机的实现时,有很重要的帮助。它可以帮助我们在大脑中模拟一个完整的虚拟机的形象。它也是PHP中其它一些数据结构如数组实现的基础。
Zend
HashTable的实现结合了双向链表和向量两种数据结构的优点,为PHP提供了非常高效的数据存储和查询机制。
Let’s begin! 一、 HashTable的数据结构 在Zend
Engine中的HashTable的实现代码主要包括zend_hash.h,
zend_hash.c这两个文件中。Zend
HashTable包括两个主要的数据结构,其一是Bucket结构,另一个是HashTable结构。Bucket结构是用于保存数据的容器,而HashTable结构则提供了对所有这些Bucket进行管理的机制。复制代码 代码如下:typedef struct bucket { ulong
h; /* Used for numeric indexing */ uint nKeyLength; /* key 长度 */
void *pData; /* 指向Bucket中保存的数据的指针 */ void *pDataPtr; /*
指针数据 */ struct bucket *pListNext; /*
指向HashTable桶列中下一个元素 */ struct bucket *pListLast; /*
指向HashTable桶列中前一个元素 */ struct bucket *pNext; /*
指向具有同一个hash值的桶列的后一个元素 */ struct bucket *pLast; /*
指向具有同一个hash值的桶列的前一个元素 */ char arKey[1]; /*
必须是最后一个成员,key名称*/ } Bucket; 在Zend
HashTable中,每个数据元素,它在整个HashTable中是唯一的,不能重复。根据键名可以唯一确定HashTable中的数据元素。键名有两种表示方式。第一种方式使用字符串arKey作为键名,该字符串的长度为nKeyLength。注意到在上面的数据结构中arKey虽然只是一个长度为1的字符数组,但它并不意味着key只能是一个字符。实际上Bucket是一个可变长的结构体,由于arKey是Bucket的最后一个成员变量,通过arKey与nKeyLength结合可确定一个长度为nKeyLength的key。这是C语言编程中的一个比较常用的技巧。另一种键名的表示方式是索引方式,这时nKeyLength总是0,长整型字段h就表示该数据元素的键名。简单的来说,即如果nKeyLength=0,则键名为h;否则键名为arKey,
键名的长度为nKeyLength。 当nKeyLength >
0时,并不表示这时的h值就没有意义。事实上,此时它保存的是arKey对应的hash值。不管hash函数怎么设计,冲突都是不可避免的,也就是说不同的arKey可能有相同的hash值。具有相同hash值的Bucket保存在HashTable的arBuckets数组的同一个索引对应的桶列中。这个桶列是一个双向链表,其前向元素,后向元素分别用pLast,
pNext来表示。新插入的Bucket放在该桶列的最前面。
在Bucket中,实际的数据是保存在pData指针指向的内存块中,通常这个内存块是系统另外分配的。但有一种情况例外,就是当Bucket保存的数据是一个指针时,HashTable将不会另外请求系统分配空间来保存这个指针,而是直接将该指针保存到pDataPtr中,然后再将pData指向本结构成员的地址。这样可以提高效率,减少内存碎片。由此我们可以看到PHP
HashTable设计的精妙之处。如果Bucket中的数据不是一个指针,pDataPtr为NULL。
HashTable中所有的Bucket通过pListNext,
pListLast构成了一个双向链表。最新插入的Bucket放在这个双向链表的最后。
注意在一般情况下,Bucket并不能提供它所存储的数据大小的信息。所以在PHP的实现中,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; #if
ZEND_DEBUG int inconsistent; #endif } HashTable; 123下一页阅读全文

笔者github上有一个简易版的HashTable的实现:HashTable实现

HashTable在通常的数据结构教材中也称作散列表,哈希表。其基本原理比较简单(如果你对其不熟悉,请查阅随便一本数据结构教材或在网上搜
索),但PHP的实现有其独特的地方。理解了HashTable的数据存储结构,对我们分析PHP的源代码,特别是Zend
Engine中的虚拟机的实现时,有很重要的帮助。它可以帮助我们在大脑中模拟一个完整的虚拟机的形象。它也是PHP中其它一些数据结构如数组实现的基
础。

另外,我在github有对PHP源码更详细的注解。感兴趣的可以围观一下,给个star。PHP5.4源码注解。可以通过commit记录查看已添加的注解。

Zend
HashTable的实现结合了双向链表和向量(数组)两种数据结构的优点,为PHP提供了非常高效的数据存储和查询机制。

HashTable的介绍

哈希表是实现字典操作的一种有效数据结构。

一、 HashTable的数据结构

定义

简单地说,HashTable(哈希表)就是一种键值对的数据结构。支持插入,查找,删除等操作。在一些合理的假设下,在哈希表中的所有操作的时间复杂度是O(1)(对相关证明感兴趣的可以自行查阅)。

在Zend Engine中的HashTable的实现代码主要包括zend_hash.h,
zend_hash.c这两个文件中。Zend
HashTable包括两个主要的数据结构,其一是Bucket(桶)结构,另一个是HashTable结构。Bucket结构是用于保存数据的容器,而
HashTable结构则提供了对所有这些Bucket(或桶列)进行管理的机制。

实现哈希表的关键

在哈希表中,不是使用关键字做下标,而是通过哈希函数计算出key的哈希值作为下标,然后查找/删除时再计算出key的哈希值,从而快速定位元素保存的位置。

在一个哈希表中,不同的关键字可能会计算得到相同的哈希值,这叫做“哈希冲突”,就是处理两个或多个键的哈希值相同的情况。解决哈希冲突的方法有很多,开放寻址法,拉链法等等。

因此,实现一个好的哈希表的关键就是一个好的哈希函数和处理哈希冲突的方法。

Hash函数

判断一个哈希算法的好坏有以下四个定义: > *
一致性,等价的键必然产生相等的哈希值; > * 高效性,计算简便; >
* 均匀性,均匀地对所有的键进行哈希。

哈希函数建立了关键值与哈希值的对应关系,即:h =
hash_func(key)。对应关系见下图:

澳门新浦京电子游戏 1

设计一个完美的哈希函数就交由专家去做吧,我们只管用已有的较成熟的哈希函数就好了。PHP内核使用的哈希函数是time33函数,又叫DJBX33A,其实现如下:

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;
}

注:函数使用了一个8次循环+switch来实现,是对for循环的优化,减少循环的运行次数,然后在switch里面执行剩下的没有遍历到的元素。

在Zend
HashTable中,每个数据元素(Bucket)有一个键名(key),它在整个HashTable中是唯一的,不能重复。根据键名可以唯一确定
HashTable中的数据元素。键名有两种表示方式。第一种方式使用字符串arKey作为键名,该字符串的长度为nKeyLength。注意到在上面的
数据结构中arKey虽然只是一个长度为1的字符数组,但它并不意味着key只能是一个字符。实际上Bucket是一个可变长的结构体,由于arKey是
Bucket的最后一个成员变量,通过arKey与nKeyLength结合可确定一个长度为nKeyLength的key。这是C语言编程中的一个比较
常用的技巧。另一种键名的表示方式是索引方式,这时nKeyLength总是0,长整型字段h就表示该数据元素的键名。简单的来说,即如果
nKeyLength=0,则键名为h;否则键名为arKey, 键名的长度为nKeyLength。

拉链法

将所有具有相同哈希值的元素都保存在一条链表中的方法叫拉链法。查找的时候通过先计算key对应的哈希值,然后根据哈希值找到对应的链表,最后沿着链表顺序查找相应的值。
具体保存后的结构图如下:

澳门新浦京电子游戏 2

当nKeyLength >
0时,并不表示这时的h值就没有意义。事实上,此时它保存的是arKey对应的hash值。不管hash函数怎么设计,冲突都是不可避免的,也就是说不同
的arKey可能有相同的hash值。具有相同hash值的Bucket保存在HashTable的arBuckets数组(参考下面的解释)的同一个索
引对应的桶列中。这个桶列是一个双向链表,其前向元素,后向元素分别用pLast,
pNext来表示。新插入的Bucket放在该桶列的最前面(类似学校里的某同学在同班级(即相同哈希值)中报道前后的关系。比如小刚和小明是同班级的,小刚在小明之前报道,所以小刚的pLast指到小明,小明的pNext指到小刚)。

PHP的HashTable结构

简单地介绍了哈希表的数据结构之后,继续看看PHP中是如何实现哈希表的。

(图片源自网络,侵权即删)

在Bucket中,实际的数据是保存在pData指针指向的内存块中,通常这个内存块是系统另外分配的。但有一种情况例外,就是当Bucket保存
的数据是一个指针时,HashTable将不会另外请求系统分配空间来保存这个指针,而是直接将该指针保存到pDataPtr中,然后再将pData指向
本结构成员的地址。这样可以提高效率,减少内存碎片。由此我们可以看到PHP
HashTable设计的精妙之处。如果Bucket中的数据不是一个指针,pDataPtr为NULL。

PHP内核hashtable的定义:

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;
          #if ZEND_DEBUG
               int inconsistent;
          #endif
} HashTable;
  • nTableSize,HashTable的大小,以2的倍数增长
  • nTableMask,用在与哈希值做与运算获得该哈希值的索引取值,arBuckets初始化后永远是nTableSize-1
  • nNumOfElements,HashTable当前拥有的元素个数,count函数直接返回这个值
  • nNextFreeElement,表示数字键值数组中下一个数字索引的位置
  • pInternalPointer,内部指针,指向当前成员,用于遍历元素
  • pListHead,指向HashTable的第一个元素,也是数组的第一个元素
  • pListTail,指向HashTable的最后一个元素,也是数组的最后一个元素。与上面的指针结合,在遍历数组时非常方便,比如reset和endAPI
  • arBuckets,包含bucket组成的双向链表的数组,索引用key的哈希值和nTableMask做与运算生成
  • pDestructor,删除哈希表中的元素使用的析构函数
  • persistent,标识内存分配函数,如果是TRUE,则使用操作系统本身的内存分配函数,否则使用PHP的内存分配函数
  • nApplyCount,保存当前bucket被递归访问的次数,防止多次递归
  • bApplyProtection,标识哈希表是否要使用递归保护,默认是1,要使用

举一个哈希与mask结合的例子:

例如,”foo”真正的哈希值(使用DJBX33A哈希函数)是193491849。如果我们现在有64容量的哈希表,我们明显不能使用它作为数组的下标。取而代之的是通过应用哈希表的mask,然后只取哈希表的低位。

hash           |        193491849  |     0b1011100010000111001110001001
& mask         | &             63  | &   0b0000000000000000000000111111
----------------------------------------------------------------------
= index        | = 9               | =   0b0000000000000000000000001001

因此,在哈希表中,foo是保存在arBuckets中下标为9的bucket向量中。

HashTable中所有的Bucket通过pListNext,
pListLast构成了一个双向链表。最新插入的Bucket放在这个双向链表的最后(类似学校里的某同学在其报道前后的关系。没有班级限制)。

bucket结构体的定义

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;
  • h,哈希值(或数字键值的key
  • nKeyLength,key的长度
  • pData,指向数据的指针
  • pDataPtr,指针数据
  • pListNext,指向HashTable中的arBuckets链表中的下一个元素
  • pListLast,指向HashTable中的arBuckets链表中的上一个元素
  • pNext,指向具有相同hash值的bucket链表中的下一个元素
  • pLast,指向具有相同hash值的bucket链表中的上一个元素
  • arKey,key的名称

PHP中的HashTable是采用了向量加双向链表的实现方式,向量在arBuckets变量保存,向量包含多个bucket的指针,每个指针指向由多个bucket组成的双向链表,新元素的加入使用前插法,即新元素总是在bucket的第一个位置。由上面可以看到,PHP的哈希表实现相当复杂。这是它使用超灵活的数组类型要付出的代价。

一个PHP中的HashTable的示例图如下所示:

澳门新浦京电子游戏 3

注意在一般情况下,Bucket并不能提供它所存储的数据大小的信息。所以在PHP的实现中,Bucket中保存的数据必须具有管理自身大小的能力。

HashTable相关API

  • zend_hash_init
  • zend_hash_add_or_update
  • zend_hash_find
  • zend_hash_del_key_or_index

zend_hash_init

函数执行步骤

  • 设置哈希表大小
  • 设置结构体其他成员变量的初始值
    (包括释放内存用的析构函数pDescructor)

详细代码注解点击:zend_hash_init源码

注:

1、pHashFunction在此处并没有用到,php的哈希函数使用的是内部的zend_inline_hash_func

2、zend_hash_init执行之后并没有真正地为arBuckets分配内存和计算出nTableMask的大小,真正分配内存和计算nTableMask是在插入元素时进行CHECK_INIT检查初始化时进行。

在HashTable结构中,nTableSize指定了HashTable的大小,同时它限定了HashTable中能保存Bucket的最大数量,此
数越大,系统为HashTable分配的内存就越多。为了提高计算效率,系统自动会将nTableSize调整到最小一个不小于nTableSize的2
的整数次方。也就是说,如果在初始化HashTable时指定一个nTableSize不是2的整数次方,系统将会自动调整nTableSize的值。即

zend_hash_add_or_update

函数执行步骤

  • 检查键的长度
  • 检查初始化
  • 计算哈希值和下标
  • 遍历哈希值所在的bucket,如果找到相同的key且值需要更新,则更新数据,否则继续指向bucket的下一个元素,直到指向bucket的最后一个位置
  • 为新加入的元素分配bucket,设置新的bucket的属性值,然后添加到哈希表中
  • 如果哈希表空间满了,则重新调整哈希表的大小

nTableSize = 2ceil(log(nTableSize, 2)) 或 nTableSize =
pow(ceil(log(nTableSize,2)))

函数执行流程图

澳门新浦京电子游戏 4

CONNECT_TO_BUCKET_DLLIST是将新元素添加到具有相同hash值的bucket链表。

CONNECT_TO_GLOBAL_DLLIST是将新元素添加到HashTable的双向链表。

详细代码和注解请点击:zend_hash_add_or_update代码注解。

例如,如果在初始化HashTable的时候指定nTableSize =
11,HashTable初始化程序会自动将nTableSize增大到16。

zend_hash_find

函数执行步骤

  • 计算哈希值和下标
  • 遍历哈希值所在的bucket,如果找到key所在的bucket,则返回值,否则,指向下一个bucket,直到指向bucket链表中的最后一个位置

详细代码和注解请点击:zend_hash_find代码注解。

arBuckets是HashTable的关键,HashTable初始化程序会自动申请一块内存,并将其地址赋值给arBuckets,该内存大
小正好能容纳nTableSize个指针。我们可以将arBuckets看作一个大小为nTableSize的数组,每个数组元素都是一个指针,用于指向
实际存放数据的Bucket。当然刚开始时每个指针均为NULL。

zend_hash_del_key_or_index

函数执行步骤

  • 计算key的哈希值和下标
  • 遍历哈希值所在的bucket,如果找到key所在的bucket,则进行第三步,否则,指向下一个bucket,直到指向bucket链表中的最后一个位置
  • 如果要删除的是第一个元素,直接将arBucket[nIndex]指向第二个元素;其余的操作是将当前指针的last的next执行当前的next
  • 调整相关指针
  • 释放数据内存和bucket结构体内存

详细代码和注解请点击:zend_hash_del_key_or_index代码注解。

nTableMask的值永远是nTableSize –
1,引入这个字段的主要目的是为了提高计算效率,是为了快速计算Bucket键名在arBuckets数组中的索引。

性能分析

PHP的哈希表的优点:PHP的HashTable为数组的操作提供了很大的方便,无论是数组的创建和新增元素或删除元素等操作,哈希表都提供了很好的性能,但其不足在数据量大的时候比较明显,从时间复杂度和空间复杂度看看其不足。

不足如下:

  • 保存数据的结构体zval需要单独分配内存,需要管理这个额外的内存,每个zval占用了16bytes的内存;
  • 在新增bucket时,bucket也是额外分配,也需要16bytes的内存;
  • 为了能进行顺序遍历,使用双向链表连接整个HashTable,多出了很多的指针,每个指针也要16bytes的内存;
  • 在遍历时,如果元素位于bucket链表的尾部,也需要遍历完整个bucket链表才能找到所要查找的值

PHP的HashTable的不足主要是其双向链表多出的指针及zval和bucket需要额外分配内存,因此导致占用了很多内存空间及查找时多出了不少时间的消耗。

nNumberOfElements记录了HashTable当前保存的数据元素的个数。当nNumberOfElement大于nTableSize时,HashTable将自动扩展为原来的两倍大小。

后续

上面提到的不足,在PHP7中都很好地解决了,PHP7对内核中的数据结构做了一个大改造,使得PHP的效率高了很多,因此,推荐PHP开发者都将开发和部署版本更新吧。看看下面这段PHP代码:

<?php
$size = pow(2, 16); 

$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) {
    $array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 个恶意的元素需要 ', $endTime - $startTime, ' 秒', "n";

$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) {
    $array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 个普通元素需要 ', $endTime - $startTime, ' 秒', "n";

上面这个demo是有多个hash冲突时和无冲突时的时间消耗比较。笔者在PHP5.4下运行这段代码,结果如下

插入 65536 个恶意的元素需要 43.72204709053 秒

插入 65536 个普通元素需要 0.009843111038208 秒

而在PHP7上运行的结果:

插入 65536 个恶意的元素需要 4.4028408527374 秒

插入 65536 个普通元素需要 0.0018510818481445 秒

可见不论在有冲突和无冲突的数组操作,PHP7的性能都提升了不少,当然,有冲突的性能提升更为明显。至于为什么PHP7的性能提高了这么多,值得继续深究。

参考文章:

PHP数组的Hash冲突实例

Understanding PHP’s internal array implementation (PHP’s Source Code
for PHP Developers – Part
4)

PHP’s new hashtable
implementation

nNextFreeElement记录HashTable中下一个可用于插入数据元素的arBuckets的索引。

pListHead,
pListTail则分别表示Bucket双向链表的第一个和最后一个元素,这些数据元素通常是根据插入的顺序排列的。也可以通过各种排序函数对其进行重
新排列。pInternalPointer则用于在遍历HashTable时记录当前遍历的位置,它是一个指针,指向当前遍历到的Bucket,初始值是
pListHead。

pDestructor是一个函数指针,在HashTable的增加、修改、删除Bucket时自动调用,用于处理相关数据的清理工作。

persistent标志位指出了Bucket内存分配的方式。如果persisient为TRUE,则使用操作系统本身的内存分配函数为Bucket分配内存,否则使用PHP的内存分配函数。具体请参考PHP的内存管理。

nApplyCount与bApplyProtection结合提供了一个防止在遍历HashTable时进入递归循环时的一种机制。

inconsistent成员用于调试目的,只在PHP编译成调试版本时有效。表示HashTable的状态,状态有四种:

状态值 含义
HT_IS_DESTROYING 正在删除所有的内容,包括arBuckets本身
HT_IS_DESTROYED 已删除,包括arBuckets本身
HT_CLEANING 正在清除所有的arBuckets指向的内容,但不包括arBuckets本身
HT_OK 正常状态,各种数据完全一致

现在来看zend_hash_key结构就比较容易理解了。它通过arKey, nKeyLength,
h三个字段唯一确定了HashTable中的一个元素。

根据上面对HashTable相关数据结构的解释,我们可以画出HashTable的内存结构图:

澳门新浦京电子游戏 5

hashtable结构

二、 Zend HashTable的实现

本节具体介绍一下PHP中HashTable的实现。以下函数均取自于zend_hash.c。只要充分理解了上述数据结构,HashTable实现的代码并不难理解。

1 HashTable初始化

HashTable提供了一个zend_hash_init宏来完成HashTable的初始化操作。实际上它是通过下面的内部函数来实现的:

在以前的版本中,可以使用pHashFunction来指定hash函数。但现PHP已强制使用DJBX33A算法,因此实际上pHashFunction这个参数并不会用到,保留在这里只是为了与以前的代码兼容。

2 增加、插入和修改元素

向HashTable中添加一个新的元素最关键的就是要确定将这个元素插入到arBuckets数组中的哪个位置。根据上面对Bucket结构键名
的解释,我们可以知道有两种方式向HashTable添加一个新的元素。第一种方法是使用字符串作为键名来插入Bucket;第二种方法是使用索引作为键
名来插入Bucket。第二种方法具体又可以分为两种情况:指定索引或不指定索引,指定索引指的是强制将Bucket插入到指定的索引位置中;不指定索引
则将Bucket插入到nNextFreeElement对应的索引位置中。这几种插入数据的方法实现比较类似,不同的只是定位Bucket的方法。

修改HashTable中的数据的方法与增加数据的方法也很类似。

我们先看第一种使用字符串作为键名增加或修改Bucket的方法:

ZEND_API int _zend_hash_add_or_update(HashTable *ht, char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
ulong h;
uint nIndex;
Bucket *p;
 
IS_CONSISTENT(ht);     // 调试信息输出
 
if (nKeyLength &lt;= 0) { #if ZEND_DEBUG ZEND_PUTS(”zend_hash_update: Can’t put in empty keyn”); #endif return FAILURE; } /* 使用hash函数计算arKey的hash值 */ h = zend_inline_hash_func(arKey, nKeyLength); /* 将hash值和nTableMask按位与后生成该元素在arBuckets中的索引。让它和 * nTableMask按位与是保证不会产生一个使得arBuckets越界的数组下标。 */ nIndex = h &amp; ht-&gt;nTableMask;
 
p = ht-&gt;arBuckets[nIndex];   /* 取得相应索引对应的Bucket的指针 */
 
/* 检查对应的桶列中是否包含有数据元素(key, hash) */
while (p != NULL) {
if ((p-&gt;h == h) &amp;&amp; (p-&gt;nKeyLength == nKeyLength)) {
if (!memcmp(p-&gt;arKey, arKey, nKeyLength)) {
if (flag &amp; HASH_ADD) {
return FAILURE; // 对应的数据元素已存在,不能进行插入操作
}
HANDLE_BLOCK_INTERRUPTIONS();
#if ZEND_DEBUG
if (p-&gt;pData == pData) {
ZEND_PUTS(”Fatal error in zend_hash_update: p-&gt;pData == pDatan”);
HANDLE_UNBLOCK_INTERRUPTIONS();
return FAILURE;
}
#endif
if (ht-&gt;pDestructor) {
/* 如果数据元素存在,对原来的数据进行析构操作 */
ht-&gt;pDestructor(p-&gt;pData);
}
/* 用新的数据来更新原来的数据 */
UPDATE_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p-&gt;pData;
}
HANDLE_UNBLOCK_INTERRUPTIONS();
return SUCCESS;
}
}
p = p-&gt;pNext;
}
 
/* HashTable中没有key对应的数据,新增一个Bucket */
p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht-&gt;persistent);
if (!p) {
return FAILURE;
}
memcpy(p-&gt;arKey, arKey, nKeyLength);
p-&gt;nKeyLength = nKeyLength;
INIT_DATA(ht, p, pData, nDataSize);
p-&gt;h = h;
// 将Bucket加入到相应的桶列中
CONNECT_TO_BUCKET_DLLIST(p, ht-&gt;arBuckets[nIndex]);
if (pDest) {
*pDest = p-&gt;pData;
}
 
HANDLE_BLOCK_INTERRUPTIONS();
// 将Bucket 加入到HashTable的双向链表中
CONNECT_TO_GLOBAL_DLLIST(p, ht);
ht-&gt;arBuckets[nIndex] = p;
HANDLE_UNBLOCK_INTERRUPTIONS();
 
ht-&gt;nNumOfElements++;
// 如果HashTable已满,重新调整HashTable的大小。
ZEND_HASH_IF_FULL_DO_RESIZE(ht);   /* If the Hash table is full, resize it */
return SUCCESS;
}

因为这个函数是使用字符串作为键名来插入数据的,因此它首先检查nKeyLength的值是否大于0,如果不是的话就直接退出。然后计算arKey对应的
hash值h,将其与nTableMask按位与后得到一个无符号整数nIndex。这个nIndex就是将要插入的Bucket在arBuckets数
组中的索引位置。
现在已经有了arBuckets数组的一个索引,我们知道它包括的数据是一个指向Bucket的双向链表的指针。如果这个双向链表不为空的话我们首先检查
这个双向链表中是否已经包含了用字符串arKey指定的键名的Bucket,这样的Bucket如果存在,并且我们要做的操作是插入新Bucket(通过
flag标识),这时就应该报错 –
因为在HashTable中键名不可以重复。如果存在,并且是修改操作,则使用在HashTable中指定了析构函数pDestructor对原来的
pData指向的数据进行析构操作;然后将用新的数据替换原来的数据即可成功返回修改操作。
如果在HashTable中没有找到键名指定的数据,就将该数据封装到Bucket中,然后插入HashTable。这里要注意的是如下的两个宏:
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex])
CONNECT_TO_GLOBAL_DLLIST(p, ht)
前者是将该Bucket插入到指定索引的Bucket双向链表中,后者是插入到整个HashTable的Bucket双向链表中。两者的插入方式也不同,前者是将该Bucket插入到双向链表的最前面,后者是插入到双向链表的最末端。

下面是第二种插入或修改Bucket的方法,即使用索引的方法:

flag标志指明当前操作是HASH_NEXT_INSERT(不指定索引插入或修改),
HASH_ADD(指定索引插入)还是HASH_UPDATE(指定索引修改)。由于这些操作的实现代码基本相同,因此统一合并成了一个函数,再用flag加以区分。
本函数基本与前一个相同,不同的是如果确定插入到arBuckets数组中的索引的方法。如果操作是HASH_NEXT_INSERT,则直接使用nNextFreeElement作为插入的索引。注意nNextFreeElement的值是如何使用和更新的。
3 访问元素
同样,HashTable用两种方式来访问元素,一种是使用字符串arKey的zend_hash_find();另一种是使用索引的访问方式zend_hash_index_find()。由于其实现的代码很简单,分析工作就留给读者自已完成。
4 删除元素
HashTable删除数据均使用zend_hash_del_key_or_index()函数来完成,其代码也较为简单,这里也不再详细分析。需要的是注意如何根据arKey或h来计算出相应的下标,以及两个双向链表的指针的处理。
5 遍历元素

因为HashTable中所有Bucket都可以通过pListHead指向的双向链表来访问,因此遍历HashTable的实现也比较简单。这里值得一
提的是对当前遍历到的Bucket的处理使用了一个apply_func_t类型的回调函数。根据实际需要,该回调函数返回下面值之一:

ZEND_HASH_APPLY_KEEP
ZEND_HASH_APPLY_STOP
ZEND_HASH_APPLY_REMOVE

它们分别表示继续遍历,停止遍历或删除相应元素后继续遍历。

还有一个要注意的问题就是遍历时的防止递归的问题,也就是防止对同一个HashTable同时进行多次遍历。这是用下面两个宏来实现的:
HASH_PROTECT_RECURSION(ht)
HASH_UNPROTECT_RECURSION(ht)
其主要原理是如果遍历保护标志bApplyProtection为真,则每次进入遍历函数时将nApplyCount值加1,退出遍历函数时将nApplyCount值减1。开始遍历之前如果发现nApplyCount
> 3就直接报告错误信息并退出遍历。

上面的apply_func_t不带参数。HashTable还提供带一个参数或可变参数的回调方式,对应的遍历函数分别为:

除了上面提供的几种提供外,还有许多其它操作HashTable的API。如排序、HashTable的拷贝与合并等等。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注