## 2.2 數組
數組是PHP中非常強大、靈活的一種數據類型,它的底層實現為散列表(HashTable,也稱作:哈希表),除了我們熟悉的PHP用戶空間的Array類型之外,內核中也隨處用到散列表,比如函數、類、常量、已include文件的索引表、全局符號表等都用的HashTable存儲。
散列表是根據關鍵碼值(Key value)而直接進行訪問的數據結構,它的key - value之間存在一個映射函數,可以根據key通過映射函數直接索引到對應的value值,它不以關鍵字的比較為基本操作,采用直接尋址技術(就是說,它是直接通過key映射到內存地址上去的),從而加快查找速度,在理想情況下,無須任何比較就可以找到待查關鍵字,查找的期望時間為O(1)。
### 2.2.1 數組結構
存放記錄的數組稱做散列表,這個數組用來存儲value,而value具體在數組中的存儲位置由映射函數根據key計算確定,映射函數可以采用取模的方式,key可以通過一些譬如“times 33”的算法得到一個整形值,然后與數組總大小取模得到在散列表中的存儲位置。這是一個普通散列表的實現,PHP散列表的實現整體也是這個思路,只是有幾個特殊的地方,下面就是PHP中HashTable的數據結構:
```c
//Bucket:散列表中存儲的元素
typedef struct _Bucket {
zval val; //存儲的具體value,這里嵌入了一個zval,而不是一個指針
zend_ulong h; //key根據times 33計算得到的哈希值,或者是數值索引編號
zend_string *key; //存儲元素的key
} Bucket;
//HashTable結構
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)
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`保證的,這是第一個與普通散列表實現不同的地方。
既然arData并不是按key映射的散列表,那么映射函數是如何將key與arData中的value建立映射關系的呢?
實際上這個散列表也在`arData`中,比較特別的是散列表在ht->arData內存之前,分配內存時這個散列表與Bucket數組一起分配,arData向后移動到了Bucket數組的起始位置,并不是申請內存的起始位置,這樣散列表可以由arData指針向前移動訪問到,即arData[-1]、arData[-2]、arData[-3]......散列表的結構是`uint32_t`,它保存的是value在Bucket數組中的位置。
所以,整體來看HashTable主要依賴arData實現元素的存儲、索引。插入一個元素時先將元素按先后順序插入Bucket數組,位置是idx,再根據key的哈希值映射到散列表中的某個位置nIndex,將idx存入這個位置;查找時先在散列表中映射到nIndex,得到value在Bucket數組的位置idx,再從Bucket數組中取出元素。
比如:
```php
$arr["a"] = 1;
$arr["b"] = 2;
$arr["c"] = 3;
$arr["d"] = 4;
unset($arr["c"]);
```
對應的HashTable如下圖所示。

> 圖中Bucket的zval.u2.next默認值應該為-1,不是0
### 2.2.2 映射函數
映射函數(即:散列函數)是散列表的關鍵部分,它將key與value建立映射關系,一般映射函數可以根據key的哈希值與Bucket數組大小取模得到,即`key->h % ht->nTableSize`,但是PHP卻不是這么做的:
```c
nIndex = key->h | ht->nTableMask;
```
顯然位運算要比取模更快。
`nTableMask`為`nTableSize`的負數,即:`nTableMask = -nTableSize`,因為`nTableSize`等于2^n,所以`nTableMask`二進制位右側全部為0,也就保證了nIndex落在數組索引的范圍之內(`|nIndex| <= nTableSize`):
```c
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
```
### 2.2.3 哈希碰撞
哈希碰撞是指不同的key可能計算得到相同的哈希值(數值索引的哈希值直接就是數值本身),但是這些值又需要插入同一個散列表。一般解決方法是將Bucket串成鏈表,查找時遍歷鏈表比較key。
PHP的實現也是如此,只是將鏈表的指針指向轉化為了數值指向,即:指向沖突元素的指針并沒有直接存在Bucket中,而是保存到了value的`zval`中:
```c
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;
};
```
當出現沖突時將原value的位置保存到新value的`zval.u2.next`中,然后將新插入的value的位置更新到散列表,也就是后面沖突的value始終插入header。所以查找過程類似:
```c
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); //移到下一個沖突的value
}
return NULL;
```
### 2.2.4 插入、查找、刪除
這幾個基本操作比較簡單,不再贅述,定位到元素所在Bucket位置后的操作類似單鏈表的插入、刪除、查找。
### 2.2.5 擴容
散列表可存儲的value數是固定的,當空間不夠用時就要進行擴容了。
PHP散列表的大小為2^n,插入時如果容量不夠則首先檢查已刪除元素所占比例,如果達到閾值(ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5),則將已刪除元素移除,重建索引,如果未到閾值則進行擴容操作,擴大為當前大小的2倍,將當前Bucket數組復制到新的空間,然后重建索引。
```c
//zend_hash.c
static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
{
if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) {
//只有到一定閾值才進行rehash操作
zend_hash_rehash(ht); //重建索引數組
} else if (ht->nTableSize < HT_MAX_SIZE) {
//擴容
void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
//擴大為2倍,加法要比乘法快,小的優化點無處不在...
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數組起始位置
HT_SET_DATA_ADDR(ht, new_data);
//將舊的Bucket數組拷到新空間
memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
//釋放舊空間
pefree(old_data, ht->u.flags & HASH_FLAG_PERSISTENT);
//重建索引數組:散列表
zend_hash_rehash(ht);
...
}
...
}
#define HT_SET_DATA_ADDR(ht, ptr) do { \
(ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); \
} while (0)
```
### 2.2.6 重建散列表
當刪除元素達到一定數量或擴容后都需要重建散列表,因為value在Bucket位置移動了或哈希數組nTableSize變化了導致key與value的映射關系改變,重建過程實際就是遍歷Bucket數組中的value,然后重新計算映射值更新到散列表,除了更新散列表之外,這里還有一個重要的處理:移除已刪除的value,開始的時候我們說過,刪除value時只是將value的type設置為IS_UNDEF,并沒有實際從Bucket數組中刪除,如果這些value一直存在那么將浪費很多空間,所以這里會把它們移除,操作的方式也比較簡單:將后面未刪除的value依次前移,具體過程如下:
```c
//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數組重新插入索引數組即可
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依次前移,壓實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);
}
}
```
除了上面這些操作,PHP中關于HashTable的還有很多,這里不再介紹。
- 前言
- 第1章 PHP基本架構
- 1.1 PHP簡介
- 1.2 PHP7的改進
- 1.3 FPM
- 1.3.1 概述
- 1.3.2 基本實現
- 1.3.3 FPM的初始化
- 1.3.4 請求處理
- 1.3.5 進程管理
- 1.4 PHP執行的幾個階段
- 第2章 變量
- 2.1 變量的內部實現
- 2.2 數組
- 2.3 靜態變量
- 2.4 全局變量
- 2.5 常量
- 第3章 Zend虛擬機
- 3.1 PHP代碼的編譯
- 3.1.1 詞法解析、語法解析
- 3.1.2 抽象語法樹編譯流程
- 3.2 函數實現
- 3.2.1 內部函數
- 3.2.2 用戶函數的實現
- 3.3 Zend引擎執行流程
- 3.3.1 基本結構
- 3.3.2 執行流程
- 3.3.3 函數的執行流程
- 3.3.4 全局execute_data和opline
- 3.4 面向對象實現
- 3.4.1 類
- 3.4.2 對象
- 3.4.3 繼承
- 3.4.4 動態屬性
- 3.4.5 魔術方法
- 3.4.6 類的自動加載
- 3.5 運行時緩存
- 3.6 Opcache
- 3.6.1 opcode緩存
- 3.6.2 opcode優化
- 3.6.3 JIT
- 第4章 PHP基礎語法實現
- 4.1 類型轉換
- 4.2 選擇結構
- 4.3 循環結構
- 4.4 中斷及跳轉
- 4.5 include/require
- 4.6 異常處理
- 第5章 內存管理
- 5.1 Zend內存池
- 5.2 垃圾回收
- 第6章 線程安全
- 6.1 什么是線程安全
- 6.2 線程安全資源管理器
- 第7章 擴展開發
- 7.1 概述
- 7.2 擴展的實現原理
- 7.3 擴展的構成及編譯
- 7.3.1 擴展的構成
- 7.3.2 編譯工具
- 7.3.3 編寫擴展的基本步驟
- 7.3.4 config.m4
- 7.4 鉤子函數
- 7.5 運行時配置
- 7.5.1 全局變量
- 7.5.2 ini配置
- 7.6 函數
- 7.6.1 內部函數注冊
- 7.6.2 函數參數解析
- 7.6.3 引用傳參
- 7.6.4 函數返回值
- 7.6.5 函數調用
- 7.7 zval的操作
- 7.7.1 新生成各類型zval
- 7.7.2 獲取zval的值及類型
- 7.7.3 類型轉換
- 7.7.4 引用計數
- 7.7.5 字符串操作
- 7.7.6 數組操作
- 7.8 常量
- 7.9 面向對象
- 7.9.1 內部類注冊
- 7.9.2 定義成員屬性
- 7.9.3 定義成員方法
- 7.9.4 定義常量
- 7.9.5 類的實例化
- 7.10 資源類型
- 7.11 經典擴展解析
- 7.8.1 Yaf
- 7.8.2 Redis
- 第8章 命名空間
- 8.1 概述
- 8.2 命名空間的定義
- 8.2.1 定義語法
- 8.2.2 內部實現
- 8.3 命名空間的使用
- 8.3.1 基本用法
- 8.3.2 use導入
- 8.3.3 動態用法
- 附錄
- break/continue按標簽中斷語法實現
- defer推遲函數調用語法的實現
- 一起線上事故引發的對PHP超時控制的思考