说明
这里基于php7.2.5进行测试，php7之后内部结构变化应该不是太大，但与php5.X有差别。
我们今天学习PHP中的数组语法，数组在PHP中堪称万能结构，什么都能存什么都能放，非常灵活，因为PHP没有其他语言的如map、list等结构，PHParray就够了。
我们前面说变量的存储结构为zval, 值呢放在zend_value中，忘了的看这里
如何声明
<code>$arr = []; $arr[1
] ="hello"
; $arr1 = ['name'
=>'愤怒的鸟'
];/<code>
如何实现
数组的底层结构为zend_array 也叫HashTable，也就是通过对数组的key进行hash计算之后能直接获取value的地址，时间复杂度为O(1)那是很快的。
<code>typedef
struct
_zend_array
HashTable
;struct
_zend_array
{ zend_refcounted_h gc;union
{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; Bucket *arData;uint32_t
nNumUsed;uint32_t
nNumOfElements;uint32_t
nTableSize;uint32_t
nInternalPointer; zend_long nNextFreeElement;dtor_func_t
pDestructor; };typedef
struct
_Bucket
{ zval val; zend_ulong h; zend_string *key; } Bucket; /<code>
我们知道数组的key可以是数字或者字符串，但是PHP中的数组是有序的，也就是跟插入顺序是保持一致的，那么是如何做到的。
结论：key在存入bucket之前先通过一个中间映射表保存key的位置，先对key进行hash计算然后与数组大小值进行取模运算得出这个key在中间表的位置，然后在中间表的位置存储这个key在bucket中的位置。如图
这里在key是字符串的时候需要进行hash计算，如果是数值就直接拿来用就行了。
插入元素
这个操作比较明晰了，先计算中间表的位置，再存储到bucket
<code>add_to_hash: idx = ht->nNumUsed++; ht->nNumOfElements++;if
(ht->nInternalPointer == HT_INVALID_IDX) { ht->nInternalPointer = idx; } zend_hash_iterators_update(ht, HT_INVALID_IDX, idx); p = ht->arData + idx; p->key = key;if
(!ZSTR_IS_INTERNED(key)) { zend_string_addref(key); ht->u.flags &= ~HASH_FLAG_STATIC_KEYS; zend_string_hash_val(key); } p->h = h = ZSTR_H(key); ZVAL_COPY_VALUE(&p->val, pData); nIndex = h | ht->nTableMask; Z_NEXT(p->val) = HT_HASH(ht, nIndex); HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);return
&p->val;/<code>
查找元素
先自己思考一下我们在获取数组的值$a['name'],是如何获取的，先用key计算hash值，拿到中间表的位置，再拿到bucket的位置，就能取到值了
<code> h = zend_string_hash_val(key); arData = ht->arData; nIndex = h | ht->nTableMask; idx = HT_HASH_EX(arData, nIndex);while
(EXPECTED(idx != HT_INVALID_IDX)) { p = HT_HASH_TO_BUCKET_EX(arData, idx);if
(EXPECTED(p->key == key)) {return
p; }else
if
(EXPECTED(p->h == h) && EXPECTED(p->key) && EXPECTED(ZSTR_LEN(p->key) == ZSTR_LEN(key)) && EXPECTED(memcmp(ZSTR_VAL(p->key), ZSTR_VAL(key), ZSTR_LEN(key)) ==0
)) {return
p; } idx = Z_NEXT(p->val); }/<code>
hash冲突
hash计算不可避免的在数据量大的时候有冲突的几率，一般一个常用方法是拉链法，也就是冲突元素串成链表，当keyhash冲突后遍历这个位置的链表，最终拿到匹配的key, 也就是上面的查找元素中while那一段，来看下PHP hashTable是如何处理的，我们还是分析上面那一段代码
<code>add_to_hash: idx = ht->nNumUsed++; ht->nNumOfElements++;if
(ht->nInternalPointer == HT_INVALID_IDX) { ht->nInternalPointer = idx; } zend_hash_iterators_update(ht, HT_INVALID_IDX, idx); p = ht->arData + idx; p->key = key;if
(!ZSTR_IS_INTERNED(key)) { zend_string_addref(key); ht->u.flags &= ~HASH_FLAG_STATIC_KEYS; zend_string_hash_val(key); } p->h = h = ZSTR_H(key); ZVAL_COPY_VALUE(&p->val, pData); nIndex = h | ht->nTableMask; Z_NEXT(p->val) = HT_HASH(ht, nIndex); HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);return
&p->val; ((uint32_t*)(data))[(int32_t)(idx)] HT_HASH_EX((ht)->arData, idx)/<code>
上图
扩容
PHP数组在初始化时不需要指定容量大小，也就是它是自动扩容的，如何实现呢。
结论：如果插入元素时发现容量不够了，如果已删除的元素达到一定比例就重建索引，如果没有达到就会进行原大小2倍的扩容，然后复制元素到新数组。
<code>IS_CONSISTENT(ht); HT_ASSERT_RC1(ht);if
(ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >>5
)) { zend_hash_rehash(ht); }else
if
(ht->nTableSize < HT_MAX_SIZE) { void *new_data, *old_data = HT_GET_DATA_ADDR(ht); uint32_t nSize = ht->nTableSize + ht->nTableSize; Bucket *old_buckets = ht->arData; new_data = pemalloc(HT_SIZE_EX(nSize, -nSize), ht->u.flags & HASH_FLAG_PERSISTENT); ht->nTableSize = nSize; ht->nTableMask = -ht->nTableSize; HT_SET_DATA_ADDR(ht, new_data); memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed); pefree(old_data, ht->u.flags & HASH_FLAG_PERSISTENT); zend_hash_rehash(ht); }else
{ zend_error_noreturn(E_ERROR,"Possible integer overflow in memory allocation (%u * %zu + %zu)"
, ht->nTableSize *2
, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket)); }/<code>
总结
PHP数组底层是hashTable, 通过一个中间映射表实现顺序性，自动扩容，value可以任何类型，key可以是int也可以是string
参考资料：
《PHP内核剖析》
