哈希表结构
先看看哈希表的结构
PHP的GC(内存回收)机制就是根据nNumOfElements大小来进行判断,当采取unset()时,该字段的值减一,在字段值为0时进行内存回收
首先初始化HashTable的大小为8
初始化
|
|
例如如果设置初始大小为10,则上面的算法将会将大小调整为16。也就是始终将大小调整为接近初始大小的2的整数次方。
为什么会做这样的调整呢?我们先看看HashTable将哈希值映射到槽位的方法,上一小节我们使用了取模的方式来将哈希值映射到槽位,例如大小为8的哈希表,哈希值为100, 则映射的槽位索引为: 100 % 8 = 4,由于索引通常从0开始,所以槽位的索引值为3,在PHP中使用如下的方式计算索引:
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
从上面的_zend_hash_init()函数中可知,ht->nTableMask的大小为ht->nTableSize -1。这里使用&操作而不是使用取模,这是因为是相对来说取模操作的消耗和按位与的操作大很多。
Bucket结构
|
|
如上面各字段的注释。h字段保存哈希表key哈希后的值。这里保存的哈希值而不是在哈希表中的索引值,这是因为索引值和哈希表的容量有直接关系,如果哈希表扩容了,那么这些索引还得重新进行哈希在进行索引映射,这也是一种优化手段。在PHP中可以使用字符串或者数字作为数组的索引。数字索引直接就可以作为哈希表的索引,数字也无需进行哈希处理。h字段后面的nKeyLength字段是作为key长度的标示,如果索引是数字的话,则nKeyLength为0。在PHP数组中如果索引字符串可以被转换成数字也会被转换成数字索引。所以在PHP中例如’10’,’11’这类的字符索引和数字索引10, 11没有区别。
HashTable接口的调用
这里介绍的是插入操作,对于数组的添加操作,其最终调用的都是该接口
所以这里主要针对插入接口进行介绍
- 生成hash值,通过与nTableMask执行与操作,获取在arBuckets数组中的Bucket。
- 如果Bucket中已经存在元素,则遍历整个Bucket,查找是否存在相同的key值元素,如果有并且是update调用,则执行update数据操作。
- 创建新的Bucket元素,初始化数据,并将新元素添加到当前hash值对应的Bucket链表的最前面(CONNECT_TO_BUCKET_DLLIST)。
- 将新的Bucket元素添加到数组的链接表的最后面(CONNECT_TO_GLOBAL_DLLIST)。
- 将元素个数加1,如果此时数组的容量满了,则对其进行扩容。这里的判断是依据nNumOfElements和nTableSize的大小。如果nNumOfElements > nTableSize则会调用zend_hash_do_resize以2X的方式扩容(nTableSize << 1)。
更多HashTable的具体接口操作可以查看上一节内容