PHP内核探索之变量- hash table【转】

2015-10-20 18:11 
1568 
2

  在PHP中,除了zval, 另一个比较重要的数据结构非hash table莫属,例如我们最常见的数组,在底层便是hash table。除了数组,在线程安全(TSRM)、GC、资源管理、Global变量、ini配置管理中,几乎都有Hash table的踪迹(上一次我们也提到,符号表也是使用Hash table实现的)。那么,在PHP中,这种数据有什么特殊之处,结构是怎么实现的?

一、Hash table的基本介绍和背景知识

1. 基本定义

  Hash table,又叫哈希表,散列表,Hash表,维基百科上对哈希表的定义是:散列表,是根据关键字(Key value)而直接访问在内存存储位置的数据结构。也就是说,它通过把键值通过一个函数的计算,映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。”。提取文中的主干,我们可以得出如下信息:

(1).Hash table是一种数据结构。

(2).这种数据结构是普通数组的扩展。

(3).这种数据结构通过key->value的映射关系,使得插入和查找的效率很高(数组可以直接寻址,可在O(1)的时间内访问任意元素)。

  我们知道,在一般的数组、线性表、树中,记录在结构中的位置是相对随机的,即记录和关键字之间不存在直接的、确定的对应关系。在这些结构中,要查找 和插入关键字,常常需要进行一系列的比较,查找的效率通常是O(n)或者O(lgn)的。而Hash table通过Hash函数建立了关键字和记录之间的对应关系,使得普通的查找和插入操作可以在O(1)(平均时间复杂度)的时间内完成,这显然是最理想的查找方式。

2. Hash函数

  如上所述,Hash函数建立了关键字和记录之间的对应关系,即:Record = Hash(key) 理论上,哈希函数可以是任何函数如Crc32, unique_id,MD5,SHA1或者用户自定义的函数。这个函数的好坏直接关系到Hash table的性能(考虑冲突和查找的性能)。这里列举了几个常见的Hash函数和对应的实现,有兴趣的童鞋可以看看。一个典型的字符串Hash算法如下:

  1. function hash( $key ){
  2. $result = 0;
  3. $len = strlen($key);
  4. for($i = 0;$i < $len; $i++ ){
  5. $result += ord($key{$i}) * ((1 << 5) + 1);
  6. }
  7. return $result;
  8. }

3.冲突解决

  在理想的情况下,我们期望任何关键字计算出的Hash值都是唯一的,这样我们便可以通过Hash(key)这种方式直接定位到要查找的记录。但不幸 的,几乎没有一个Hash函数可以满足这样的特性(即使有这样的Hash函数,也可能很复杂,无法在实际中使用)。也就是说,即使是精心设计的Hash函 数,也经常会出现key1 != key2 但是hash(key1) = hash(key2)的情况,这便是Hash冲突(Hash碰撞)。解决Hash碰撞的主要方法有多种(见这里),作为示例,我们只简单讨论下链接法解决 冲突。这种方法的基本思想是:在哈希表出现冲突时,使用链表的形式链接所有具有相同hash值的记录,而哈希表中只保存链表的头指针。PHP底层的 Hash table,便是使用链表(双向链表)来解决hash冲突的。关于这一点,后续会有详细的介绍。引入链表之后,Hash table的结构如下所示:

一个Hash table的实现如下:

  1. Class HashTable{
  2. private $buckets = null;
  3. /* current size */
  4. private $size = 0;
  5. /* max hashtable size */
  6. private $max = 2048;
  7. private $mask = 0;
  8. public function __construct($size){
  9. $this->_init_hash($size);
  10. }
  11. /* hashtable init */
  12. private function _init_hash($size){
  13. if($size > $this->max){
  14. $size = $this->max;
  15. }
  16. $this->size = $size;
  17. $this->mask = $this->size - 1;
  18. // SplFixedArray is faster when the size is known
  19. // see http://php.net/manual/en/class.splfixedarray.php
  20. $this->buckets = new SplFixedArray($this->size);
  21. }
  22. public function hash( $key ){
  23. $result = 0;
  24. $len = strlen($key);
  25. for($i = 0;$i < $len; $i++ ){
  26. $result += ord($key{$i}) * ((1 << 5) + 1);
  27. }
  28. return $result % ($this->size);
  29. }
  30. /* 拉链法 */
  31. public function insert( $key, $val ){
  32. $h = $this->hash($key);
  33. if(!isset($this->buckets[$h])){
  34. $next = NULL;
  35. }else{
  36. $next = $this->bucket[$h];
  37. }
  38. $this->buckets[$h] = new Node($key, $val, $next);
  39. }
  40. /* 拉链法 */
  41. public function lookup( $key ){
  42. $h = $this->hash($key);
  43. $cur = $this->buckets[$h];
  44. while($cur !== NULL){
  45. if( $cur->key == $key){
  46. return $cur->value;
  47. }
  48. $cur = $cur->next;
  49. }
  50. return NULL;
  51. }
  52. }
  53. Class Node{
  54. public $key;
  55. public $value;
  56. public $next = null;
  57. public function __construct($key, $value, $next = null){
  58. $this->key = $key;
  59. $this->value = $value;
  60. $this->next = $next;
  61. }
  62. }
  63. $hash = new HashTable(200);
  64. $hash->insert('apple','this is apple');
  65. $hash->insert('orange','this is orange');
  66. $hash->insert('banana','this is banana');
  67. echo $hash->lookup('apple');

  我们知道,在PHP中,数组支持k->v这样的关联数组,也支持普通的数组。不仅支持直接寻址(根据关键字直接定位),而且支持线性遍历(foreach等)。这都要归功于Hash table这一强大和灵活的数据结构。

二、PHP中Hash table的基本结构和实现

1. 基本数据结构

  在PHP底层,与Hash table相关的结构定义、算法实现都位于Zend/zend_hash.c和Zend/zend_hash.h这两个文件中。PHP 的hash table实现包括两个重要的数据结构,一个是HashTable,另一个是bucket.前者是hash table的主体,后者则是构成链表的每个“结点”,是真正数据存储的容器。
(1) HashTable的基本结构
定义如下(zend_hash.h):

  1. typedef struct _hashtable {
  2. uint nTableSize;
  3. uint nTableMask;
  4. uint nNumOfElements;
  5. ulong nNextFreeElement;
  6. Bucket *pInternalPointer; /* Used for element traversal */
  7. Bucket *pListHead;
  8. Bucket *pListTail;
  9. Bucket **arBuckets;
  10. dtor_func_t pDestructor;
  11. zend_bool persistent;
  12. unsigned char nApplyCount;
  13. zend_bool bApplyProtection;
  14. #if ZEND_DEBUG
  15. int inconsistent;
  16. #endif
  17. } HashTable;

这是一个结构体,其中比较重要的几个成员:

  nTableSize 这个成员用于标明Hash表的大小,在hash表初始化操作的时候,会设定nTableSize的大小,而在hash表扩容的时候,也会相应调整这个数值的大小。注意这个数值并不是hash表中元素的个数。

  nTableMask 是一个“掩码”,主要用于快速计算一个元素的索引(nIndex = h & ht->nTableMask,在一般的Hash函数中,是通过模运算来确定索引的,但显然,位运算比模运算效率要高),在arBuckets初始 化之后,该值默认固定为nTableSize – 1;

  nNumOfElements 这个成员保存了hashtable中保存的元素的个数,通常情况下,我们在PHP脚本中使用count($arr)与这个结果是一致的(参见ext/standard/array.c)

  nNextFreeElement 这个字段记录下一个可用的索引位置,我们在脚本中使用$array[] = ‘key’的时候,就是使用nNextFreeElement给出的索引值(zend_hash.c):

  1. if (flag & HASH_NEXT_INSERT) {
  2. h = ht->nNextFreeElement;
  3. }

  pInternalPointer 这是一个指针。在PHP脚本中,我们使用current,next,key,end等 与数组相关的操作时,都是使用pInternalPointer这一指针来完成的。

   pListHead 和pListTail PHP底层实际上维护了两个重要的数据结构,除了hash表(以及用于解决冲突的双链表),还有一个双向链表用于hash表元素的线性扫描。pListHead和pListTail便指向这个双链表的表头和表尾。

  arBuckets 这是一个bucket 类型的数组,数组中每个元素都是一个bucket 的指针,具有相同hash值的元素通过bucket的pNext和pLast指针连接成一个双链表(这个双链表与前面说的用于线性遍历的双链表并不是一个东西)。因此,bucket是实际存储数据的容器。

nApplyCount和bApplyProtection 提供了一种保护机制,主要是用于防止循环引用导致的无限递归。

  persistent 这是一个布尔变量,该变量会影响到内存分配的方式,这涉及到PHP内存管理的一些知识,我们暂时不做更多解释,详细的可以参考:http://cn2.php.net/manual/en/internals2.memory.persistence.php

(2)另一个数据结构是Bucket

该结构的定义为:

  1. typedef struct bucket {
  2. ulong h;
  3. uint nKeyLength;
  4. void *pData;
  5. void *pDataPtr;
  6. struct bucket *pListNext;
  7. struct bucket *pListLast;
  8. struct bucket *pNext;
  9. struct bucket *pLast;
  10. const char *arKey;
  11. } Bucket;

其中:

   h ,arKey,nKeyLength PHP数组中,有两类不同的索引,一类是数字索引,这与C中的数组非常类似(如$arr = array(1=>’cont’)), 另一类是字符串索引,也就是使用关键词作为数组项的索引(如$arr = array(‘index’=>’cont’);).这两类索引在PHP底层是通过不同的机制来区分的:对于数字型索引,直接使用h作为hash 值,同时,arKey=NULL 且nKeyLength=0, 而对于字符串索引,arKey保存字符串key, nKeyLength保存该key的长度,h则是该字符串通过hash函数计算后的hash值。这样,在PHP中,实际上通过h, arKey, nKeyLength来唯一确定数组中的一个元素的,这从zend_hash_key这个结构体的定义也可以看出来:

  1. typedef struct _zend_hash_key {
  2. const char *arKey;
  3. uint nKeyLength;
  4. ulong h;
  5. } zend_hash_key;

而确定数组元素在hashtable中的位置则是通过h & ht->nTableMask 来实现的:

  1. /* 字符串型索引 */
  2. h = zend_inline_hash_func(arKey, nKeyLength);
  3. nIndex = h & ht->nTableMask;
  4. /* 数字型索引-append $arr[] = 'test';这种形式 */
  5. if (flag & HASH_NEXT_INSERT) {
  6. h = ht->nNextFreeElement;
  7. }
  8. /* 指定数字索引时直接使用h */
  9. nIndex = h & ht->nTableMask;

   pData和pDataPtr 通常情况下,Bucket中的数据是保存在pData指针指向的内存空间的。但是也有例外,例如保存的是一个指针。这时,pDataPtr指向该指针,而pData指向pDataPtr。这从INIT_DATA这个宏定义可以看出来:

  1. #define INIT_DATA(ht, p, pData, nDataSize);
  2. if (nDataSize == sizeof(void*)) {
  3. memcpy(&(p)->pDataPtr, pData, sizeof(void *));
  4. (p)->pData=&(p)->pDataPtr;
  5. }else{
  6. (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
  7. if(!(p)->pData){
  8. pefree_rel(p, (ht)->persistent);
  9. return FAILURE;
  10. }
  11. memcpy((p)->pData,pData,nDataSize);
  12. (p)->pDataPtr=NULL;
  13. }

   pListNext和pListLast,pNext和pLast 前面已经介绍过,pListNext和pListLast构成了用于遍历的整个双链表。而pNext和pLast则是在出现hash冲突时,用于链接具有 相同hash值的Bucket。

三、HashTable的实现

1. HashTable相关宏定义

为了方便操作HashTable, PHP底层定义了很多的宏,这些宏包括:

(1). CONNECT_TO_BUCKET_DLLIST(element, list_head)

该宏用于把元素插入Bucket的双链表的头部,也就是说,在发生冲突时,新插入的元素总是位于Bucket链表的头部。该宏的定义为:

  1. #define CONNECT_TO_BUCKET_DLLIST(element, list_head)
  2. (element)->pNext = (list_head);
  3. (element)->pLast = NULL;
  4. if ((element)->pNext) {
  5. (element)->pNext->pLast = (element);
  6. }

(2). CONNECT_TO_GLOBAL_DLLIST(element, ht)

   与上述不同,这个是将元素插入到全局遍历的双链表的末尾,这个双链表类似队列的作用,它保证了我们遍历数组时的正确顺序。该宏的定义是:

  1. 1 #define CONNECT_TO_GLOBAL_DLLIST(element, ht)
  2. 2 (element)->pListLast = (ht)->pListTail;
  3. 3 (ht)->pListTail = (element);
  4. 4 (element)->pListNext = NULL;
  5. 5 if ((element)->pListLast != NULL) {
  6. 6 (element)->pListLast->pListNext = (element);
  7. 7 }
  8. 8
  9. 9 if (!(ht)->pListHead) {
  10. 10 (ht)->pListHead = (element);
  11. 11 }
  12. 12
  13. 13 if ((ht)->pInternalPointer == NULL) {
  14. 14 (ht)->pInternalPointer = (element);
  15. 15 }

(3). HASH_PROTECT_RECURSION(ht)

这个宏主要用于防止HashTable被递归遍历时深度过大,是一种保护机制

  1. #define HASH_PROTECT_RECURSION(ht)
  2. if ((ht)->bApplyProtection) {
  3. if ((ht)->nApplyCount++ >= 3) {
  4. zend_error(E_ERROR, Nesting level too deep - recursive dependency?);
  5. }
  6. }

(4). ZEND_HASH_IF_FULL_DO_RESIZE(ht)

  HashTable的大小并不是固定不变的,当nNumOfElements > nTableSize时,会对HashTable进行扩容,以便于容纳更多的元素,这便是通过该宏实现的(实际上是调用 zend_hash_do_resize来实现的)。该宏定义为:

  1. #define ZEND_HASH_IF_FULL_DO_RESIZE(ht)
  2. if ((ht)->nNumOfElements > (ht)->nTableSize) {
  3. zend_hash_do_resize(ht);
  4. }

(5). INIT_DATA(ht, p, pData, nDataSize)

这里实际上有两种情况,如果要保存的数据本身是一个指针,则pDataPtr保存该指针,并且将pData指向pDataPtr的地址:

  1. if (nDataSize == sizeof(void*)) {
  2. memcpy(&(p)->pDataPtr, pData, sizeof(void *));
  3. (p)->pData = &(p)->pDataPtr;
  4. }

  否者保存的是普通的数据,则申请分配nDataSize字节的内存,并将pData指向内存的内容复制到p->pData的内存。这里,复制都是通过memcpy来进行的,因为它的src和dest的指针都是void *的,因此可以复制几乎任何类型的数据:

  1. else {
  2. (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
  3. if (!(p)->pData) {
  4. pefree_rel(p, (ht)->persistent);
  5. return FAILURE;
  6. }
  7. memcpy((p)->pData, pData, nDataSize);
  8. (p)->pDataPtr=NULL;
  9. }

整个宏定义为:

  1. #define UPDATE_DATA(ht, p, pData, nDataSize)
  2. if (nDataSize == sizeof(void*)) {
  3. if ((p)->pData != &(p)->pDataPtr) {
  4. pefree_rel((p)->pData, (ht)->persistent);
  5. }
  6. memcpy(&(p)->pDataPtr, pData, sizeof(void *));
  7. (p)->pData = &(p)->pDataPtr;
  8. } else {
  9. if ((p)->pData == &(p)->pDataPtr) {
  10. (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
  11. (p)->pDataPtr=NULL;
  12. } else {
  13. (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent);
  14. /* (p)->pDataPtr is already NULL so no need to initialize it */
  15. }
  16. memcpy((p)->pData, pData, nDataSize);
  17. }

(6). UPDATE_DATA(ht, p, pData, nDataSize)

  与INIT_DATA类似,不同的是,需要对之前的内存块做更多的处理(例如之前pData保存的实际的数据,但是update之后保存的是指针, 则需要释放原来申请的内存,否者就会造成内存泄露,相反,如果之前保存的是指针数据,update之后保存的是普通的数据,则pDataPtr要设置为 NULL,同时为pData分配新的内存空间),该宏的定义为:

  1. #define UPDATE_DATA(ht, p, pData, nDataSize)
  2. if (nDataSize == sizeof(void*)) {
  3. if ((p)->pData != &(p)->pDataPtr) {
  4. pefree_rel((p)->pData, (ht)->persistent);
  5. }
  6. memcpy(&(p)->pDataPtr, pData, sizeof(void *));
  7. (p)->pData = &(p)->pDataPtr;
  8. } else {
  9. if ((p)->pData == &(p)->pDataPtr) {
  10. (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
  11. (p)->pDataPtr=NULL;
  12. } else {
  13. (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent);
  14. /* (p)->pDataPtr is already NULL so no need to initialize it */
  15. }
  16. memcpy((p)->pData, pData, nDataSize);
  17. }

(7). CHECK_INIT(ht)

  在调用_zend_hash_init()为hash table初始化之后,实际上arBuckets并没有分配内存空间,且没有设置nTableMask的值。CHECK_INIT会检查 arBuckets是否已经初始化(nTableMask==0表示未初始化),如果没有初始化,则要为arBuckets分配内存空间,同时设置 nTableMask的值为nTableSize – 1.该宏定义为:

  1. #define CHECK_INIT(ht) do {
  2. if (UNEXPECTED((ht)->nTableMask == 0)) {
  3. (ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent);
  4. (ht)->nTableMask = (ht)->nTableSize - 1;
  5. }
  6. } while (0)

2. 哈希函数

   写这篇文章的时候,发现鸟哥已经写了一篇《PHP中的hash算法》,里边对hash的算法、思想等都做了比较详细的解答,这里就不在做过多的解 释,只说一点:unrolled。unrolled本身是展开的意思,对于nKeyLength长度的key, PHP的hash算法会以8为单位做unrolled,也就是这样的形式:

  1. for (; nKeyLength >= 8; nKeyLength -= 8) {
  2. hash = ((hash << 5) + hash) + *arKey++;
  3. hash = ((hash << 5) + hash) + *arKey++;
  4. hash = ((hash << 5) + hash) + *arKey++;
  5. hash = ((hash << 5) + hash) + *arKey++;
  6. hash = ((hash << 5) + hash) + *arKey++;
  7. hash = ((hash << 5) + hash) + *arKey++;
  8. hash = ((hash << 5) + hash) + *arKey++;
  9. hash = ((hash << 5) + hash) + *arKey++;
  10. }

那为什么不直接用循环呢?比如说:

  1. for(;nKeyLength > 0; nKeyLength--)
  2. {
  3. hash = ((hash << 5) + hash) + *arKey++;
  4. }

  这样其实是没有问题的,而unroll的原因自然是效率更高:对CPU而言,一般顺序执行的指令比循环要快(后者在汇编指令中表现为JMP, JNZ等跳转,以及循环之前的比较)。同时,对于8位以下的字符串索引,会有更好的效率。

  1. /*
  2. * 1. inline static 是为了提高效率
  3. * 2. const限定arKey, 表明在函数中arKey的内容不应该不修改
  4. */
  5. static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
  6. {
  7. /* 3.register变量,也是为了提高效率 */
  8. register ulong hash = 5381;
  9. /* 4. variant with the hash unrolled eight times */
  10. for (; nKeyLength >= 8; nKeyLength -= 8) {
  11. hash = ((hash << 5) + hash) + *arKey++;
  12. hash = ((hash << 5) + hash) + *arKey++;
  13. hash = ((hash << 5) + hash) + *arKey++;
  14. hash = ((hash << 5) + hash) + *arKey++;
  15. hash = ((hash << 5) + hash) + *arKey++;
  16. hash = ((hash << 5) + hash) + *arKey++;
  17. hash = ((hash << 5) + hash) + *arKey++;
  18. hash = ((hash << 5) + hash) + *arKey++;
  19. }
  20. switch (nKeyLength) {
  21. case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
  22. case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
  23. case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
  24. case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
  25. case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
  26. case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
  27. case 1: hash = ((hash << 5) + hash) + *arKey++; break;
  28. case 0: break;
  29. EMPTY_SWITCH_DEFAULT_CASE()
  30. }
  31. /* 5. 返回的hash值并没有经过取模运算 */
  32. return hash;
  33. }
  1. 初始化、添加/更新和查找、删除等API

(1). 初始化

  _zend_hash_init用于hash table的初始化操作(主要包括对hashTable这个结构体的数据成员赋初值)。调用_zend_hash_init之后,nTableMask默 认为0(之后再CHECK_INIT时被赋值为nTableSize-1), nTableSize被赋值为大于nSize的最小的2的整数次方,并且nTableSize最小为8,最大为0x80000000,且在 _zend_hash_init之后,arBuckets是没有分配内存空间的(也是在CHECK_INIT时分配的)。nTableMask用于快速计 算hash值对应的索引,因为它有一个特性,即nTableMask = 2^n – 1,展开成二进制之后,所有位都是1,因而通过nIndex = h & nTableMask可以快速得到索引位置。该函数的实现源码(不同版本的具体实现有不同,本文的PHP版本是5.4.24):

  1. 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)
  2. {
  3. /* hashTable最小size为 1<<3 = 8 */
  4. uint i = 3;
  5. SET_INCONSISTENT(HT_OK);
  6. if (nSize >= 0x80000000) {
  7. /* prevent overflow */
  8. ht->nTableSize = 0x80000000;
  9. } else {
  10. while ((1U << i) < nSize) {
  11. i++;
  12. }
  13. ht->nTableSize = 1 << i;
  14. }
  15. ht->nTableMask = 0; /* 0 means that ht->arBuckets is uninitialized */
  16. ht->pDestructor = pDestructor;
  17. ht->arBuckets = (Bucket**)&uninitialized_bucket;
  18. ht->pListHead = NULL;
  19. ht->pListTail = NULL;
  20. ht->nNumOfElements = 0;
  21. ht->nNextFreeElement = 0;
  22. ht->pInternalPointer = NULL;
  23. ht->persistent = persistent;
  24. ht->nApplyCount = 0;
  25. ht->bApplyProtection = 1;
  26. return SUCCESS;
  27. }

(2). 查找元素。

  对于字符串索引和数字索引,分别提供了zend_hash_find和zend_hash_index_find两种查找方式。这两种方式并没有本 质的不同,都是在计算hash值之后,寻找元素在对应Bucket中的位置。对字符串索引,确定相同的条件是:p->arKey == arKey ||((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength)),即要么arKey和p->arKey指向的同一块内存,要么h,nKeyLength和arKey指向的内容完全一致, 才能确定为相同。而对于数字型索引,只需要(p->h == h) && (p->nKeyLength == 0)即可。这两种查找的实现如下:

  1. /* 数字型索引的查找 */
  2. ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
  3. {
  4. uint nIndex;
  5. Bucket *p;
  6. IS_CONSISTENT(ht);
  7. /* 计算索引 */
  8. nIndex = h & ht->nTableMask;
  9. p = ht->arBuckets[nIndex];
  10. /* 遍历双链表,一旦找到立即返回 */
  11. while (p != NULL) {
  12. if ((p->h == h) && (p->nKeyLength == 0)) {
  13. *pData = p->pData;
  14. return SUCCESS;
  15. }
  16. p = p->pNext;
  17. }
  18. /* 如果遍历完双链表,没有找到,那么查找失败 */
  19. return FAILURE;
  20. }
  21. /* 字符串索引的查找 */
  22. ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
  23. {
  24. ulong h;
  25. uint nIndex;
  26. Bucket *p;
  27. IS_CONSISTENT(ht);
  28. /* 字符串索引需要先计算字符串的hash值 */
  29. h = zend_inline_hash_func(arKey, nKeyLength);
  30. nIndex = h & ht->nTableMask;
  31. p = ht->arBuckets[nIndex];
  32. /* Bucket双链表中查找,一旦找到,立即返回,注意查找成功的条件 */
  33. while (p != NULL) {
  34. if (p->arKey == arKey ||
  35. ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
  36. *pData = p->pData;
  37. return SUCCESS;
  38. }
  39. p = p->pNext;
  40. }
  41. /* 查找失败 */
  42. return FAILURE;
  43. }

(3).插入元素

在PHP脚本中,有三种形式可以在当前数组中插入元素,如:

  1. $arr = array();
  2. $arr['index'] = 'cont';
  3. $arr[2] = 'test';
  4. $arr[] = 10;

  这三种插入方式分别是:字符串索引插入,数字索引插入,下一个可用位置插入,在实现中,字符串索引插入对应 _zend_hash_add_or_update,而后两种对应_zend_hash_index_update_or_next_insert. 以$arr[‘index’] = ‘cont’这个操作为例,PHP会尝试先update相应的数据,如果没有找到对应的Bucket,则表示这是一个新增的元素,因而会执行insert 操作,这在_zend_hash_add_or_update中实现如下(省略非关键步骤):ZEN

注意:
本文非原创内容,为了尊重他人劳动,转载请到文章原文地址,非常感谢:
https://www.cnblogs.com/ohmygirl/p/internal-3.html

上一篇: 我在北京你在哪

评论列表

暂无评论

添加评论

* (邮箱不会公开,只会做回复通知用)

* (好的站点我会把它添加到友情链接

* (需要您帮忙,确定您是真实的访客)

*

提交评论