PHP 数组的底层主要是通过 HashTable 实现，HashTable 通过映射函数或者散列函数将 String Key 转换成一个普通的数字下标，然后再将 Value 值存储到下标对应的数组元素中
HashTable 主要包含两部分：1.存储元素的数组 2.散列函数或者映射函数
随机访问
如果我们指定一个 Key=>Value 的映射关系，Key 是一个 String 类型的，则先通过 Time 33 算法将 String 转换成一个 Int 整型，然后再通过 PHP 里面特定的散列算法映射成 Bucket 数组中的一个下标，将 Value 值存储到对应的下标元素中，当我们通过 Key 访问数组元素时，只需要再通过相同的算法计算出对应的 Key,就能实现随机访问数组元素
顺序访问
存储在 HashTable 中的数组是无序的，但是 PHP 中的数组是有序的，为了实现 HashTable 的有序性，PHP 引入了一个中间映射表，该表是一个大小和 Bucket 数组相同的数组，数组中存放的是整形数据，主要用于存放元素实际存储的 Value 的下标值，当引入中间映射表之后，Bucket 中的数据是有序的，而中间映射表中的数据是无序的，当我们顺序访问的时候只需要遍历 Bucket 中的数据即可
Hash 冲突
PHP 解决 Hash 冲突采用的是链地址法，将出现冲突的 Bucket 串成链表，这样通过中间映射表映射出来的就不再是一个元素而是一个链表，通过散列函数定位到对应的 Bucket 链表时，需要遍历链表，逐个对比 key 值，直至找出对应的目标值
PHP 实现扩容
1.当删除的元素所占比例超出阈值的时候，则需要移除已经被逻辑删除的 Bucket,将后面的 Bucket 补位到前面，因为 Bucket 的下标发生了变动，所以需要更新每元素在中间映射表中实际存储的下标值
2.当没有超出阈值的时候，PHP 会申请一个大小是原来两倍的新数组，并将旧数组中的数据复制到新数组中，因为数组长度发生了变化，所以 key->value 的映射关系需要重新计算，这个就是重建索引
网友评论