在PHP中，除了zval, 另一個比較重要的數據結構非hash table莫屬，例如我們最常見的數組，在底層便是hash table。除了數組，在線程安全（TSRM）、GC、資源管理、Global變量、ini配置管理中，幾乎都有Hash table的蹤跡（上一次我們也提到，符號表也是使用Hash table實現的）。那麼，在PHP中，這種數據有什麼特殊之處，結構是怎麼實現的？ 帶著這些問題，我們開始本次的內核探索之旅。
本文主要內容：
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算法如下：
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值都是唯一的，這樣我們便可以通過Hash(key)這種方式直接定位到要查找的記錄。但不幸的，幾乎沒有一個Hash函數可以滿足這樣的特性（即使有這樣的Hash函數，也可能很復雜，無法在實際中使用）。也就是說，即使是精心設計的Hash函數，也經常會出現key1 != key2 但是hash(key1) = hash(key2)的情況，這便是Hash沖突（Hash碰撞）。解決Hash碰撞的主要方法有多種（見這裡），作為示例，我們只簡單討論下鏈接法解決沖突。這種方法的基本思想是：在哈希表出現沖突時，使用鏈表的形式鏈接所有具有相同hash值的記錄，而哈希表中只保存鏈表的頭指針。PHP底層的Hash table，便是使用鏈表（雙向鏈表）來解決hash沖突的。關於這一點，後續會有詳細的介紹。
引入鏈表之後，Hash table的結構如下所示：
一個簡單的Hash table的實現如下：
Class HashTable{
private $buckets = null;
/* current size */
private $size = 0;
/* max hashtable size */
private $max = 2048;
private $mask = 0;
public function __construct($size){
$this->_init_hash($size);
}
/* hashtable init */
private function _init_hash($size){
if($size > $this->max){
$size = $this->max;
}
$this->size = $size;
$this->mask = $this->size - 1;
// SplFixedArray is faster when the size is known
// see http://php.net/manual/en/class.splfixedarray.php
$this->buckets = new SplFixedArray($this->size);
}
public function hash( $key ){
$result = 0;
$len = strlen($key);
for($i = 0;$i < $len; $i++ ){
$result += ord($key{$i}) * ((1 << 5) + 1);
}
return $result % ($this->size);
}
/* 拉鏈法 */
public function insert( $key, $val ){
$h = $this->hash($key);
if(!isset($this->buckets[$h])){
$next = NULL;
}else{
$next = $this->bucket[$h];
}
$this->buckets[$h] = new Node($key, $val, $next);
}
/* 拉鏈法 */
public function lookup( $key ){
$h = $this->hash($key);
$cur = $this->buckets[$h];
while($cur !== NULL){
if( $cur->key == $key){
return $cur->value;
}
$cur = $cur->next;
}
return NULL;
}
}
Class Node{
public $key;
public $value;
public $next = null;
public function __construct($key, $value, $next = null){
$this->key = $key;
$this->value = $value;
$this->next = $next;
}
}
$hash = new HashTable(200);
$hash->insert('apple','this is apple');
$hash->insert('orange','this is orange');
$hash->insert('banana','this is banana');
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）：
typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer; /* Used for element traversal */
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 這個成員用於標明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）：
if (flag & HASH_NEXT_INSERT) {
h = ht->nNextFreeElement;
}
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
該結構的定義為：
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 ,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這個結構體的定義也可以看出來：
typedef struct _zend_hash_key {
const char *arKey;
uint nKeyLength;
ulong h;
} zend_hash_key;
而確定數組元素在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鏈表的頭部。該宏的定義為：
#define CONNECT_TO_BUCKET_DLLIST(element, list_head) \
(element)->pNext = (list_head); \
(element)->pLast = NULL; \
if ((element)->pNext) { \
(element)->pNext->pLast = (element); \
}
(2). CONNECT_TO_GLOBAL_DLLIST(element, ht)
與上述不同，這個是將元素插入到全局遍歷的雙鏈表的末尾，這個雙鏈表類似隊列的作用，它保證了我們遍歷數組時的正確順序。該宏的定義是：
1 #define CONNECT_TO_GLOBAL_DLLIST(element, ht) \
2 (element)->pListLast = (ht)->pListTail; \
3 (ht)->pListTail = (element); \
4 (element)->pListNext = NULL; \
5 if ((element)->pListLast != NULL) { \
6 (element)->pListLast->pListNext = (element); \
7 } \
8
9 if (!(ht)->pListHead) { \
10 (ht)->pListHead = (element); \
11 } \
12
13 if ((ht)->pInternalPointer == NULL) { \
14 (ht)->pInternalPointer = (element); \
15 }
(3). HASH_PROTECT_RECURSION(ht)
這個宏主要用於防止HashTable被遞歸遍歷時深度過大，是一種保護機制
#define HASH_PROTECT_RECURSION(ht) \
if ((ht)->bApplyProtection) { \
if ((ht)->nApplyCount++ >= 3) { \
zend_error(E_ERROR, "Nesting level too deep - recursive dependency?");\
} \
}
(4). ZEND_HASH_IF_FULL_DO_RESIZE(ht)
HashTable的大小並不是固定不變的，當nNumOfElements > nTableSize時，會對HashTable進行擴容，以便於容納更多的元素，這便是通過該宏實現的（實際上是調用zend_hash_do_resize來實現的）。該宏定義為：
#define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
if ((ht)->nNumOfElements > (ht)->nTableSize) { \
zend_hash_do_resize(ht); \
}
(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;
}
整個宏定義為：
#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); \
}
(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.該宏定義為：
#define CHECK_INIT(ht) do { \
if (UNEXPECTED((ht)->nTableMask == 0)) { \
(ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent); \
(ht)->nTableMask = (ht)->nTableSize - 1; \
} \
} while (0)
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;
}
/* 字符串索引的查找 */
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);
}
HashTable的更多操作如zend_hash_do_resize（擴容），zend_hash_rehash（擴容之後需要對原來hashTable的元素重新hash ），zend_hash_del_key_or_index（HashTable中刪除元素），zend_hash_destroy（銷毀Hash表），zend_hash_copy（hash表拷貝），這裡不再一一列舉，有興趣的同學可以翻看源碼查看。
