?
This document uses PHP Chinese website manual Release
數(shù)組
數(shù)組是PHP中非常強(qiáng)大、靈活的一種數(shù)據(jù)類型，它的底層實(shí)現(xiàn)為散列表(HashTable，也稱作：哈希表)，除了我們熟悉的PHP用戶空間的Array類型之外，內(nèi)核中也隨處用到散列表，比如函數(shù)、類、常量、已include文件的索引表、全局符號(hào)表等都用的HashTable存儲(chǔ)。
散列表是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，它的key - value之間存在一個(gè)映射函數(shù)，可以根據(jù)key通過映射函數(shù)直接索引到對(duì)應(yīng)的value值，它不以關(guān)鍵字的比較為基本操作，采用直接尋址技術(shù)（就是說，它是直接通過key映射到內(nèi)存地址上去的），從而加快查找速度，在理想情況下，無須任何比較就可以找到待查關(guān)鍵字，查找的期望時(shí)間為O(1)。
數(shù)組結(jié)構(gòu)
存放記錄的數(shù)組稱做散列表，這個(gè)數(shù)組用來存儲(chǔ)value，而value具體在數(shù)組中的存儲(chǔ)位置由映射函數(shù)根據(jù)key計(jì)算確定，映射函數(shù)可以采用取模的方式，key可以通過一些譬如“times 33”的算法得到一個(gè)整形值，然后與數(shù)組總大小取模得到在散列表中的存儲(chǔ)位置。這是一個(gè)普通散列表的實(shí)現(xiàn)，PHP散列表的實(shí)現(xiàn)整體也是這個(gè)思路，只是有幾個(gè)特殊的地方，下面就是PHP中HashTable的數(shù)據(jù)結(jié)構(gòu)：
//Bucket：散列表中存儲(chǔ)的元素typedef struct _Bucket {
zval val; //存儲(chǔ)的具體value，這里嵌入了一個(gè)zval，而不是一個(gè)指針
zend_ulong h; //key根據(jù)times 33計(jì)算得到的哈希值，或者是數(shù)值索引編號(hào)
zend_string *key; //存儲(chǔ)元素的key} Bucket;//HashTable結(jié)構(gòu)typedef struct _zend_array HashTable;struct _zend_array {
zend_refcounted_h gc; union { struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar flags,
zend_uchar nApplyCount,
zend_uchar nIteratorsCount,
zend_uchar reserve)
} v; uint32_t flags;
} u; uint32_t nTableMask; //哈希值計(jì)算掩碼，等于nTableSize的負(fù)值(nTableMask = -nTableSize)
Bucket *arData; //存儲(chǔ)元素?cái)?shù)組，指向第一個(gè)Bucket
uint32_t nNumUsed; //已用Bucket數(shù)
uint32_t nNumOfElements; //哈希表有效元素?cái)?shù)
uint32_t nTableSize; //哈希表總大小，為2的n次方
uint32_t nInternalPointer;
zend_long nNextFreeElement; //下一個(gè)可用的數(shù)值索引,如:arr[] = 1;arr["a"] = 2;arr[] = 3; 則nNextFreeElement = 2;
dtor_func_t pDestructor;
};HashTable中有兩個(gè)非常相近的值:nNumUsed、nNumOfElements，nNumOfElements表示哈希表已有元素?cái)?shù)，那這個(gè)值不跟nNumUsed一樣嗎？為什么要定義兩個(gè)呢？實(shí)際上它們有不同的含義，當(dāng)將一個(gè)元素從哈希表刪除時(shí)并不會(huì)將對(duì)應(yīng)的Bucket移除，而是將Bucket存儲(chǔ)的zval修改為IS_UNDEF，只有擴(kuò)容時(shí)發(fā)現(xiàn)nNumOfElements與nNumUsed相差達(dá)到一定數(shù)量(這個(gè)數(shù)量是:ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5))時(shí)才會(huì)將已刪除的元素全部移除，重新構(gòu)建哈希表。所以nNumUsed>=nNumOfElements。
HashTable中另外一個(gè)非常重要的值arData，這個(gè)值指向存儲(chǔ)元素?cái)?shù)組的第一個(gè)Bucket，插入元素時(shí)按順序 依次插入數(shù)組，比如第一個(gè)元素在arData[0]、第二個(gè)在arData[1]...arData[nNumUsed]。PHP數(shù)組的有序性正是通過arData保證的，這是第一個(gè)與普通散列表實(shí)現(xiàn)不同的地方。
既然arData并不是按key映射的散列表，那么映射函數(shù)是如何將key與arData中的value建立映射關(guān)系的呢？
實(shí)際上這個(gè)散列表也在arData中，比較特別的是散列表在ht->arData內(nèi)存之前，分配內(nèi)存時(shí)這個(gè)散列表與Bucket數(shù)組一起分配，arData向后移動(dòng)到了Bucket數(shù)組的起始位置，并不是申請(qǐng)內(nèi)存的起始位置，這樣散列表可以由arData指針向前移動(dòng)訪問到，即arData[-1]、arData[-2]、arData[-3]......散列表的結(jié)構(gòu)是uint32_t，它保存的是value在Bucket數(shù)組中的位置。
所以，整體來看HashTable主要依賴arData實(shí)現(xiàn)元素的存儲(chǔ)、索引。插入一個(gè)元素時(shí)先將元素按先后順序插入Bucket數(shù)組，位置是idx，再根據(jù)key的哈希值映射到散列表中的某個(gè)位置nIndex，將idx存入這個(gè)位置；查找時(shí)先在散列表中映射到nIndex，得到value在Bucket數(shù)組的位置idx，再從Bucket數(shù)組中取出元素。
比如：
$arr["a"] = 1; $arr["b"] = 2; $arr["c"] = 3; $arr["d"] = 4;unset($arr["c"]);
對(duì)應(yīng)的HashTable如下圖所示。
映射函數(shù)
映射函數(shù)(即：散列函數(shù))是散列表的關(guān)鍵部分，它將key與value建立映射關(guān)系，一般映射函數(shù)可以根據(jù)key的哈希值與Bucket數(shù)組大小取模得到，即key->h % ht->nTableSize，但是PHP卻不是這么做的：
nIndex = key->h | ht->nTableMask;
顯然位運(yùn)算要比取模更快。
nTableMask為nTableSize的負(fù)數(shù)，即:nTableMask = -nTableSize，因?yàn)閚TableSize等于2^n，所以nTableMask二進(jìn)制位右側(cè)全部為0，也就保證了nIndex落在數(shù)組索引的范圍之內(nèi)(|nIndex| <= nTableSize)：
11111111 11111111 11111111 11111000 -8 11111111 11111111 11111111 11110000 -16 11111111 11111111 11111111 11100000 -32 11111111 11111111 11111111 11000000 -64 11111111 11111111 11111111 10000000 -128
哈希碰撞
哈希碰撞是指不同的key可能計(jì)算得到相同的哈希值(數(shù)值索引的哈希值直接就是數(shù)值本身)，但是這些值又需要插入同一個(gè)散列表。一般解決方法是將Bucket串成鏈表，查找時(shí)遍歷鏈表比較key。
PHP的實(shí)現(xiàn)也是如此，只是將鏈表的指針指向轉(zhuǎn)化為了數(shù)值指向，即：指向沖突元素的指針并沒有直接存在Bucket中，而是保存到了value的zval中：
struct _zval_struct {
zend_value value; /* value */
... union { uint32_t var_flags; uint32_t next; /* hash collision chain */
uint32_t cache_slot; /* literal cache slot */
uint32_t lineno; /* line number (for ast nodes) */
uint32_t num_args; /* arguments number for EX(This) */
uint32_t fe_pos; /* foreach position */
uint32_t fe_iter_idx; /* foreach iterator index */
} u2;
};當(dāng)出現(xiàn)沖突時(shí)將原value的位置保存到新value的zval.u2.next中，然后將新插入的value的位置更新到散列表，也就是后面沖突的value始終插入header。所以查找過程類似：
zend_ulong h = zend_string_hash_val(key);uint32_t idx = ht->arHash[h & ht->nTableMask];while (idx != INVALID_IDX) {
Bucket *b = &ht->arData[idx]; if (b->h == h && zend_string_equals(b->key, key)) { return b;
}
idx = Z_NEXT(b->val); //移到下一個(gè)沖突的value}return NULL;插入、查找、刪除
這幾個(gè)基本操作比較簡單，不再贅述，定位到元素所在Bucket位置后的操作類似單鏈表的插入、刪除、查找。
擴(kuò)容
散列表可存儲(chǔ)的value數(shù)是固定的，當(dāng)空間不夠用時(shí)就要進(jìn)行擴(kuò)容了。
PHP散列表的大小為2^n，插入時(shí)如果容量不夠則首先檢查已刪除元素所占比例，如果達(dá)到閾值(ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5)，則將已刪除元素移除，重建索引，如果未到閾值則進(jìn)行擴(kuò)容操作，擴(kuò)大為當(dāng)前大小的2倍，將當(dāng)前Bucket數(shù)組復(fù)制到新的空間，然后重建索引。
//zend_hash.c
static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
{
if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) {
//只有到一定閾值才進(jìn)行rehash操作
zend_hash_rehash(ht); //重建索引數(shù)組
} else if (ht->nTableSize < HT_MAX_SIZE) {
//擴(kuò)容
void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
//擴(kuò)大為2倍，加法要比乘法快，小的優(yōu)化點(diǎn)無處不在...
uint32_t nSize = ht->nTableSize + ht->nTableSize;
Bucket *old_buckets = ht->arData;
//新分配arData空間，大小為:(sizeof(Bucket) + sizeof(uint32_t)) * nSize
new_data = pemalloc(HT_SIZE_EX(nSize, -nSize), ...);
ht->nTableSize = nSize;
ht->nTableMask = -ht->nTableSize;
//將arData指針偏移到Bucket數(shù)組起始位置
HT_SET_DATA_ADDR(ht, new_data);
//將舊的Bucket數(shù)組拷到新空間
memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
//釋放舊空間
pefree(old_data, ht->u.flags & HASH_FLAG_PERSISTENT);
//重建索引數(shù)組：散列表
zend_hash_rehash(ht);
...
}
...
}
#define HT_SET_DATA_ADDR(ht, ptr) do { \
(ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); \
} while (0)重建散列表
當(dāng)刪除元素達(dá)到一定數(shù)量或擴(kuò)容后都需要重建散列表，因?yàn)関alue在Bucket位置移動(dòng)了或哈希數(shù)組nTableSize變化了導(dǎo)致key與value的映射關(guān)系改變，重建過程實(shí)際就是遍歷Bucket數(shù)組中的value，然后重新計(jì)算映射值更新到散列表，除了更新散列表之外，這里還有一個(gè)重要的處理：移除已刪除的value，開始的時(shí)候我們說過，刪除value時(shí)只是將value的type設(shè)置為IS_UNDEF，并沒有實(shí)際從Bucket數(shù)組中刪除，如果這些value一直存在那么將浪費(fèi)很多空間，所以這里會(huì)把它們移除，操作的方式也比較簡單：將后面未刪除的value依次前移，具體過程如下：
//zend_hash.c
ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
Bucket *p;
uint32_t nIndex, i;
...
i = 0;
p = ht->arData;
if (ht->nNumUsed == ht->nNumOfElements) { //沒有已刪除的直接遍歷Bucket數(shù)組重新插入索引數(shù)組即可
do {
nIndex = p->h | ht->nTableMask;
Z_NEXT(p->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
p++;
} while (++i < ht->nNumUsed);
} else {
do {
if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
//有已刪除元素則將后面的value依次前移，壓實(shí)Bucket數(shù)組
......
while (++i < ht->nNumUsed) {
p++;
if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
ZVAL_COPY_VALUE(&q->val, &p->val);
q->h = p->h;
nIndex = q->h | ht->nTableMask;
q->key = p->key;
Z_NEXT(q->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
if (UNEXPECTED(ht->nInternalPointer == i)) {
ht->nInternalPointer = j;
}
q++;
j++;
}
}
......
ht->nNumUsed = j;
break;
}
nIndex = p->h | ht->nTableMask;
Z_NEXT(p->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
p++;
}while(++i < ht->nNumUsed);
}
}除了上面這些操作，PHP中關(guān)于HashTable的還有很多，這里不再介紹。