首先,我们还是先了解下相关的数据结构,为下面的内容打好基础
哈希表
哈希表,顾名思义,即将不同的关键字映射到不同单元的一种数据结构。而将不同关键字映射到不同单元的方法就叫做哈希函数
理想情况下,经过哈希函数处理,关键字和单元是会进行一一对应的;但是如果关键字值足够多的情况下,就容易出现多个关键字映射到同一单元的情况,即出现哈希冲突
哈希冲突的解决方案,要么使用链接法,要么使用开放寻址法
链接法
即当不同的关键字映射到同一单元时,在同一单元内使用链表来保存这些关键字
开放寻址法
即当插入数据时,如果发现关键字被映射到的单元存在数据了,说明发生了冲突,就继续寻找下一个单元,直到找到可用单元为止
而因为开放寻址法方案属于占用其他关键字映射单元的位置,所以后续的关键字更容易出现哈希冲突,因此容易出现性能下降
链表
既然上面提到了链表,这里我们简单聊一下链表的基础知识。链表分为很多种类型,常用的数据结构包括:队列,栈,双向链表等
链表,就是由不同的链表节点组成的一种数据结构。链表节点一般由元素+指向下一节点的指针组成。而双向链表,顾名思义,则是由指向上一节点的指针+元素+指向下一节点的指针组成
对于数据结构的内容,我们不过多展开,我们之后会有专门的内容去详细介绍数据结构
php数组
php解决哈希冲突的方式是使用了链接法,所以php数组是由哈希表+链表实现,准确来说,是由哈希表+双向链表实现。
内部结构-哈希表
HashTable结构体主要用来存放哈希表的基本信息
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
Bucket结构体则用于保存数据的具体内容
1 2 3 4 5 6 7 8 9 10 11 12 |
|
其中Bucket结构体内有指向用户数据的pData元素,其实是指向了之前我们介绍的变量zval结构体,这也是为什么当创建数组时,会出现数组元素+1的变量容器。
哈希表内部结构关系图
从上图我们可以看出,Bucket在存放数据的时候,如果存在哈希冲突,则将多个关键字映射到链表中,由此组成了双向链表
总结
今天,我们以数组作为切入点,简单了解了下基本的数据结构:哈希表和链表;并且了解了数组的底层实现,即哈希表+双向链表。其实哈希表作为php中最重要的数据结构,用处很广。变量的符号表,函数列表等都是用哈希表来存储的