PHP カーネルで探索される変数 (3) - ハッシュ テーブル
PHP では、zval に加えて、もう 1 つの重要なデータ構造が、たとえば、最も一般的な配列は一番下にあります。ハッシュテーブル。配列に加えて、スレッド セーフ (TSRM)、GC、リソース管理、グローバル変数、および ini 構成管理にもハッシュ テーブルの痕跡がほとんどあります (シンボル テーブルもハッシュ テーブルを使用して実装されていることも前回触れました)。では、PHP におけるこの種のデータの何が特別で、その構造はどのように実装されているのでしょうか? これらの質問をもとに、カーネル探索の旅を始めます。
この記事の主な内容:
1. 基本定義
ハッシュ テーブル、ハッシュ テーブル、ハッシュ テーブル、ハッシュ テーブルとも呼ばれ、Wikipedia ではハッシュ テーブルの定義が:"ハッシュ テーブルは、キーワード (キー値) に基づいてメモリの保存場所に直接アクセスするデータ構造です。つまり、関数の計算によってキー値をテーブル内の位置にマッピングすることでレコードにアクセスします。このマッピング関数はハッシュ関数と呼ばれ、レコードを格納する配列はハッシュと呼ばれます。テーブル」。記事のバックボーンを抽出すると、次の情報が得られます:
(1) ハッシュ テーブルはデータ構造です。
(2) このデータ構造は、通常の配列の拡張です。
(3)。このデータ構造により、キーと値のマッピング関係によって挿入と検索が効率化されます (配列は直接アドレス指定でき、O(1 ) で処理してアクセスできます)。任意の要素）。
一般的な配列、線形テーブル、およびツリーでは、構造内のレコードの位置が比較的ランダムである、つまり、レコードとキーワードの間に直接的かつ明確な対応関係がないことがわかっています。これらの構造では、キーワードを検索して挿入するために一連の比較が必要になることが多く、検索効率は通常 O(n) または O(lgn) です。ハッシュ テーブルは、ハッシュ関数によってキーワードとレコードの対応関係を確立するため、通常の検索と挿入操作を O(1) (平均時間計算量) の時間で完了できます。これは明らかに最も理想的な検索方法です。2. ハッシュ関数
前述のように、ハッシュ関数はキーワードとレコードの間に対応関係を確立します。つまり、レコード = ハッシュです。 (key)、この対応は次のとおりです:
function hash( $key ){ $result = 0; $len = strlen($key); for($i = 0;$i < $len; $i++ ){ $result += ord($key{$i}) * ((1 << 5) + 1); } return $result;}3. 競合の解決
理想的な状況では次に、キーワードによって計算されたハッシュ値が一意であることが期待されるため、Hash(key) を通じて探しているレコードを直接見つけることができます。しかし、残念ながら、このような特性を満たすハッシュ関数はほとんど存在しません（たとえあったとしても、複雑すぎて実用に耐えない可能性があります）。つまり、適切に設計されたハッシュ関数であっても、 key1 != key2 であるが、 hash(key1) = hash(key2) となることがよくあります。これは、ハッシュの衝突 (ハッシュの衝突) です。ハッシュの衝突を解決するための主な方法は多数あります (ここを参照) 例として、競合を解決するためのチェーン方法について簡単に説明します。この方法の基本的な考え方は、ハッシュ テーブルで競合が発生した場合、同じハッシュ値を持つすべてのレコードがリンク リストの形式でリンクされ、リンク リストの先頭ポインタのみがハッシュに格納されます。テーブル。 PHP の基礎となるハッシュ テーブルは、リンク リスト (二重リンク リスト) を使用してハッシュの競合を解決します。これについては、後ほど詳しくご紹介します。 リンク リストの導入後のハッシュ テーブルの構造は次のとおりです。
我们知道，在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）：
<span style="color: #000000;">typedef struct _hashtable { uint nTableSize; uint nTableMask; uint nNumOfElements; ulong nNextFreeElement; Bucket </span>*pInternalPointer; <span style="color: #008000;">/*</span><span style="color: #008000;"> Used for element traversal </span><span style="color: #008000;">*/</span><span style="color: #000000;"> Bucket </span>*<span style="color: #000000;">pListHead; Bucket </span>*<span style="color: #000000;">pListTail; Bucket </span>**<span style="color: #000000;">arBuckets; dtor_func_t pDestructor; zend_bool persistent; unsigned char nApplyCount; zend_bool bApplyProtection;</span><span style="color: #008000;">#</span><span style="color: #008000;">if ZEND_DEBUG</span><span style="color: #000000;"> int inconsistent;</span><span style="color: #008000;">#</span><span style="color: #008000;">endif</span>} 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）：
<span style="color: #0000ff;">if</span> (flag &<span style="color: #000000;"> HASH_NEXT_INSERT) { h </span>= ht-><span style="color: #000000;">nNextFreeElement;}</span>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
该结构的定义为：
<span style="color: #000000;">typedef struct bucket { ulong h; uint nKeyLength; void </span>*<span style="color: #000000;">pData; void </span>*<span style="color: #000000;">pDataPtr; struct bucket </span>*<span style="color: #000000;">pListNext; struct bucket </span>*<span style="color: #000000;">pListLast; struct bucket </span>*<span style="color: #000000;">pNext; struct bucket </span>*<span style="color: #000000;">pLast; </span><span style="color: #0000ff;">const</span> char *<span style="color: #000000;">arKey;} Bucket;</span>其中：
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这个结构体的定义也可以看出来：
<span style="color: #000000;">typedef struct _zend_hash_key { </span><span style="color: #0000ff;">const</span> char *<span style="color: #000000;">arKey; uint nKeyLength; ulong h;} zend_hash_key;</span>而确定数组元素在hashtable中的位置则是通过h & ht->nTableMask 来实现的：
/* 字符串型索引 */h = zend_inline_hash_func(arKey, nKeyLength);nIndex = h & ht->nTableMask; /* 数字型索引-append $arr[] = 'test';这种形式 */if (flag & HASH_NEXT_INSERT) { h = ht->nNextFreeElement;}/* 指定数字索引时直接使用h */nIndex = h & ht->nTableMask;pData和pDataPtr 通常情况下，Bucket中的数据是保存在pData指针指向的内存空间的。但是也有例外，例如保存的是一个指针。这时，pDataPtr指向该指针，而pData指向pDataPtr。这从INIT_DATA这个宏定义可以看出来：
#define INIT_DATA(ht, p, pData, nDataSize); \ if (nDataSize == sizeof(void*)) { \ memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \ (p)->pData=&(p)->pDataPtr; \ }else{ \ (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\ if(!(p)->pData){ \ pefree_rel(p, (ht)->persistent); \ return FAILURE; \ } \ memcpy((p)->pData,pData,nDataSize); \ (p)->pDataPtr=NULL; \ }pListNext和pListLast，pNext和pLast 前面已经介绍过,pListNext和pListLast构成了用于遍历的整个双链表。而pNext和pLast则是在出现hash冲突时，用于链接具有相同hash值的Bucket。这两种双链表的结构分别如下图所示：
a. 发生hash冲突时的双链表：
b. 用于全局的双链表：
需要注意的是，这两种双链表结构并不是单独存在，而是相互关联的。在HashTable的相关操作中，需要同时维护这两种链表：
可以看出，PHP的hashTable相当复杂，正是这种复杂性，使得PHP的数组操作有很大的灵活性（PHP中数组可以用作数组、栈、队列，可以说非常便利）
1. HashTable相关宏定义
为了方便操作HashTable, PHP底层定义了很多的宏，这些宏包括：
(1). CONNECT_TO_BUCKET_DLLIST(element, list_head)
该宏用于把元素插入Bucket的双链表的头部，也就是说，在发生冲突时，新插入的元素总是位于Bucket链表的头部。该宏的定义为：
<span style="color: #0000ff;">#define</span> CONNECT_TO_BUCKET_DLLIST(element, list_head) \<span style="color: #000000;"> (element)</span>->pNext =<span style="color: #000000;"> (list_head); \ (element)</span>->pLast =<span style="color: #000000;"> NULL; \ </span><span style="color: #0000ff;">if</span> ((element)-><span style="color: #000000;">pNext) { \ (element)</span>->pNext->pLast =<span style="color: #000000;"> (element); \ }</span>(2). CONNECT_TO_GLOBAL_DLLIST(element, ht)
与上述不同，这个是将元素插入到全局遍历的双链表的末尾，这个双链表类似队列的作用，它保证了我们遍历数组时的正确顺序。该宏的定义是：
<span style="color: #008080;"> 1</span> <span style="color: #0000ff;">#define</span> CONNECT_TO_GLOBAL_DLLIST(element, ht) \<span style="color: #008080;"> 2</span> (element)->pListLast = (ht)-><span style="color: #000000;">pListTail; \</span><span style="color: #008080;"> 3</span> (ht)->pListTail =<span style="color: #000000;"> (element); \</span><span style="color: #008080;"> 4</span> (element)->pListNext =<span style="color: #000000;"> NULL; \</span><span style="color: #008080;"> 5</span> <span style="color: #0000ff;">if</span> ((element)->pListLast !=<span style="color: #000000;"> NULL) { \</span><span style="color: #008080;"> 6</span> (element)->pListLast->pListNext =<span style="color: #000000;"> (element); \</span><span style="color: #008080;"> 7</span> <span style="color: #000000;"> } \</span><span style="color: #008080;"> 8</span> <span style="color: #008080;"> 9</span> <span style="color: #0000ff;">if</span> (!(ht)-><span style="color: #000000;">pListHead) { \</span><span style="color: #008080;">10</span> (ht)->pListHead =<span style="color: #000000;"> (element); \</span><span style="color: #008080;">11</span> <span style="color: #000000;"> } \</span><span style="color: #008080;">12</span> <span style="color: #008080;">13</span> <span style="color: #0000ff;">if</span> ((ht)->pInternalPointer ==<span style="color: #000000;"> NULL) { \</span><span style="color: #008080;">14</span> (ht)->pInternalPointer =<span style="color: #000000;"> (element); \</span><span style="color: #008080;">15</span> }(3). HASH_PROTECT_RECURSION(ht)
这个宏主要用于防止HashTable被递归遍历时深度过大，是一种保护机制
<span style="color: #0000ff;">#define</span> HASH_PROTECT_RECURSION(ht) \ <span style="color: #0000ff;">if</span> ((ht)-><span style="color: #000000;">bApplyProtection) { \ </span><span style="color: #0000ff;">if</span> ((ht)->nApplyCount++ >= <span style="color: #800080;">3</span><span style="color: #000000;">) { \ zend_error(E_ERROR, </span><span style="color: #800000;">"</span><span style="color: #800000;">Nesting level too deep - recursive dependency?</span><span style="color: #800000;">"</span><span style="color: #000000;">);\ } \ }</span>(4). ZEND_HASH_IF_FULL_DO_RESIZE(ht)
HashTable的大小并不是固定不变的，当nNumOfElements > nTableSize时，会对HashTable进行扩容，以便于容纳更多的元素，这便是通过该宏实现的（实际上是调用zend_hash_do_resize来实现的）。该宏定义为：
<span style="color: #0000ff;">#define</span> ZEND_HASH_IF_FULL_DO_RESIZE(ht) \ <span style="color: #0000ff;">if</span> ((ht)->nNumOfElements > (ht)-><span style="color: #000000;">nTableSize) { \ zend_hash_do_resize(ht); \ }</span>(5). INIT_DATA(ht, p, pData, nDataSize)
这里实际上有两种情况，如果要保存的数据本身是一个指针，则pDataPtr保存该指针，并且将pData指向pDataPtr的地址：
if (nDataSize == sizeof(void*)) { memcpy(&(p)->pDataPtr, pData, sizeof(void *)); (p)->pData = &(p)->pDataPtr;}否者保存的是普通的数据，则申请分配nDataSize字节的内存，并将pData指向内存的内容复制到p->pData的内存。这里，复制都是通过memcpy来进行的，因为它的src和dest的指针都是void *的，因此可以复制几乎任何类型的数据：
else { (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent); if (!(p)->pData) { pefree_rel(p, (ht)->persistent); return FAILURE; } memcpy((p)->pData, pData, nDataSize); (p)->pDataPtr=NULL;}整个宏定义为：
<span style="color: #0000ff;">#define</span> UPDATE_DATA(ht, p, pData, nDataSize) \ <span style="color: #0000ff;">if</span> (nDataSize == <span style="color: #0000ff;">sizeof</span>(<span style="color: #0000ff;">void</span>*<span style="color: #000000;">)) { \ </span><span style="color: #0000ff;">if</span> ((p)->pData != &(p)-><span style="color: #000000;">pDataPtr) { \ pefree_rel((p)</span>->pData, (ht)-><span style="color: #000000;">persistent); \ } \ memcpy(</span>&(p)->pDataPtr, pData, <span style="color: #0000ff;">sizeof</span>(<span style="color: #0000ff;">void</span> *<span style="color: #000000;">)); \ (p)</span>->pData = &(p)-><span style="color: #000000;">pDataPtr; \ } </span><span style="color: #0000ff;">else</span><span style="color: #000000;"> { \ </span><span style="color: #0000ff;">if</span> ((p)->pData == &(p)-><span style="color: #000000;">pDataPtr) { \ (p)</span>->pData = (<span style="color: #0000ff;">void</span> *) pemalloc_rel(nDataSize, (ht)-><span style="color: #000000;">persistent); \ (p)</span>->pDataPtr=<span style="color: #000000;">NULL; \ } </span><span style="color: #0000ff;">else</span><span style="color: #000000;"> { \ (p)</span>->pData = (<span style="color: #0000ff;">void</span> *) perealloc_rel((p)->pData, nDataSize, (ht)-><span style="color: #000000;">persistent);\ </span><span style="color: #008000;">/*</span><span style="color: #008000;"> (p)->pDataPtr is already NULL so no need to initialize it </span><span style="color: #008000;">*/</span><span style="color: #000000;"> \ } \ memcpy((p)</span>-><span style="color: #000000;">pData, pData, nDataSize); \ }</span>(6). UPDATE_DATA(ht, p, pData, nDataSize)
与INIT_DATA类似，不同的是，需要对之前的内存块做更多的处理（例如之前pData保存的实际的数据，但是update之后保存的是指针，则需要释放原来申请的内存，否者就会造成内存泄露，相反，如果之前保存的是指针数据，update之后保存的是普通的数据，则pDataPtr要设置为NULL，同时为pData分配新的内存空间），该宏的定义为：
#define UPDATE_DATA(ht, p, pData, nDataSize) \ if (nDataSize == sizeof(void*)) { \ if ((p)->pData != &(p)->pDataPtr) { \ pefree_rel((p)->pData, (ht)->persistent); \ } \ memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \ (p)->pData = &(p)->pDataPtr; \ } else { \ if ((p)->pData == &(p)->pDataPtr) { \ (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent); \ (p)->pDataPtr=NULL; \ } else { \ (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent); \ /* (p)->pDataPtr is already NULL so no need to initialize it */ \ } \ memcpy((p)->pData, pData, nDataSize); \ }(7). CHECK_INIT(ht)
在调用_zend_hash_init()为hash table初始化之后，实际上arBuckets并没有分配内存空间，且没有设置nTableMask的值。CHECK_INIT会检查arBuckets是否已经初始化（nTableMask==0表示未初始化），如果没有初始化，则要为arBuckets分配内存空间，同时设置nTableMask的值为nTableSize – 1.该宏定义为：
<span style="color: #0000ff;">#define</span> CHECK_INIT(ht) do { \ <span style="color: #0000ff;">if</span> (UNEXPECTED((ht)->nTableMask == <span style="color: #800080;">0</span><span style="color: #000000;">)) { \ (ht)</span>->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, <span style="color: #0000ff;">sizeof</span>(Bucket *), (ht)-><span style="color: #000000;">persistent); \ (ht)</span>->nTableMask = (ht)->nTableSize - <span style="color: #800080;">1</span><span style="color: #000000;">; \ } \} </span><span style="color: #0000ff;">while</span> (<span style="color: #800080;">0</span>)2. 哈希函数
写这篇文章的时候，发现鸟哥已经写了一篇《PHP中的hash算法》，里边对hash的算法、思想等都做了比较详细的解答，这里就不在做过多的解释，只说一点：unrolled。unrolled本身是展开的意思，对于nKeyLength长度的key, PHP的hash算法会以8为单位做unrolled，也就是这样的形式：
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++;}那为什么不直接用循环呢？
比如说：
for(;nKeyLength > 0; nKeyLength--){ hash = ((hash << 5) + hash) + *arKey++;}这样其实是没有问题的，而unroll的原因自然是效率更高:对CPU而言，一般顺序执行的指令比循环要快（后者在汇编指令中表现为JMP, JNZ等跳转，以及循环之前的比较）。同时，对于8位以下的字符串索引，会有更好的效率。
顺便贴出hash函数的实现源码：
/* * 1. inline static 是为了提高效率 * 2. const限定arKey, 表明在函数中arKey的内容不应该不修改 */static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength){ /* 3.register变量，也是为了提高效率 */ register ulong hash = 5381; /* 4. 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() } /* 5. 返回的hash值并没有经过取模运算 */ return hash;}3. 初始化、添加/更新和查找、删除等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)：
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){ /* hashTable最小size为 1<<3 = 8 */ uint i = 3; SET_INCONSISTENT(HT_OK); if (nSize >= 0x80000000) { /* prevent overflow */ ht->nTableSize = 0x80000000; } else { 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; 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). 查找元素。
对于字符串索引和数字索引，分别提供了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)即可。这两种查找的实现如下：
/* 数字型索引的查找 */ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData){ uint nIndex; Bucket *p; IS_CONSISTENT(ht); /* 计算索引 */ nIndex = h & ht->nTableMask; p = ht->arBuckets[nIndex]; /* 遍历双链表，一旦找到立即返回 */ while (p != NULL) { if ((p->h == h) && (p->nKeyLength == 0)) { *pData = p->pData; return SUCCESS; } p = p->pNext; } /* 如果遍历完双链表，没有找到，那么查找失败 */ return FAILURE;}<br />/* 字符串索引的查找 */ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData){ ulong h; uint nIndex; Bucket *p; IS_CONSISTENT(ht); /* 字符串索引需要先计算字符串的hash值 */ h = zend_inline_hash_func(arKey, nKeyLength); nIndex = h & ht->nTableMask; p = ht->arBuckets[nIndex]; /* Bucket双链表中查找，一旦找到，立即返回，注意查找成功的条件 */ while (p != NULL) { if (p->arKey == arKey || ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) { *pData = p->pData; return SUCCESS; } p = p->pNext; } /* 查找失败 */ return FAILURE;}(3).插入元素
在PHP脚本中，有三种形式可以在当前数组中插入元素，如：
$arr = array();$arr['index'] = 'cont';$arr[2] = 'test';$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中实现如下（省略非关键步骤）：
ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pD est, int flag ZEND_FILE_LINE_DC){ /* 由于是字符串索引，索引key不能为空，nKeyLength必须>0 */ if (nKeyLength <= 0) { return FAILURE; } /* ht是否初始化，如果没有，分配arBuckets的内存空间，设置nTableMask */ CHECK_INIT(ht); /* 计算在hash表中的索引 */ h = zend_inline_hash_func(arKey, nKeyLength); nIndex = h & ht->nTableMask; /* 扫描Bucket列表，看元素是否存在，如果存在，则更新之，并返回 */ p = ht->arBuckets[nIndex]; while (p != NULL) { if (p->arKey == arKey || ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) { /* 冲突，不能添加 */ if (flag & HASH_ADD) { return FAILURE; } HANDLE_BLOCK_INTERRUPTIONS(); if (ht->pDestructor) { ht->pDestructor(p->pData); } /* 进行更新的操作 */ UPDATE_DATA(ht, p, pData, nDataSize); if (pDest) { *pDest = p->pData; } HANDLE_UNBLOCK_INTERRUPTIONS(); return SUCCESS; } p = p->pNext; } /* 不存在元素，则insert */ if (IS_INTERNED(arKey)) { p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent); if (!p) { return FAILURE; } p->arKey = arKey; } else { p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent); if (!p) { return FAILURE; } p->arKey = (const char*)(p + 1); memcpy((char*)p->arKey, arKey, nKeyLength); } p->nKeyLength = nKeyLength; INIT_DATA(ht, p, pData, nDataSize); p->h = h; /* 插入到Buckets链表的头部 */ CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); /* 插入到全局的双链表，用于遍历，是个逻辑队列 */ CONNECT_TO_GLOBAL_DLLIST(p, ht); ht->arBuckets[nIndex] = p; /* 增加元素个数 */ ht->nNumOfElements++; /* 如果nNumOfElements > nTableSize，则需要对HashTable扩容 */ ZEND_HASH_IF_FULL_DO_RESIZE(ht); } zend_hash_do_resize (拡張)、zend_hash_rehash (拡張後に元の hashTable の要素を再ハッシュする必要がある)、zend_hash_del_key_or_index (HashTable 内の要素を削除)、zend_hash_destroy (ハッシュ テーブルを破棄)、zend_hash_copy などの HashTable のその他の操作(ハッシュ テーブルのコピー)、ここでは 1 つずつ列挙しません。興味のある学生はソース コードを確認してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
