详解PHP中Array结构HashTable
我们知道PHP中的Array在内部是以Hash的结构进行存储的。本文主要重点也是对PHP中Array的静态结构和动态结构进行分析和记录。
这里的静态结构，是指存储PHP中Array数据时使用的数据结构，即所谓的HashTable。
动态结构，是指程序在运行过程中，Array数据的存储状态。
?
首先PHP中的hashTable的结构如下：
#define CONNECT_TO_GLOBAL_DLLIST(element, ht) \ (element)->pListLast = (ht)->pListTail; \ (ht)->pListTail = (element); \ (element)->pListNext = NULL; \ if ((element)->pListLast != NULL) { \ (element)->pListLast->pListNext = (element); \ } \ if (!(ht)->pListHead) { \ (ht)->pListHead = (element); \ } \ if ((ht)->pInternalPointer == NULL) { \ (ht)->pInternalPointer = (element); \ }?关于这一步会对HashTable的内容有什么样的影响，请参看下面的动态示例。相信你也懂得。
?
?
?
动态示例：
现在我们假设数组中没有任何元素，则进行插入操作。现在我们按照代码的逻辑，手动模拟一下数据插入的过程：
?
1.
插入第一个元素A,假设其key对应的hash值为1
则插入之后，内存中的状态如下：
?
HashTable.arBucket[1]=A;
HashTable.pListHead = A
HashTable.pListTail = A
HashTable.pInternalPointer = A
A.pNext = null
A.pLast = null
A.pListLast = null
A.pListNext = null
?
2.
插入第二个元素B，假设其key对应的hash值为2
则插入之后内存的状态如下：
HashTable.arBucket[2] = B;
HashTable.pListHead = A
HashTable.pListTail = B
HashTable.pInternalPointer = A?????? //这个只在第一次的时候设置
A.pNext=null
A.pLast = null
A.pListNext = B
A.pListLast = null
B.pListLast = A
B.pListNext = null
B.pNext = null
B.pLast = null
?
3.
插入第三个元素C，假设其key的hash值为1，和A相同
则插入之后内存状态如下：
HashTable.arBucket[1] = C;
HashTable.pListHead = A
HashTable.pListTail =C
HashTable.pInternalPointer = A?????? //这个只在第一次的时候设置
A.pNext=null
A.pLast = C
A.pListNext = B
A.pListLast = null
?
B.pNext = null
B.pLast = null
B.pListLast = A
B.pListNext = C
C.pNext = A
C.pLast = null
C.pListNext = null
C.pListLast = B
?
插入A，B，C三个值之后的内存中状态即为：
HashTable.arBucket[1] = C;
HashTable.pListHead = A
HashTable.pListTail =C
HashTable.pInternalPointer = A
A.pNext=null
A.pLast = C
A.pListNext = B
A.pListLast = null
?
B.pNext = null
B.pLast = null
B.pListLast = A
B.pListNext = C
C.pNext = A
C.pLast = null
C.pListNext = null
C.pListLast = B
?
OK，A、B、C三个元素都已插入了，现在我们要实现两个任务：
?
1.
查找某key的元素值(value)：
如果我们要访问A元素，则提供A的key：key_a,得到对应的hash值为1
然后找HastTable.arBucket[1]。这时HastTable.arBucket[1]其实为C不是A，但由于C的key不等于A的key，因此，要沿着pNext的指针找下去，直到NULL，而此时C.pNext就是A，即找到了key_a对应的值A。
总之由key查找一个元素时，首先要hash，然后顺着hash后的索引位置的pNext指针一直找下去，直到NULL，如果遇到了和要查找的key相同的值，则找到，否则找不到。
?
2.
遍历数组：
由于我们的例子中的key是字符串类型的，全部循环遍历不能用for。只能用foreach，那foreach的遍历是如何实现的呢？
?
简单，根据最后的HashTable的状态，我们从HastTable.pListHead开始沿着pListNext指针顺序找下去即可了。以本文例子为例，则结果为：
?
?
HashTable.pListHead====>A
A.pListNext?????????????????? ====>B
B.pListNext?????????????????? ====>C
?
则最后的遍历顺序就是A，B，C，发现foreach的遍历顺序是和元素插入到数组的顺序相关的。
?
?
如果插入的元素的key不是字符串，而是数值。则可以省去做计算hash值这一步，直接拿数值的key做为hash值使用。
这样就不存在hash冲突的问题，这样也就不会用到每个元素的pNext、pLast两个指针了，这两个指针都只会是NULL。
?
这样我们可以通过使用for循环来遍历数组了，因为不存在hash冲突。
?
同样，如果我们使用foreach来遍历数组的话，遍历顺序还是元素的插入顺序，这个你当然懂得。
?
?
ps：
本文并未对zend中的hash结够做全面的记录，只是对本文主题涉及到的逻辑的重点代码进行了分析和演示。同时也为了能抓住重点。有些代码并未列出，如：再hash的逻辑，和索引为数值类型数据的代码等。这些可在代码文件Zend/zend_hash.c中找到详细内容。
?