概述
php数组原理大概是这样的：
首先有个散列表，然后通过“times 33”hash算法计算key得到一个整形值，把key存在这个位置上；然后要找到这个位置的是，只需要计算key的整型值，与散列的总大小取模得到在散列表中的存储位置了。
由于key的散列表上，存有value的内存地址，所以很快就找到key对于的值了。
//Bucket：散列表中存储的元素
typedef struct _Bucket {
zval val; //存储的具体value，这里嵌入了一个zval，而不是一个指针
zend_ulong h; //key根据times 33计算得到的哈希值，或者是数值索引编号
zend_string *key; //存储元素的key
} Bucket;
//HashTable结构
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 reserve)
} v;
uint32_t flags;
} u;
uint32_t nTableMask; //哈希值计算掩码，等于nTableSize的负值(nTableMask = -nTableSize)
Bucket *arData; //存储元素数组，指向第一个Bucket
uint32_t nNumUsed; //已用Bucket数
uint32_t nNumOfElements; //哈希表有效元素数
uint32_t nTableSize; //哈希表总大小，为2的n次方
uint32_t nInternalPointer;
zend_long nNextFreeElement; //下一个可用的数值索引,如:arr[] = 1;arr["a"] = 2;arr[] = 3; 则nNextFreeElement = 2;
dtor_func_t pDestructor;
};arData
HashTable中一个非常重要的值arData，存着数组值和数组的key的散列表：
- 插入数组value元素时按顺序 依次插入 数组，比如第一个元素在arData[0]、第二个在arData[1]...arData[nNumUsed]，PHP数组的有序性正是通过arData保证的
- key的散列表，是在第一个value元素之前，分配内存时这个散列表与Bucket数组一起分配，因为arData这个值指向存储元素数组的第一个Bucket，所以可以通过arData[-1]、arData[-2]、arData[-3]......来访问到key散列表的位置；
所以，整体来看HashTable主要依赖arData实现元素的存储、索引。插入一个元素时先将元素按先后顺序插入Bucket数组，位置是idx，再根据key的哈希值映射到散列表中的某个位置nIndex，将idx存入这个位置；查找时先在散列表中映射到nIndex，得到value在Bucket数组的位置idx，再从Bucket数组中取出元素。比如：
$arr["a"] = 1;
$arr["b"] = 2;
$arr["c"] = 3;
$arr["d"] = 4;
unset($arr["c"]);对应的HashTable如下图所示
nNumUsed、nNumOfElements
nNumOfElements哈希表有效元素数，nNumUsed已用Bucket数。
当将一个元素从哈希表删除时并不会将对应的Bucket移除，而是将Bucket存储的zval修改为IS_UNDEF，也就是nNumOfElements数量减少，只有扩容时发现nNumOfElements与nNumUsed相差达到一定数量时才会将已删除的元素全部移除，重新构建哈希表，所以nNumUsed>=nNumOfElements。
哈希碰撞
哈希碰撞是指 不同的key 可能计算得到相同的哈希值(数值索引的哈希值直接就是数值本身)，但是这些值又需要插入同一个散列表。一般解决方法是将Bucket串成链表，查找时遍历链表比较key。
最理想的链表是 从上往下，或者从下往上的结构，现在因为有hash冲突 那么整个链表应该是从上往下，或者从下往上 而相同hashcode又在同一行像又拓展，所以key的hash表变成了以下这种方式。
扩容
散列表可存储的value数是固定的，当空间不够用时就要进行扩容了。
PHP散列表的大小为2^n，插入时如果容量不够则首先检查已删除元素所占比例，如果达到阈值，则将已删除元素移除，重建索引，如果未到阈值则进行扩容操作，扩大为当前大小的2倍，将当前Bucket数组复制到新的空间，然后重建索引。
参考
https://github.com/pangudashu/php7-internal/blob/master/2/zend_ht.md
评论 (0)