笔记大全

一起学习PHP7内核之HashTable

更新时间：2023-12-30

什么是HashTable？

HashTable（哈希表）是一种键值对存储的数据结构，具有快速插入、查找、删除的优势，它将键映射到值。在PHP7中，Zend引擎使用了HashTable作为PHP的内存管理方式。

HashTable的实现方式

在 PHP 7 中，Zend引擎中的HashTable被设计成一个数字索引数组（Bucket），每个 Bucket 包含一个 zval 结构和一个字符串键（key）。


typedef struct _Bucket {
    zval value; // 值
    zend_ulong h; // 哈希值，采用的是DJBX33A算法
    zend_string *key; // 键，采用zfj_str_hash算法，将字符串转化为整型数值
    /* 当存储的是对象时，next指向双向链表下一个元素，只有同一Bucket中的元素，才会有指向Bucket下一个元素的指针 */
    struct _Bucket *next, *prev;
} Bucket;

一个 Hashtable 对象，实际上就是一个指向 Bucket 数组的指针。每个 Bucket 的 h 字段存储哈希值，并且均匀地分配在一个确定大小的数组（table）中。当不同的元素映射到同一个 Bucket 时，就会形成一个双向链表。

HashTable的增删改查

HashTable的增删改查均为O(1)复杂度的操作。在HashTable中，获取值、插入值、删除值的操作均可以使用HashTable提供的方法帮助进行，或是使用底层的C语言方法操作。

增加元素

HashTable提供了自己的元素增加方法zend_hash_add()：


#define SUCCESS 0
#define FAILURE -1

int zend_hash_add(HashTable *ht, zend_string *key, zval *value);

该函数将在哈希表中增加给定键名和识别符相对应的数据，其中ht是对哈希表的引用，key为新元素的键名，value为新元素的值。

删除元素

HashTable提供了自己的元素删除方法zend_hash_del()：


int zend_hash_del(HashTable *ht, zend_string *key);

该函数将删除哈希表中指定键名的元素。如果哈希表中没有指定的键名，则会由此函数返回 FAILURE。如果删除成功，则会返回 SUCCESS。

查找元素

HashTable提供了自己的元素查找方法zend_hash_find()：


int zend_hash_find(HashTable *ht, zend_string *key, zval **value);

该函数将在哈希表中查找给定键名和识别符所对应的数值，并将其返回到value变量中。如果找到相应数据，则会返回 SUCCESS。否则，函数将返回 FAILURE。

修改元素

HashTable提供了自己的元素修改方法zend_hash_update()：


int zend_hash_update(HashTable *ht, zend_string *key, zval *value);

该函数将在哈希表中修改给定键名和识别符相对应的数据。如果哈希表中没有指定的键名，则函数会返回 FAILURE。如果修改成功，则函数将返回 SUCCESS。

c语言编程笔录