站長資訊網PHP數組的底層實現原理是：1、哈希表，將不同的關鍵字映射到不同單元的一種數據結構；2、鏈表，就是由不同的鏈表節點組成的一種數據結構；3、php數組，使用鏈接法解決哈希沖突的方式。
一、哈希表
哈希表，顧名思義，即將不同的關鍵字映射到不同單元的一種數據結構。而將不同關鍵字映射到不同單元的方法就叫做哈希函數
理想情況下，經過哈希函數處理，關鍵字和單元是會進行一一對應的；但是如果關鍵字值足夠多的情況下，就容易出現多個關鍵字映射到同一單元的情況，即出現哈希沖突
哈希沖突的解決方案，要么使用鏈接法，要么使用開放尋址法
鏈接法
即當不同的關鍵字映射到同一單元時，在同一單元內使用鏈表來保存這些關鍵字
開放尋址法
即當插入數據時，如果發現關鍵字被映射到的單元存在數據了，說明發生了沖突，就繼續尋找下一個單元，直到找到可用單元為止
而因為開放尋址法方案屬于占用其他關鍵字映射單元的位置，所以后續的關鍵字更容易出現哈希沖突，因此容易出現性能下降
二、鏈表
既然上面提到了鏈表，這里我們簡單聊一下鏈表的基礎知識。鏈表分為很多種類型，常用的數據結構包括：隊列，棧，雙向鏈表等
鏈表，就是由不同的鏈表節點組成的一種數據結構。鏈表節點一般由元素+指向下一節點的指針組成。而雙向鏈表，顧名思義，則是由指向上一節點的指針+元素+指向下一節點的指針組成
對于數據結構的內容，我們不過多展開，我們之后會有專門的內容去詳細介紹數據結構
三、php數組
php解決哈希沖突的方式是使用了鏈接法，所以php數組是由哈希表+鏈表實現，準確來說，是由哈希表+雙向鏈表實現
四、內部結構-哈希表
HashTable結構體主要用來存放哈希表的基本信息 typedef struct _hashtable { uint nTableSize; // hash Bucket的大小，即哈希表的容量，最小為8，以2x增長。 uint nTableMask; // nTableSize-1 ， 索引取值的優化 uint nNumOfElements; // hash Bucket中當前存在的元素個數，count()函數會直接返回此值 ulong nNextFreeElement; // 下一個可使用的數字鍵值 Bucket *pInternalPointer; // 當前遍歷的指針（foreach比for快的原因之一） Bucket *pListHead; // 存儲整個哈希表的頭元素指針 Bucket *pListTail; // 存儲整個哈希表的尾元素指針 Bucket **arBuckets; // 存儲hash數組 dtor_func_t pDestructor; // 在刪除元素時執行的回調函數，用于資源的釋放 zend_bool persistent; //指出了Bucket內存分配的方式。如果persisient為TRUE，則使用操作系統本身的內存分配函數為Bucket分配內存，否則使用PHP的內存分配函數。 unsigned char nApplyCount; // 標記當前hash Bucket被遞歸訪問的次數（防止多次遞歸） zend_bool bApplyProtection;// 標記當前hash桶允許不允許多次訪問，不允許時，最多只能遞歸3次 #if ZEND_DEBUG int inconsistent; #endif } HashTable;
Bucket結構體則用于保存數據的具體內容
typedef struct bucket { ulong h; // 對char *key進行hash后的值，或者是用戶指定的數字索引值 uint nKeyLength; // hash關鍵字的長度，如果數組索引為數字，此值為0 void *pData; // 指向value，一般是用戶數據的副本，如果是指針數據，則指向pDataPtr void *pDataPtr; // 如果是指針數據，此值會指向真正的value，同時上面pData會指向此值 struct bucket *pListNext; // 指向整個哈希表的該單元的下一個元素 struct bucket *pListLast; // 指向整個哈希表的該單元的上一個元素 struct bucket *pNext; // 指向由于哈希沖突導致存放在同一個單元的鏈表中的下一個元素 struct bucket *pLast; // 指向由于哈希沖突導致存放在同一個單元的鏈表中的上一個元素 // 保存當前值所對于的key字符串，這個字段只能定義在最后，實現變長結構體 char arKey[1]; } Bucket;
相關學習推薦：PHP編程從入門到精通
