全面剖析PHP 數(shù)組底層實(shí)現(xiàn)邏輯-魔扣目錄

前言

php小編香蕉全面剖析php數(shù)組底層實(shí)現(xiàn)邏輯。php中的數(shù)組是一種靈活且強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，背后的實(shí)現(xiàn)邏輯卻是相當(dāng)復(fù)雜的。在本文中，我們將深入探討php數(shù)組的底層原理，包括數(shù)組的內(nèi)部結(jié)構(gòu)、索引與哈希表的關(guān)系，以及數(shù)組的增刪改查操作的實(shí)現(xiàn)方式。通過(guò)了解php數(shù)組的底層實(shí)現(xiàn)邏輯，可以幫助開(kāi)發(fā)者更好地理解和利用數(shù)組這一重要的數(shù)據(jù)結(jié)構(gòu)。

數(shù)組的結(jié)構(gòu)

一個(gè)數(shù)組在 PHP 內(nèi)核里是長(zhǎng)什么樣的呢？我們可以從 PHP 的源碼里看到其結(jié)構(gòu)如下：

<code>//?定義結(jié)構(gòu)體別名為?HashTable
<a style="color:#f60; text-decoration:underline;" href="https://www.php.cn/zt/58423.html" target="_blank">typedef</a>?struct?_zend_array?HashTable;

struct?_zend_array?{
	//?<strong class="keylink">GC</strong>?保存引用計(jì)數(shù)，內(nèi)存管理相關(guān)；本文不涉及
	zend_refcounted_h?gc;
	//?u?儲(chǔ)存輔助信息；本文不涉及
	u<strong class="keylink">NIO</strong>n?{
		struct?{
			ZEND_ENDIAN_LOHI_4(
				zend_uchar????flags,
				zend_uchar????nApplyCount,
				zend_uchar????nIteratorsCount,
				zend_uchar????consistency)
		}?v;
		uint32_t?flags;
	}?u;
	//?用于散列函數(shù)
	uint32_t??????????nTableMask;
	//?arData?指向儲(chǔ)存元素的數(shù)組第一個(gè)?Bucket，Bucket?為統(tǒng)一的數(shù)組元素類型
	Bucket???????????*arData;
	//?已使用?Bucket?數(shù)
	uint32_t??????????nNumUsed;
	//?數(shù)組內(nèi)有效元素個(gè)數(shù)
	uint32_t??????????nNumOfElements;
	//?數(shù)組總?cè)萘?	uint32_t??????????nTableSize;
	//?內(nèi)部指針，用于遍歷
	uint32_t??????????nInternalPointer;
	//?下一個(gè)可用數(shù)字<strong class="keylink">索引</strong>
	zend_long?????????nNextFreeElement;
	//?析構(gòu)函數(shù)
	dtor_func_t???????pDestructor;
};</code>

登錄后復(fù)制

nNumUsed 和 nNumOfElements 的區(qū)別：nNumUsed 指的是 arData 數(shù)組中已使用的 Bucket 數(shù)，因?yàn)閿?shù)組在刪除元素后只是將該元素 Bucket 對(duì)應(yīng)值的類型設(shè)置為 IS_UNDEF（因?yàn)槿绻看蝿h除元素都要將數(shù)組移動(dòng)并重新索引太浪費(fèi)時(shí)間），而 nNumOfElements 對(duì)應(yīng)的是數(shù)組中真正的元素個(gè)數(shù)。

nTableSize 數(shù)組的容量，該值為 2 的冪次方。PHP 的數(shù)組是不定長(zhǎng)度但 C 語(yǔ)言的數(shù)組定長(zhǎng)的，為了實(shí)現(xiàn) PHP 的不定長(zhǎng)數(shù)組的功能，采用了「擴(kuò)容」的機(jī)制，就是在每次插入元素的時(shí)候判斷 nTableSize 是否足以儲(chǔ)存。如果不足則重新申請(qǐng) 2 倍 nTableSize 大小的新數(shù)組，并將原數(shù)組復(fù)制過(guò)來(lái)（此時(shí)正是清除原數(shù)組中類型為 IS_UNDEF 元素的時(shí)機(jī)）并且重新索引。

nNextFreeElement 保存下一個(gè)可用數(shù)字索引，例如在 PHP 中 $a[] = 1; 這種用法將插入一個(gè)索引為 nNextFreeElement 的元素，然后 nNextFreeElement ?自增 1。

_zend_array 這個(gè)結(jié)構(gòu)先講到這里，有些結(jié)構(gòu)體成員的作用在下文會(huì)解釋，不用緊張O(∩_∩)O哈哈~。下面來(lái)看看作為數(shù)組成員的 Bucket 結(jié)構(gòu)：

<code>typedef?struct?_Bucket?{
	//?數(shù)組元素的值
	zval??????????????val;
	//?key?通過(guò)?Time?33?<strong class="keylink">算法</strong>計(jì)算得到的哈希值或數(shù)字索引
	zend_ulong????????h;
	//?字符鍵名，數(shù)字索引則為?NULL
	zend_string??????*key;
}?Bucket;</code>

登錄后復(fù)制

數(shù)組訪問(wèn)

我們知道 PHP 數(shù)組是基于哈希表實(shí)現(xiàn)的，而與一般哈希表不同的是 PHP 的數(shù)組還實(shí)現(xiàn)了元素的有序性，就是插入的元素從內(nèi)存上來(lái)看是連續(xù)的而不是亂序的，為了實(shí)現(xiàn)這個(gè)有序性 PHP 采用了「映射表」技術(shù)。下面就通過(guò)圖例說(shuō)明我們是如何訪問(wèn) PHP 數(shù)組的元素 :-D。

注意：因?yàn)殒I名到映射表下標(biāo)經(jīng)過(guò)了兩次散列運(yùn)算，為了區(qū)分本文用哈希特指第一次散列，散列即為第二次散列。

由圖可知，映射表和數(shù)組元素在同一片連續(xù)的內(nèi)存中，映射表是一個(gè)長(zhǎng)度與存儲(chǔ)元素相同的整型數(shù)組，它默認(rèn)值為 -1 ，有效值為 Bucket 數(shù)組的下標(biāo)。而 HashTable->arData 指向的是這片內(nèi)存中 Bucket 數(shù)組的第一個(gè)元素。

舉個(gè)例子 $a['key'] 訪問(wèn)數(shù)組 $a 中鍵名為 key 的成員，流程介紹：首先通過(guò) Time 33 算法計(jì)算出 key 的哈希值，然后通過(guò)散列算法計(jì)算出該哈希值對(duì)應(yīng)的映射表下標(biāo)，因?yàn)橛成浔碇斜４娴闹稻褪?Bucket 數(shù)組中的下標(biāo)值，所以就能獲取到 Bucket 數(shù)組中對(duì)應(yīng)的元素。

現(xiàn)在我們來(lái)聊一下散列算法，就是通過(guò)鍵名的哈希值映射到「映射表」的下標(biāo)的算法。其實(shí)很簡(jiǎn)單就一行代碼：

<code>nIndex?=?h?|?ht-&gt;nTableMask;</code>

登錄后復(fù)制

將哈希值和 nTableMask 進(jìn)行或運(yùn)算即可得出映射表的下標(biāo)，其中 nTableMask 數(shù)值為 nTableSize 的負(fù)數(shù)。并且由于 ?nTableSize 的值為 2 的冪次方，所以 h | ht->nTableMask 的取值范圍在 [-nTableSize, -1] 之間，正好在映射表的下標(biāo)范圍內(nèi)。至于為何不用簡(jiǎn)單的「取余」運(yùn)算而是費(fèi)盡周折的采用「按位或」運(yùn)算？因?yàn)椤赴次换颉惯\(yùn)算的速度要比「取余」運(yùn)算要快很多，我覺(jué)得對(duì)于這種頻繁使用的操作來(lái)說(shuō)，復(fù)雜一點(diǎn)的實(shí)現(xiàn)帶來(lái)的時(shí)間上的優(yōu)化是值得的。

散列沖突

不同鍵名的哈希值通過(guò)散列計(jì)算得到的「映射表」下標(biāo)有可能相同，此時(shí)便發(fā)生了散列沖突。對(duì)于這種情況 PHP 使用了「鏈地址法」解決。下圖是訪問(wèn)發(fā)生散列沖突的元素的情況：

這看似與第一張圖差不多，但我們同樣訪問(wèn) $a['key'] 的過(guò)程多了一些步驟。首先通過(guò)散列運(yùn)算得出映射表下標(biāo)為 -2 ，然后訪問(wèn)映射表發(fā)現(xiàn)其內(nèi)容指向 arData 數(shù)組下標(biāo)為 1 的元素。此時(shí)我們將該元素的 key 和要訪問(wèn)的鍵名相比較，發(fā)現(xiàn)兩者并不相等，則該元素并非我們所想訪問(wèn)的元素，而元素的 val.u2.next 保存的值正是下一個(gè)具有相同散列值的元素對(duì)應(yīng) arData 數(shù)組的下標(biāo)，所以我們可以不斷通過(guò) next 的值遍歷直到找到鍵名相同的元素或查找失敗。

插入元素

插入元素的函數(shù) _zend_hash_add_or_update_i ，基于 PHP 7.2.9 的代碼如下：

<code>static?zend_always_inline?zval?*_zend_hash_add_or_update_i(HashTable?*ht,?zend_string?*key,?zval?*pData,?uint32_t?flag?ZEND_FILE_LINE_DC)
{
	zend_ulong?h;
	uint32_t?nIndex;
	uint32_t?idx;
	Bucket?*p;

	IS_CONSISTENT(ht);
	HT_ASSERT_RC1(ht);
	if?(UNEXPECTED(!(ht-&gt;u.flags?&amp;?HASH_FLAG_INITIALIZED)))?{?//?數(shù)組未初始化
		//?初始化數(shù)組
		CHECK_INIT(ht,?0);
		//?跳轉(zhuǎn)至插入元素段
		goto?add_to_hash;
	}?else?if?(ht-&gt;u.flags?&amp;?HASH_FLAG_PACKED)?{?//?數(shù)組為連續(xù)數(shù)字索引數(shù)組
		//?轉(zhuǎn)換為關(guān)聯(lián)數(shù)組
		zend_hash_packed_to_hash(ht);
	}?else?if?((flag?&amp;?HASH_ADD_NEW)?==?0)?{?//?添加新元素
		//?查找鍵名對(duì)應(yīng)的元素
		p?=?zend_hash_find_bucket(ht,?key);

		if?(p)?{?//?若相同鍵名元素存在
			zval?*data;
			
			if?(flag?&amp;?HASH_ADD)?{?//?指定?add?操作
				if?(!(flag?&amp;?HASH_UPDATE_INDIRECT))?{?//?若不允許更新間接類型變量則直接返回
					return?NULL;
				}
				//?確定當(dāng)前值和新值不同
				ZEND_ASSERT(&amp;p-&gt;val?!=?pData);
				//?data?指向原數(shù)組成員值
				data?=?&amp;p-&gt;val;
				if?(Z_TYPE_P(data)?==?IS_INDIRECT)?{?//?原數(shù)組元素變量類型為間接類型
?					//?取間接變量對(duì)應(yīng)的變量
					data?=?Z_INDIRECT_P(data);
					if?(Z_TYPE_P(data)?!=?IS_UNDEF)?{?//?該對(duì)應(yīng)變量存在則直接返回
						return?NULL;
					}
				}?else?{?//?非間接類型直接返回
					return?NULL;
				}
			
			}?else?{?//?沒(méi)有指定?add?操作
				//?確定當(dāng)前值和新值不同
				ZEND_ASSERT(&amp;p-&gt;val?!=?pData);
				//?data?指向原數(shù)組元素值
				data?=?&amp;p-&gt;val;
				//?允許更新間接類型變量則?data?指向?qū)?yīng)的變量
				if?((flag?&amp;?HASH_UPDATE_INDIRECT)?&amp;&amp;?Z_TYPE_P(data)?==?IS_INDIRECT)?{
					data?=?Z_INDIRECT_P(data);
				}
			}
			if?(ht-&gt;pDestructor)?{?//?析構(gòu)函數(shù)存在
				//?執(zhí)行析構(gòu)函數(shù)
				ht-&gt;pDestructor(data);
			}
			//?將?pData?的值復(fù)制給?data
			ZVAL_COPY_VALUE(data,?pData);
			return?data;
		}
	}
	//?如果哈希表已滿，則進(jìn)行擴(kuò)容
	ZEND_HASH_IF_FULL_DO_RESIZE(ht);

add_to_hash:
	//?數(shù)組已使用?Bucket?數(shù)?+1
	idx?=?ht-&gt;nNumUsed++;
	//?數(shù)組有效元素?cái)?shù)目?+1
	ht-&gt;nNumOfElements++;
	//?若內(nèi)部指針無(wú)效則指向當(dāng)前下標(biāo)
	if?(ht-&gt;nInternalPointer?==?HT_INVALID_IDX)?{
		ht-&gt;nInternalPointer?=?idx;
	}
????
	zend_hash_iterators_update(ht,?HT_INVALID_IDX,?idx);
	//?p?為新元素對(duì)應(yīng)的?Bucket
	p?=?ht-&gt;arData?+?idx;
	//?設(shè)置鍵名
	p-&gt;key?=?key;
	if?(!ZSTR_IS_INTERNED(key))?{
		zend_string_addref(key);
		ht-&gt;u.flags?&amp;=?~HASH_FLAG_STATIC_KEYS;
		zend_string_hash_val(key);
	}
	//?計(jì)算鍵名的哈希值并賦值給?p
	p-&gt;h?=?h?=?ZSTR_H(key);
	//?將?pData?賦值該?Bucket?的?val
	ZVAL_COPY_VALUE(&amp;p-&gt;val,?pData);
	//?計(jì)算映射表下標(biāo)
	nIndex?=?h?|?ht-&gt;nTableMask;
	//?解決沖突，將原映射表中的內(nèi)容賦值給新元素變量值的?u2.next?成員
	Z_NEXT(p-&gt;val)?=?HT_HASH(ht,?nIndex);
	//?將映射表中的值設(shè)為?idx
	HT_HASH(ht,?nIndex)?=?HT_IDX_TO_HASH(idx);

	return?&amp;p-&gt;val;
}</code>

登錄后復(fù)制

?擴(kuò)容

前面將數(shù)組結(jié)構(gòu)的時(shí)候我們有提到擴(kuò)容，而在插入元素的代碼里有這樣一個(gè)宏 ZEND_HASH_IF_FULL_DO_RESIZE，這個(gè)宏其實(shí)就是調(diào)用了 zend_hash_do_resize 函數(shù)，對(duì)數(shù)組進(jìn)行擴(kuò)容并重新索引。注意：并非每次 Bucket 數(shù)組滿了都需要擴(kuò)容，如果 Bucket 數(shù)組中 IS_UNDEF 元素的數(shù)量占較大比例，就直接將 IS_UNDEF 元素刪除并重新索引，以此節(jié)省內(nèi)存。下面我們看看 zend_hash_do_resize 函數(shù)：

重新索引的邏輯在 zend_hash_rehash 函數(shù)中，代碼如下：

?總結(jié)

嗯哼，本文就到此結(jié)束了，因?yàn)樽陨硭皆虿荒芙忉尩氖衷敱M清楚。這算是我寫(xiě)過(guò)最難寫(xiě)的內(nèi)容了，寫(xiě)完之后似乎覺(jué)得這篇文章就我自己能看明白/(ㄒoㄒ)/~~因?yàn)槲墓P太辣雞。想起一句話「如果你不能簡(jiǎn)單地解釋一樣?xùn)|西，說(shuō)明你沒(méi)真正理解它。」PHP 的源碼里有很多細(xì)節(jié)和實(shí)現(xiàn)我都不算熟悉，這篇文章只是一個(gè)我的 PHP 底層學(xué)習(xí)的開(kāi)篇，希望以后能夠?qū)懗稣嬲钊霚\出的好文章。