结构定义
HashTable结构定义在zend_types.h中
1 |
|
重要的几个字段:
nTableSize: 哈系表最多容纳元素数量,归整为2的幂。
nTableMask: 掩码, 对key求哈系得到的值h, h | nTableMask得到偏移量。 |
arData:存储实际数据。
arData指向的数据实际分为两部分,Hash部分和Data部分。
1 |
|
—————–Hash部分———————— | ——————-Data部分——————– |
{Hash部分}{arData指针}{Data部分}。
哈希运算不可避免会产生冲突,有两个以上的key映射到同一位置, PHP采用的是链地址法,即把冲突的键值用链表连接起来。链地址法会有内存碎片,还需要不断分配释放内存,所以这里直接分配了nTableSize个Bucket空间,存放所有的key-val对。
所以这里分配了两个空间,Data部分存储key-val对,Hash部分存储映射对某个位置的元素链表的头部。
初始化
zend_hash_init对HashTable进行初始化赋值。这是一个宏,实际调用_zend_hash_init.
ht->nTableSize存放取整后的nSize,此时没有为哈希表元素分配内存。 添加元素时通过ht->u.flags & HASH_FLAG_INITIALIZED判断为false时分配内存。
zend_hash_check_size(nSize) 将nsize取整为2的幂。
1 |
|
第一次向表中添加元素时调用, 分配空间。
1 |
|
查找元素
HashTable如何查找元素:
1 |
|
添加元素
通过_zend_hash_add_or_update_i添加元素。
1 |
|