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的數據結構：

//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; //存儲元素數組，指向第一個Bucketuint32_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; };

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30

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數組中取出元素。

比如：

$arr["a"] = 1; $arr["b"] = 2; $arr["c"] = 3; $arr["d"] = 4;unset($arr["c"]);

• 1
• 2
• 3
• 4
• 5
• 6

對應的HashTable如下圖所示。

圖中Bucket的zval.u2.next默認值應該為-1，不是0

2.2.2 映射函數

映射函數(即：散列函數)是散列表的關鍵部分，它將key與value建立映射關系，一般映射函數可以根據key的哈希值與Bucket數組大小取模得到，即key->h % ht->nTableSize，但是PHP卻不是這么做的：

nIndex = key->h | ht->nTableMask;

• 1

顯然位運算要比取模更快。

nTableMask為nTableSize的負數，即:nTableMask = -nTableSize，因為nTableSize等于2^n，所以nTableMask二進制位右側全部為0，也就保證了nIndex落在數組索引的范圍之內(|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

• 1
• 2
• 3
• 4
• 5

2.2.3 哈希碰撞

哈希碰撞是指不同的key可能計算得到相同的哈希值(數值索引的哈希值直接就是數值本身)，但是這些值又需要插入同一個散列表。一般解決方法是將Bucket串成鏈表，查找時遍歷鏈表比較key。

PHP的實現也是如此，只是將鏈表的指針指向轉化為了數值指向，即：指向沖突元素的指針并沒有直接存在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; };

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

當出現沖突時將原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); //移到下一個沖突的value } return NULL;

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

2.2.4 插入、查找、刪除

這幾個基本操作比較簡單，不再贅述，定位到元素所在Bucket位置后的操作類似單鏈表的插入、刪除、查找。

2.2.5 擴容

散列表可存儲的value數是固定的，當空間不夠用時就要進行擴容了。

PHP散列表的大小為2^n，插入時如果容量不夠則首先檢查已刪除元素所占比例，如果達到閾值(ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5)，則將已刪除元素移除，重建索引，如果未到閾值則進行擴容操作，擴大為當前大小的2倍，將當前Bucket數組復制到新的空間，然后重建索引。

//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)) * nSizenew_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)

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35

2.2.6 重建散列表

當刪除元素達到一定數量或擴容后都需要重建散列表，因為value在Bucket位置移動了或哈希數組nTableSize變化了導致key與value的映射關系改變，重建過程實際就是遍歷Bucket數組中的value，然后重新計算映射值更新到散列表，除了更新散列表之外，這里還有一個重要的處理：移除已刪除的value，開始的時候我們說過，刪除value時只是將value的type設置為IS_UNDEF，并沒有實際從Bucket數組中刪除，如果這些value一直存在那么將浪費很多空間，所以這里會把它們移除，操作的方式也比較簡單：將后面未刪除的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數組重新插入索引數組即可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);} }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48

除了上面這些操作，PHP中關于HashTable的還有很多，這里不再介紹。

來源:http://blog.csdn.net/itbsl/article/details/75096710

總結

以上是生活随笔為你收集整理的PHP源码分析-数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。