散列表-PHP 数组底层实现原理（二）

数据结构与算法系列（二十五）

数组的初始化

数组的初始化主要是针对 HashTable 成员的设置，初始化时并不会立即分配 arData 的内存，插入第一个元素之后才会分配 arData 的内存。初始化操作可以通过 zend_hash_init 宏完成，最后由 _zend_hash_init_int 函数处理（该函数定义在 Zend/zend_hash.c 文件中）：

此时的 HashTable 只是设置了散列表的大小及其他成员的初始值，还无法用来存储元素。

插入数据

插入时会检查数组是否已经分配存储空间，因为初始化并没有实际分配 arData 的内存，在第一次插入时才会根据 nTableSize 的大小分配，分配以后会把 HashTable->u.flags 打上 HASH_FLAG_INITIALIZED 掩码，这样，下次插入时发现已经分配了就不会重复操作，这段检查逻辑位于 _zend_hash_add_or_update_i 函数中：

if (UNEXPECTED(!(HT_FLAGS(ht) & HASH_FLAG_INITIALIZED))) {
    zend_hash_real_init_mixed(ht);
    if (!ZSTR_IS_INTERNED(key)) {
        zend_string_addref(key);
        HT_FLAGS(ht) &= ~HASH_FLAG_STATIC_KEYS;
        zend_string_hash_val(key);
    }
    goto add_to_hash;
}

如果 arData 还没有分配，则最终由 zend_hash_real_init_mixed_ex 完成内存分配：

分配完 arData 的内存后就可以进行插入操作了，插入时先将元素按照顺序插入 arData，然后将其在 arData 数组中的位置存储到根据 key 的散列值与 nTableMask 计算得到的中间映射表中的对应位置：

上述只是最基本的插入处理，不涉及已存在数据的覆盖和清理。

哈希冲突

PHP 数组底层的散列表采用链地址法解决哈希冲突，即将冲突的 Bucket 串成链表。

HashTable 中的 Bucket 会记录与它冲突的元素在 arData 数组中的位置，这也是一个链表，冲突元素的保存位置不在 Bucket 结构中，而是保存在了存储元素 zval 的 u2 结构中，即 Bucket.val.u2.next，所以插入时分为以下两步：

// 将映射表中原来的值保存到新 Bucket 中，哈希冲突时会用到（以链表方式解决哈希冲突） Z_NEXT(p->val) = HT_HASH_EX(arData, nIndex); // 再把新元素数组存储位置更新到数据表中 // 保存idx：((unit32_t*))(ht->arData)[nIndex] = idx HT_HASH_EX(arData, nIndex) = HT_IDX_TO_HASH(idx);

数组查找

清楚了 HashTable 的实现和哈希冲突的解决方式之后，查找的过程就比较简单了：首先根据 key 计算出的散列值与 nTableMask 计算得到最终散列值 nIndex，然后根据散列值从中间映射表中得到存储元素在有序存储数组中的位置 idx，接着根据 idx 从有序存储数组（即 arData）中取出 Bucket，遍历该 Bucket，判断 Bucket 的 key 是否是要查找的 key，如果是则终止遍历，否则继续根据 zval.u2.next 遍历比较。

对应的底层源码如下：

删除数据

关于数组数据删除前面我们在介绍散列表中的 nNumUsed 和 nNumOfElements 字段时已经提及过，从数组中删除元素时，并没有真正移除，并重新 rehash，而是当 arData 满了之后，才会移除无用的数据，从而提高性能。即数组在需要扩容的情况下才会真正删除元素：首先检查数组中已删除元素所占比例，如果比例达到阈值则触发重新构建索引的操作，这个过程会把已删除的 Bucket 移除，然后把后面的 Bucket 往前移动补上空位，如果还没有达到阈值则会分配一个原数组大小 2 倍的新数组，然后把原数组的元素复制到新数组上，最后重建索引，重建索引会将已删除的 Bucket 移除。

对应底层代码如下：

除此之外，数组还有很多其他操作，比如复制、合并、销毁、重置等，这些操作对应的代码都位于 zend_hash.c 中，感兴趣的同学可以去看看。