亚洲视频二区_亚洲欧洲日本天天堂在线观看_日韩一区二区在线观看_中文字幕不卡一区

前言

php小編香蕉全面剖析php數組底層實現邏輯。php中的數組是一種靈活且強大的數據結構，背后的實現邏輯卻是相當復雜的。在本文中，我們將深入探討php數組的底層原理，包括數組的內部結構、索引與哈希表的關系，以及數組的增刪改查操作的實現方式。通過了解php數組的底層實現邏輯，可以幫助開發者更好地理解和利用數組這一重要的數據結構。

數組的結構

一個數組在 PHP 內核里是長什么樣的呢？我們可以從 PHP 的源碼里看到其結構如下：

<code>//?定義結構體別名為?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>?保存引用計數，內存管理相關；本文不涉及
	zend_refcounted_h?gc;
	//?u?儲存輔助信息；本文不涉及
	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;
	//?用于散列函數
	uint32_t??????????nTableMask;
	//?arData?指向儲存元素的數組第一個?Bucket，Bucket?為統一的數組元素類型
	Bucket???????????*arData;
	//?已使用?Bucket?數
	uint32_t??????????nNumUsed;
	//?數組內有效元素個數
	uint32_t??????????nNumOfElements;
	//?數組總容量
	uint32_t??????????nTableSize;
	//?內部指針，用于遍歷
	uint32_t??????????nInternalPointer;
	//?下一個可用數字<strong class="keylink">索引</strong>
	zend_long?????????nNextFreeElement;
	//?析構函數
	dtor_func_t???????pDestructor;
};</code>

登錄后復制

nNumUsed 和 nNumOfElements 的區別：nNumUsed 指的是 arData 數組中已使用的 Bucket 數，因為數組在刪除元素后只是將該元素 Bucket 對應值的類型設置為 IS_UNDEF（因為如果每次刪除元素都要將數組移動并重新索引太浪費時間），而 nNumOfElements 對應的是數組中真正的元素個數。

nTableSize 數組的容量，該值為 2 的冪次方。PHP 的數組是不定長度但 C 語言的數組定長的，為了實現 PHP 的不定長數組的功能，采用了「擴容」的機制，就是在每次插入元素的時候判斷 nTableSize 是否足以儲存。如果不足則重新申請 2 倍 nTableSize 大小的新數組，并將原數組復制過來（此時正是清除原數組中類型為 IS_UNDEF 元素的時機）并且重新索引。

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

_zend_array 這個結構先講到這里，有些結構體成員的作用在下文會解釋，不用緊張O(∩_∩)O哈哈~。下面來看看作為數組成員的 Bucket 結構：

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

登錄后復制

數組訪問

我們知道 PHP 數組是基于哈希表實現的，而與一般哈希表不同的是 PHP 的數組還實現了元素的有序性，就是插入的元素從內存上來看是連續的而不是亂序的，為了實現這個有序性 PHP 采用了「映射表」技術。下面就通過圖例說明我們是如何訪問 PHP 數組的元素 :-D。

注意：因為鍵名到映射表下標經過了兩次散列運算，為了區分本文用哈希特指第一次散列，散列即為第二次散列。

由圖可知，映射表和數組元素在同一片連續的內存中，映射表是一個長度與存儲元素相同的整型數組，它默認值為 -1 ，有效值為 Bucket 數組的下標。而 HashTable->arData 指向的是這片內存中 Bucket 數組的第一個元素。

舉個例子 $a['key'] 訪問數組 $a 中鍵名為 key 的成員，流程介紹：首先通過 Time 33 算法計算出 key 的哈希值，然后通過散列算法計算出該哈希值對應的映射表下標，因為映射表中保存的值就是 Bucket 數組中的下標值，所以就能獲取到 Bucket 數組中對應的元素。

現在我們來聊一下散列算法，就是通過鍵名的哈希值映射到「映射表」的下標的算法。其實很簡單就一行代碼：

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

登錄后復制

將哈希值和 nTableMask 進行或運算即可得出映射表的下標，其中 nTableMask 數值為 nTableSize 的負數。并且由于 ?nTableSize 的值為 2 的冪次方，所以 h | ht->nTableMask 的取值范圍在 [-nTableSize, -1] 之間，正好在映射表的下標范圍內。至于為何不用簡單的「取余」運算而是費盡周折的采用「按位或」運算？因為「按位或」運算的速度要比「取余」運算要快很多，我覺得對于這種頻繁使用的操作來說，復雜一點的實現帶來的時間上的優化是值得的。

散列沖突

不同鍵名的哈希值通過散列計算得到的「映射表」下標有可能相同，此時便發生了散列沖突。對于這種情況 PHP 使用了「鏈地址法」解決。下圖是訪問發生散列沖突的元素的情況：

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

插入元素

插入元素的函數 _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)))?{?//?數組未初始化
		//?初始化數組
		CHECK_INIT(ht,?0);
		//?跳轉至插入元素段
		goto?add_to_hash;
	}?else?if?(ht-&gt;u.flags?&amp;?HASH_FLAG_PACKED)?{?//?數組為連續數字索引數組
		//?轉換為關聯數組
		zend_hash_packed_to_hash(ht);
	}?else?if?((flag?&amp;?HASH_ADD_NEW)?==?0)?{?//?添加新元素
		//?查找鍵名對應的元素
		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;
				}
				//?確定當前值和新值不同
				ZEND_ASSERT(&amp;p-&gt;val?!=?pData);
				//?data?指向原數組成員值
				data?=?&amp;p-&gt;val;
				if?(Z_TYPE_P(data)?==?IS_INDIRECT)?{?//?原數組元素變量類型為間接類型
?					//?取間接變量對應的變量
					data?=?Z_INDIRECT_P(data);
					if?(Z_TYPE_P(data)?!=?IS_UNDEF)?{?//?該對應變量存在則直接返回
						return?NULL;
					}
				}?else?{?//?非間接類型直接返回
					return?NULL;
				}
			
			}?else?{?//?沒有指定?add?操作
				//?確定當前值和新值不同
				ZEND_ASSERT(&amp;p-&gt;val?!=?pData);
				//?data?指向原數組元素值
				data?=?&amp;p-&gt;val;
				//?允許更新間接類型變量則?data?指向對應的變量
				if?((flag?&amp;?HASH_UPDATE_INDIRECT)?&amp;&amp;?Z_TYPE_P(data)?==?IS_INDIRECT)?{
					data?=?Z_INDIRECT_P(data);
				}
			}
			if?(ht-&gt;pDestructor)?{?//?析構函數存在
				//?執行析構函數
				ht-&gt;pDestructor(data);
			}
			//?將?pData?的值復制給?data
			ZVAL_COPY_VALUE(data,?pData);
			return?data;
		}
	}
	//?如果哈希表已滿，則進行擴容
	ZEND_HASH_IF_FULL_DO_RESIZE(ht);

add_to_hash:
	//?數組已使用?Bucket?數?+1
	idx?=?ht-&gt;nNumUsed++;
	//?數組有效元素數目?+1
	ht-&gt;nNumOfElements++;
	//?若內部指針無效則指向當前下標
	if?(ht-&gt;nInternalPointer?==?HT_INVALID_IDX)?{
		ht-&gt;nInternalPointer?=?idx;
	}
????
	zend_hash_iterators_update(ht,?HT_INVALID_IDX,?idx);
	//?p?為新元素對應的?Bucket
	p?=?ht-&gt;arData?+?idx;
	//?設置鍵名
	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);
	}
	//?計算鍵名的哈希值并賦值給?p
	p-&gt;h?=?h?=?ZSTR_H(key);
	//?將?pData?賦值該?Bucket?的?val
	ZVAL_COPY_VALUE(&amp;p-&gt;val,?pData);
	//?計算映射表下標
	nIndex?=?h?|?ht-&gt;nTableMask;
	//?解決沖突，將原映射表中的內容賦值給新元素變量值的?u2.next?成員
	Z_NEXT(p-&gt;val)?=?HT_HASH(ht,?nIndex);
	//?將映射表中的值設為?idx
	HT_HASH(ht,?nIndex)?=?HT_IDX_TO_HASH(idx);

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

登錄后復制

?擴容

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

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

?總結

嗯哼，本文就到此結束了，因為自身水平原因不能解釋的十分詳盡清楚。這算是我寫過最難寫的內容了，寫完之后似乎覺得這篇文章就我自己能看明白/(ㄒoㄒ)/~~因為文筆太辣雞。想起一句話「如果你不能簡單地解釋一樣東西，說明你沒真正理解它。」PHP 的源碼里有很多細節和實現我都不算熟悉，這篇文章只是一個我的 PHP 底層學習的開篇，希望以后能夠寫出真正深入淺出的好文章。