PHP内核中的HashTable原理
简易的结构
|
|
这个是一个简化过的哈希表结构
Bucket是一个链表,而_HashTable用于存储hash值并指向真正的数据储存单位
解决冲突算法DJBX33A
而链表是为了解决冲突用的,冲突解决采用DJBX33A算法,算法的内容如下
HashTable的初始化
初始化,申请空间并且设置初始化值
HashTable的插入
插入函数,插入时验证key是否存在,存在更新value值,不存在并取发生冲突则创建新节点并插入到原有链表的头部
HashTable的扩容
当Hash表容量满了的时候,Hash表的性能会下降,这时候需要对Hash表进行扩容
先把原来Hash表容量变成两倍,然后对其进行重新插入操作,时间复杂度为O(n)
HashTable的查找
元素的查找和插入采取相同的策略,都是先获得hash值,然后取得bucket链表,随后比较键名进行查找