当前位置：首页 > PHP

php hash table 实现

2026-03-13 05:55:29PHP

PHP 哈希表实现

PHP 内部使用哈希表（HashTable）作为核心数据结构，用于实现数组、对象属性表等。哈希表在 PHP 源码中通过 zend_array（即 HashTable 结构体）实现。

哈希表结构

PHP 的哈希表实现主要包含以下关键组件：

桶（Bucket）：存储实际键值对的结构，包含哈希值、键、值及链表指针。
哈希函数：将键转换为哈希值，PHP 默认使用 DJBX33A 算法。
冲突解决：采用链地址法（拉链法），哈希冲突的桶通过链表连接。

哈希表的核心定义在 Zend/zend_types.h 和 Zend/zend_hash.h 中：

typedef struct _zend_array HashTable;
struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,
                zend_uchar    reserve)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask;
    Bucket           *arData;      // 存储桶数组
    uint32_t          nNumUsed;    // 已用桶数
    uint32_t          nNumOfElements; // 有效元素数
    uint32_t          nTableSize;  // 哈希表大小（总是 2^n）
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

哈希表操作

插入元素

计算键的哈希值：hash = zend_string_hash_val(key)。
根据哈希值确定桶的位置：idx = hash & nTableMask。
若发生冲突，将新桶插入链表头部。
更新哈希表的元信息（如 nNumUsed）。

查找元素

计算键的哈希值。
定位到桶的位置，遍历链表比对键值。
返回匹配的桶或 NULL。

扩容机制

当哈希表的负载因子（元素数/桶数）超过阈值时，触发扩容：

新容量为当前容量的 2 倍（new_size = nTableSize << 1）。
重新分配 arData 内存，并重建哈希索引。

示例代码（简化版）

以下是一个简化版的哈希表实现逻辑：

php hash table 实现

// 插入操作示例
void zend_hash_insert(HashTable *ht, zend_string *key, zval *value) {
    uint32_t hash = zend_string_hash_val(key);
    uint32_t idx = hash & ht->nTableMask;
    Bucket *p = ht->arData + idx;

    // 遍历冲突链
    while (p->key != NULL) {
        if (p->key == key || zend_string_equals(p->key, key)) {
            // 键已存在，更新值
            p->val = *value;
            return;
        }
        p = p->next;
    }

    // 新插入桶
    p->key = key;
    p->val = *value;
    p->next = ht->arData[idx].next;
    ht->arData[idx].next = p;
    ht->nNumUsed++;
}