php底层HashTable的实现

codeKK 发布于2019-07-01 14:12 / 3008人阅读

摘要：底层的实现有两个非常重要的结构分别是和。简单来说就是哈希表的结构维护了哈希表中插入元素的先后顺序，哈希表结构维护了整个哈希表的头和尾。在操作哈希表的过程中始终保持预算之间的关系。

HashTable对PHP来说是一种非常重要的数据结构。很多PHP的内部实现（变量的作用域，函数表，类的属性、方法，数组）就是通过HashTable来实现的。最近了解了一下PHP底层HashTable的实现。
PHP底层HashTable的实现有两个非常重要的结构分别是:HashTable和Bucket。
先说一下HashTable结构:
HashTable的底层实现代码如下:

typedef struct _hashtable{
    uint nTableSize;         // hash Bucket的大小，最小为8
    uint nTableMask;         //nTableSize - 1, 索引取值的优化
    uint nNumofElements      // bucket 里面存的总数 
    ulong nNextFreeElement   //下一个数字索引的位置
    Bucket *pInternalPointer  //当前遍历的指针(foreach比较快的原因)
    Bucket *pListHead         //整个hashtable的头指针
    Bucket *pListTail         //整个hashTable的尾指针
    Bucket **argBuckets       // Buceket 数组，用来存储数据
    doctor_func_t pDestructor //删除元素时的回调函数，用于资源的释放
    zend_bool persistent      //Bucket的内存分配方式，true使用系统的分配函数，false 使用php的内存分配函数
    unsigned char nApplyCount //标记当前hash bucket 被递归的次数
    zend_bool bApplyProtection 
#if ZEND_DEBUG
    int inconsistent           
#endif 
}HashTable

建议不太了解hash数据结构的同学先简单了解一下hash结构。
简单说一下php中hashtable的初始化操作:
代码如下：

 ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
    uint i = 3;
    //...
    if (nSize >= 0x80000000) {
        /* prevent overflow */
        ht->nTableSize = 0x80000000;
    } else {
        while ((1U << i) < nSize) {
            i++;
        }
        ht->nTableSize = 1 << i;
    }
    // ...
    ht->nTableMask = ht->nTableSize - 1;

    /* Uses ecalloc() so that Bucket* == NULL */
    if (persistent) {
        tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
        if (!tmp) {
            return FAILURE;
        }
        ht->arBuckets = tmp;
    } else {
        tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
        if (tmp) {
            ht->arBuckets = tmp;
        }
    }

    return SUCCESS;
}

最开始判断需要初始化的hashtable大小是不是超过了系统能使用的最大大小。下面是对tablesize大小的一个处理。将用户自定义的大小改成需要的大小。例如:如果用户定义的hashtable大小是6，那初始化时，就会将6变成8，如果用户定义的大小为11，那初始化后的Hashtable的大小为16.
下面就是一个简单的判断，来决定是按照C语言本身的分配内存函数来分配内存，还是根据php封装好的内存分配函数来分配内存。

再谈一下 bucket的结构

typedef struct bucket{
    ulong h;       //对key索引以后的值，数字key不做kash
    uint nKeyLength; //key的长度
    void *pData;     
    void *pDataPtr;   //指针数据，指向真实数据
    struct bucket * pListNext; //整个hash表的下个元素
    struct bucket *pListLast;   //整个hash表的上个元素
    struct bucket *pNext;       //本bucket里面，下一个元素
    struct bucket *pLast;       //本bucket里面的上一个元素
    char arKey[1];
}Bucket

这里用一张网络上的很火的图来说明(图原地址没找到，没有做来源说明):

下面是引用了tipi里面的插入说明:
引用地址:tipi

如图中左下角的假设，假设依次插入了Bucket1，Bucket2，Bucket3三个元素：

1、插入Bucket1时，哈希表为空，经过哈希后定位到索引为1的槽位。此时的1槽位只有一个元素Bucket1。其中Bucket1的pData或者pDataPtr指向的是Bucket1所存储的数据。此时由于没有链接关系。pNext， pLast，pListNext，pListLast指针均为空。同时在HashTable结构体中也保存了整个哈希表的第一个元素指针，和最后一个元素指针，此时HashTable的pListHead和pListTail指针均指向Bucket1。
2、插入Bucket2时，由于Bucket2的key和Bucket1的key出现冲突，此时将Bucket2放在双链表的前面。由于Bucket2后插入并置于链表的前端，此时Bucket2.pNext指向Bucket1，由于Bucket2后插入。 Bucket1.pListNext指向Bucket2，这时Bucket2就是哈希表的最后一个元素，这是HashTable.pListTail指向Bucket2。3、插入Bucket3，该key没有哈希到槽位1，这时Bucket2.pListNext指向Bucket3，因为Bucket3后插入。同时HashTable.pListTail改为指向Bucket3。
简单来说就是哈希表的Bucket结构维护了哈希表中插入元素的先后顺序，哈希表结构维护了整个哈希表的头和尾。在操作哈希表的过程中始终保持预算之间的关系。

云服务器 GPU云服务器 php的数组底层实现 hashtable实现底层实现 php底层库

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31884.html

php底层原理之类和对象

摘要：所以想要理解更深入的同学最好查看下我之前的关于介绍变量函数的文章类的数据结构不管是普通类还是抽象类或是接口，都存放到统一的结构体中，并且在生成中间代码时，会将此类添加到全局类列表中。对于PHPer来说，OOP是不可或缺的开发思维，但是你对php类和对象的底层实现又了解多少呢？本着知其然且知其所以然的思想，让我们一起来寻找答案~ 类的底层实现可看作是之前我们讲过的变量、函数等的知识集合...

isaced 2019-07-01 12:42 评论0 收藏0
PHP_底层分析

摘要：将会产生强制分裂结构体结构体引用数组时的一些奇怪现象引用数组时的怪现象数组不会比较细致的检查，多维数组存在。因此，判断的时候，只会判断外面一层的结构体。中底层都离不开表。底层所有的变量都是放在中。 PHP编译特点编译型语言对于C语言，C++，编译成机器码(二进制)来运行。Java语言，把.java 编译成.class，称为bytecode(字节码)，由jvm来运行解释型语言解...

tomlingtm 2019-07-01 12:16 评论0 收藏0
【天赢金创】PHP7与Swoole

摘要：但在密集计算方面比等静态编译语言差几十倍甚至上百倍。一使用栈内存在引擎和扩展中，经常要创建一个的变量，底层就是一个指针。代码中创建的变量也进行了优化，直接在栈内存上预分配。应用层与底层在错误抛出的方式全部统一为异常。原文：http://rango.swoole.com/archives/440最近PHP官方终于发布了传说中的PHP7，虽然只是alpha版。PHP7号称是新一代的PHP...

MingjunYang 2019-06-27 11:34 评论0 收藏0
php底层原理之数组实现

摘要：数组是最常用的数据类型，同时容易上手也得益于其强大的数组，但是数组在中是如何实现的呢首先，我们还是先了解下相关的数据结构，为下面的内容打好基础哈希表哈希表，顾名思义，即将不同的关键字映射到不同单元的一种数据结构。数组是PHPer最常用的数据类型，同时php容易上手也得益于其强大的数组，但是数组在php中是如何实现的呢？首先，我们还是先了解下相关的数据结构，为下面的内容打好基础哈希...

HackerShell 2019-07-01 12:38 评论0 收藏0
php中的哈希碰撞以及防御

php中的哈希表 php中的变量是以符号表的方式进行存储的，实际上也是个HashTable，哈希表是通过特定的哈希算法将索引转换成特定的index然后映射到对应的槽中，然后采用拉链法，在一个槽中使用链表将数据进行存储，链表的时间复杂度为O(n)。 php中的hashtable的结构定义在Zend/zend_hash.h文件中： //保存数据的单链表结构 typedef struct bucket ...

周国辉 2019-06-27 15:26 评论0 收藏0