5.1.1 数组的语义
本质上,PHP数组是一个有序的字典。
字典:使用HashTable来存储键-值对
有序:通过额外的代码设置保证有序
PHP的数组zend_array对应的是HashTable。HashTable是哈希表(也叫散列表),也是一种通过某种哈希函数将特定的键映射到特定值的一种数据结构,它维护着键和值的一一对应关系,查找效率为O(1)。
key:键
value:值,目标数据
bucket:桶,HashTable中存储数据的单元。用来存储key和value以及辅助信息的容器
slot:槽,HashTable有多个槽,一个bucket必须从属于具体的某个slot,一个slot下可以有多个bucket
哈希函数:需要自己实现,在存储的时候,会对key应用哈希函数确定所在的slot
哈希冲突:当多个key经过哈希计算后,得出的slot位置是同一个,那么就叫做哈希冲突。
解决冲突方法:
1.链地址法(PHP采用的是链地址法,即将同一个slot中的bucket通过链表连接起来)
2.开放地址法
PHP具体实现中,对bucket以及哈希函数做了一些补充
1.bucket增加h值
2.增加了hash1函数以生成h值,通过hash2函数散列到不同的slot
3.bucket里面的key作为字符串key,不在表示字符串key
h值的作用:
1.HashTable里面的key可能是数字,也可能是字符串,所以bucket在设计key的时候,需要做拆分,拆分成数字key或字符串key。h代表数字key,key代表字符串key。实际上,对于对于数字key,hash1没有做任何事情,h值就是数字key
2.每个字符串key都会生成一个h值,这个h值可以加快字符串key之间的比较速度。如果比较字符串key1和key2是否相等,会先比较key1和key2的h值是否相等,如果相等,再去比较字符串的长度与内容。在大部分场景,不同字符串生成的h值不会发生碰撞,这大大提高了hashTable的插入、查找速度