笔者github上有一个简略单纯版的HashTable的实现：HashTable实现

在PHP内毫闼楝个一一个很重要的数据构培养是HashTable。我们常用的数组，在内核中就是用HashTable来实现。那么，PHP的HashTable是怎么实现的呢？比来在看HashTable的数据构造，然则算法书本琅绫擎没有具体的实现算法，刚好比来也在浏览PHP的源码，于是参考PHP的HashTable的实现，本身实现了一个简略单纯版的HashTable，总结了一些心得，下面给大年夜家分享一下。

别的，我在github有对PHP源码更具体的注解。感兴趣的可以围不雅一下，给个star。PHP5.4源码注解。可以经由过程commit记录查看已添加的注解。

HashTable的介绍

哈希表是实现字典操作的一种有效数据构造。

定义

简单地说，HashTable(哈希表)就是一种键值对的数据构造。支撑插入，查找，删除等操作。在一些合理的假设下，在哈希表中的所有操作的时光复杂度是O(1)(对相干证实感兴趣的可以自行查阅)。

实现哈希表的关键

static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength){         register ulong hash = 5381;        /* variant with the hash unrolled eight times */        for (; nKeyLength >= 8; nKeyLength -= 8) {            hash = ((hash << 5) + hash) + *arKey++;            hash = ((hash << 5) + hash) + *arKey++;            hash = ((hash << 5) + hash) + *arKey++;            hash = ((hash << 5) + hash) + *arKey++;            hash = ((hash << 5) + hash) + *arKey++;            hash = ((hash << 5) + hash) + *arKey++;            hash = ((hash << 5) + hash) + *arKey++;            hash = ((hash << 5) + hash) + *arKey++;    }    switch (nKeyLength) {        case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */        case 1: hash = ((hash << 5) + hash) + *arKey++; break;        case 0: break;        EMPTY_SWITCH_DEFAULT_CASE()    }    return hash;}

在哈希表中，不是应用关键字做下标，而是经由过程哈希函数计算出key的哈希值作为下标，然后查找/删除时再计算出key的哈希值，大年夜而快速定位元素保存的地位。
在一个哈希表中，不合的关键字可能管帐算获得雷同的哈希值，这叫做“哈希冲突”，就是处理两个或多个键的哈希值雷同的情况。解决哈希冲突的办法有很多，开放寻址法，拉链法等等。
是以，实现一个好的哈希表的关键就是一个好的哈希函数和处理哈希冲突的办法。
Hash函数
断定一个哈希算法的短长有以下四个定义：

一致性，等价的键必定产生相等的哈希值；

高效性，计算简便；

平均性，平均地对所有的键进行哈希。
哈希函数建立了关键值与哈希值的对应关系，即：h = hash_func(key)。对应关系见下图：
注：函数应用了一个8次轮回+switch来实现，是对for轮回的优化，削减轮回的运行次数，然后在switch琅绫擎履行剩下的没有遍历到的元素。

拉链法

将所有具有雷同哈希值的元素都保存在一条链表中的办法叫拉链法。查找的时刻经由过程先计算key对应的哈希值，然后根据哈希置魅找到对应的链表，最后沿着链表次序查找响应的值。
具体保存后的构造图如下：

构造图

PHP的HashTable构造

简单地介绍了哈希表的数据构造之后，持续看看PHP中是若何实现哈希表的。

PHP内核hashtable的定义：

例如，”foo”真正的哈希值（应用DJBX33A哈希函数）是193491849。如不雅我们如今有64容量的哈希表，我们明显不克不及应用它作为数组的下标。取而代之的是经由过程应用哈希表的mask，然后只取哈希表的低位。

typedef struct _hashtable {          uint nTableSize;          uint nTableMask;          uint nNumOfElements;          ulong nNextFreeElement;          Bucket *pInternalPointer;          Bucket *pListHead;          Bucket *pListTail;           Bucket **arBuckets;          dtor_func_t pDestructor;          zend_bool persistent;          unsigned char nApplyCount;          zend_bool bApplyProtection;          #if ZEND_DEBUG               int inconsistent;          #endif} HashTable;

nTableSize，HashTable的大年夜小，以2的倍数增长

nTableMask，用在与哈希值做与运算获得该哈希值的索引取值，arBuckets初始化后永远是nTableSize-1

nNumOfElements，HashTable当前拥有的元素个数，count函数直接返回这个值

nNextFreeElement，表示数字键值数组中下一?数字索引的地位
1/3 1 2 3 下一页尾页

　　推荐阅读

　　初识Rust语言的所有权概念

今朝仅看了第二版的官方文档，记录一下初步印象，应当还有更深刻一致的解释，程度有限，仅供参考。实验情况：ubuntu17.10，rust1.18，vscode1.14 + 扩大rust（rls）。BTW，情况搭建顺利得>>>详细阅读

本文标题：[PHP内核探索]PHP中的哈希表

地址：http://www.17bianji.com/lsqh/36437.html

1/2 1