PHP7数组的底层实现示例(2)

Bucket 的数据结构如下：

typedef struct _Bucket {
  zval       val; // 存储的具体 value，这里是一个 zval，而不是一个指针
  zend_ulong    h;  // 数字 key 或字符串 key 的哈希值。用于查找时 key 的比较  
  zend_string   *key; // 当 key 值为字符串时，指向该字符串对应的 zend_string（使用数字索引时该值为 NULL），用于查找时 key 的比较
} Bucket;

到这里有个问题出现了：存储在散列表里的元素是无序的，PHP 数组如何做到按顺序读取的呢？

答案是中间映射表，为了实现散列表的有序性，PHP 为其增加了一张中间映射表，该表是一个大小与 Bucket 相同的数组，数组中储存整形数据，用于保存元素实际储存的 Value 在 Bucekt 中的下标。Bucekt 中的数据是有序的，而中间映射表中的数据是无序的。

而通过映射函数映射后的散列值要在中间映射表的区间内，这就对映射函数提出了要求。

映射函数

PHP7 数组采用的映射方式：

nIndex = h | ht->nTableMask;

将 key 经过 time33 算法生成的哈希值 h 和 nTableMask 进行或运算即可得出映射表的下标，其中 nTableMask 数值为 nTableSize 的负数。并且由于 nTableSize 的值为 2 的幂次方，所以 nTableMask 二进制位右侧全部为 0，保证了 h | ht->nTableMask 的取值范围会在 [-nTableSize, -1] 之间，正好在映射表的下标范围内。另外，用按位或运算的方法和其他方法如取余的方法相比运算速度较高，这个映射函数可以说设计的非常巧妙了。

散列（哈希）冲突

不同键名的通过映射函数计算得到的散列值有可能相同，此时便发生了散列冲突。

对于散列冲突有以下 4 种常用方法：

1.将散列值放到相邻的最近地址里

2.换个散列函数重新计算散列值

3.将冲突的散列值统一放到另一个地方