PHP是一門入門容易，使用范圍廣泛的語言，以其靈活性以及web后端開發(fā)被很多人熟知，也被很多人戲稱“PHP是世界上最好的語言”。本人是一名“忠實”的PHPer，相信用過PHP的程序員都會體會到PHP數組的靈活性，相對傳統(tǒng)的C語言，使用起來很是方便，擁有關聯數組（key值可以是字符串），不需要預定義數組空間大小，關聯數組，不需要指定key的快速索引賦值等等便利方法，這段時間研究了一下PHP數組的底層結構，并總結分析，里面含有一些我自己的猜想，如有錯誤請指出。
1.PHP的數組底層結構
哈希結構是一種非常重要的數據結構，他是一種通過key映射到value的結構，由于其特性，可以在大部分的情況下讓查找和插入的效率達到O(1)，在很多語言或者系統(tǒng)里面都有顯性得體現出來，具體的實現思路有很多種。詳細的介紹可以看我的博客數據結構之哈希結構
PHP的數組是用鏈地址法的哈希結構去實現的，鏈表是雙向鏈表，這樣既可以動態(tài)分配數組空間，也可以通過key值去計算hash值去訪問對應的元素，是一種非常高效的數據結構。
下面是PHP ?Bucket的結構，Bucket是一個基本結點的結構，Bucket是以存放基本元素的容器，可以簡單理解為數組元素的房子。
下面是PHP ?HashTable結構，HashTable是用以存儲Bucket數組和Bucket信息的哈希表結構，采用雙向鏈表的拉鏈法結構。
可能首次去看數據結構可能會覺得有點難受，密密麻麻的一堆東西，下面我會一個個分析數據字段。
2.Bucket結構體
1.h（哈希值）
通過key映射的哈希值（未經過糾正）h，為了讓不同key值均勻分配到哈希表的各個位置，必須要有一個好的哈希函數，而PHP選用的是time33算法，也就是下面的算法（簡化版）。
當然啦在PHP的具體實現細節(jié)又會有點不同，但是原理是差不多的。
2.nKeyLength（字符的個數）
如果使用的是關聯索引，那么此處nKeyLength就是字符的個數，比如說$arr['key']='value' ，那么這個值就為3，如果是索引數組，此字段就不會用上。
3.pNext pLast?（記錄該桶的前后桶）
繼續(xù)引用百度的圖，類似于下面的哈希表，拿元素337來說，他的pNext指向353的位置，pLast指向1的位置，只不過下面是單向鏈表，沒有看到當前元素指向前一個元素。
4.pListNext（記錄該桶在數據上的后元素）
這個字段從命名意思就可以看出，是鏈表的指向后繼元素的指針。比如說作如下賦值。guangdong的pListNext指向beijing，beijing的pListNext指向shanghai.....
所以你如果用foreach去遍歷數組，會發(fā)現一個很有趣的現象。輸出的結果如下，居然不是按照數組下標1,2,3,4順序去輸出，其實只要你理解了PHP的存儲數組的數據結構你就很明白了。
他的數據結構如下圖顯示，第一個元素是guangdong，然后來個元素beijing，于是guangdong的pListLast指向beijing，后面的元素同理。而foreach遍歷會從第一個元素（也就是pListHead指向的Bucket，詳看下文HashTable的介紹）去輸出，然后再指向下一個元素，因此輸出的順序不是按照下標來的，而是按照賦值順序來的，這也是為什么foreach遍歷數組要比for遍歷要快的原因，因為for每次查找元素都要去做一次哈希映射查找對應下標的Bucket，而foreach只需要遍歷Bucket鏈表就好了。pListLast與pListNext同理，只是指向前一個數組元素。
5.arKey(用以存儲key值)
這是一個c99柔性成員，如果需要深究可以百度查查c的柔性成員，如果這一個關聯數組，這個arKey就是存儲對應的key值。$arr['abc']='value';那么arKey存儲的就是abc。
3.HashTable結構體
1.nTableSize(哈希表的大小)
這是哈希表的分配Bucket空間的大小，默認會分配8個Bucket空間，當存儲元素個數大于8個就會存儲16個，如此下去，存儲的個數為2x大小，即8,16,32,64...
2.nTableMask(糾正掩碼)
用以糾正過長的哈希值，值為nTableSize-1，比如說一個我有一個字符經過哈希函數得出值為9，但是nTableSize為8，那該怎么辦呢，存放到第1個位置吧，計算方法就是9 mod 8，但是在計算機里面下標是從0開始，因此我們會使用&運算得出結果，9&7=1。
3.nNumOfElements(數組元素個數)
用以統(tǒng)計數組元素的個數，PHP的count()元素其實就是獲取這個值。
4.NextFreeElement(下一個空閑的元素)
用以存儲下一個空閑的元素的值。當你的數組是索引數組，用到$arr[]=value賦值就會用到，如果你上次賦值的元素下標是100，那么NextFreeELement就為101了。無關你的元素個數。
5.pListHead(鏈表的頭部元素)
這個Bucket指針從名字就可以看出來，用以指向鏈表的頭部元素，例如你給一個數組第一次附上一個值$arr[]=value1，那么這個指針就是指向value1。
6.pListTail(鏈表的尾部元素)
原理同上，只是指向尾部元素，每次來一個新的數組元素，pListTail就會指向它。
7.nInternalPointer(用以指向內部指向的元素)
如果我們用foreach遍歷數組，這個指針就會指向當前遍歷的元素，用以保存當前指向記錄。用到此項的還有current()，next()，prev()函數。
8.arBuckets(用以存儲Bucket在C的內部數組)
此項為指針的指針，可以用于操作Bucket數組。
下面列出一副圖來說明PHP的數組結構（為版面清晰忽略了兩種指向前一個Bucket的指針：pListLast，pLast）。
? 最后我大概猜想一下foreach函數的執(zhí)行過程，首先是將nInternalPointer指向HashTable的第一個Buckets，也就是pListHead，如果不為空則輸出該元素，然后nInternaPointer指向該Bucket的下一個元素，也就是pListNext，如此循環(huán)下去。
