PHP7+内部哈希表，即PHP強大array結構的核心實作。
哈希表是PHP内部非常重要的資料結構，除了PHP使用者空間的Array，核心也随處用到，比如function、class的索引、符号表等等都用到了哈希表。
關于哈希結構PHP7+與PHP5+的差別可以翻下[nikic]早些時候寫的一篇文章，這裡不作讨論。
示例中的HastTable實作并不是将PHP實際的實作摘出來的，而是根據PHP的實作按照自己的思路具體實作的，可以作為參考。【https://github.com/pangudashu/anywork/tree/master/hashtable】
資料結構
//zend_types.h
typedef struct _Bucket {
zval val;
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
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; //哈希值計算掩碼，等于nTableSize的負值(nTableMask = ~nTableSize + 1)
Bucket *arData; //存儲元素數組，指向第一個Bucket
uint32_t nNumUsed; //已用Bucket數
uint32_t nNumOfElements; //哈希表已有元素數
uint32_t nTableSize; //哈希表總大小，為2的n次方
uint32_t nInternalPointer;
zend_long nNextFreeElement; //下一個可用的數值索引,如:arr[] = 1;arr["a"] = 2;arr[] = 3; 則nNextFreeElement = 2;
dtor_func_t pDestructor;
};
HashTable中有兩個非常相近的值:
nNumUsed
、
nNumOfElements
，
nNumOfElements
表示哈希表已有元素數，那這個值不跟
nNumUsed
一樣嗎？為什麼要定義兩個呢？實際上它們有不同的含義，當将一個元素從哈希表删除時并不會将對應的Bucket移除，而是将Bucket存儲的zval标示為
IS_UNDEF
，隻有擴容時發現nNumOfElements與nNumUsed相差達到一定數量(這個數量是:
ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5)
)時才會将已删除的元素全部移除，重新建構哈希表。是以
nNumUsed
>=
nNumOfElements
。
HashTable中另外一個非常重要的值
arData
，這個值指向存儲元素數組的第一個Bucket，插入元素時按順序依次插入數組，比如第一個元素在arData[0]、第二個在arData[1]…arData[nNumUsed]。PHP數組的有序性正是通過
arData
保證的。
哈希表實作的關鍵是有一個數組存儲哈希值與Bucket的映射，但是HashTable中并沒有這樣一個索引數組。
實際上這個索引數組包含在
arData
中，索引數組與Bucket清單一起配置設定，arData指向了Bucket清單的起始位置，而索引數組可以通過arData指針向前移動通路到，即arData[-1]、arData[-2]、arData[-3]……索引數組的結構是
uint32_t
,它存儲的是Bucket元素在arData中的位置。
是以，整體來看HashTable主要依賴arData實作元素的存儲、索引。插入一個元素時先将元素插入Bucket數組，位置是idx，再根據key的哈希值與nTableMask計算出索引數組的位置，将idx存入這個位置；查找時先根據key的哈希值與nTableMask計算出索引數組的位置，獲得元素在Bucket數組的位置idx，再從Bucket數組中取出元素。
索引數組
索引數組類型是
uint32_t[]
，存儲的值為元素在Bucket數組中的位置
索引位置(nIndex)是如何得到的？我們一般根據哈希值與數組大小取模得到，即
key->h % ht->nTableSize
，但是PHP是這麼計算的：
nIndex = key->h | ht->nTableMask;
顯然位運算要比取模更快。
nTableMask
為
nTableSize
的負數，即:
nTableMask = -nTableSize
，因為
nTableSize
等于2^n，是以
nTableMask
二進制位右側全部為0，也就保證了
|nIndex| <= nTableSize
：
-
-
-
-
-
哈希碰撞
哈希碰撞是指不同的key可能計算得到相同的哈希值(數值索引的哈希值直接就是數值本身)，但是這些值又需要插入同一個哈希表。一般解決方法是将Bucket串成連結清單，查找時周遊連結清單比較key。
PHP的實作也是類似，隻是指向沖突元素的指針并沒有直接存在Bucket中，而是存在嵌入的
zval
中，zval的結構：
struct _zval_struct {
zend_value value; /* value */
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar type, /* active type */
zend_uchar type_flags,
zend_uchar const_flags,
zend_uchar reserved) /* call info for EX(This) */
} v;
uint32_t type_info;
} u1;
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;
};
zval.u2.next
存的就是沖突元素在Bucket數組中的位置，是以查找過程類似：
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); // b->val.u2.next
}
return NULL;
插入、查找、删除
這幾個基本操作比較簡單，不再贅述，定位到元素所在Bucket位置後的操作類似單連結清單的插入、删除、查找。
擴容
哈希表的大小為2^n，插入時如果容量不夠則首先檢查已删除元素所占比例，如果達到門檻值(ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5)，則将已删除元素移除，重建索引，如果未到門檻值則進行擴容操作，擴大為目前大小的2倍，将目前Bucket數組複制到新的空間，然後重建索引。
//zend_hash.c
static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
{
IS_CONSISTENT(ht);
HT_ASSERT(GC_REFCOUNT(ht) == );
if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> )) { //隻有到一定門檻值才進行rehash操作
HANDLE_BLOCK_INTERRUPTIONS();
zend_hash_rehash(ht); //重建索引數組
HANDLE_UNBLOCK_INTERRUPTIONS();
} else if (ht->nTableSize < HT_MAX_SIZE) { //擴大為兩倍
void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
uint32_t nSize = ht->nTableSize + ht->nTableSize;
Bucket *old_buckets = ht->arData;
HANDLE_BLOCK_INTERRUPTIONS();
new_data = pemalloc(HT_SIZE_EX(nSize, -nSize), ht->u.flags & HASH_FLAG_PERSISTENT); //新配置設定arData空間，大小為:(sizeof(Bucket) + sizeof(uint32_t)) * nSize
ht->nTableSize = nSize;
ht->nTableMask = -ht->nTableSize; //nTableSize負值
HT_SET_DATA_ADDR(ht, new_data); //将arData指針偏移到Bucket數組起始位置
memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed); //将舊的Bucket數組拷到新空間
pefree(old_data, ht->u.flags & HASH_FLAG_PERSISTENT); //釋放舊空間
zend_hash_rehash(ht); //重建索引數組
HANDLE_UNBLOCK_INTERRUPTIONS();
} else {
zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%zu * %zu + %zu)", ht->nTableSize * , sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
}
}
#define HT_SET_DATA_ADDR(ht, ptr) do { \
(ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); \
} while ()
重建索引
當删除元素達到一定數量或擴容後都需要進行索引數組的重建，因為元素所在Bucket位置移動了或哈希數組nTableSize變化了導緻原哈希索引變化，已删除的元素将重新可以配置設定。
//zend_hash.c
ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
Bucket *p;
uint32_t nIndex, i;
...
i = ;
p = ht->arData;
if (ht->nNumUsed == ht->nNumOfElements) { //沒有已删除的直接周遊Bucket數組重新插入索引數組即可
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)) {//有已删除元素需要将其移到後面，壓實Bucket數組
......
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);
}
}