• Zend 哈希表的内部实现

    数据结构与哈希算法
    服务器君一共花费 16.174 ms 进行了 4 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    数据结构

    PHP中使用一个叫Bucket的结构体表示桶(桶的相关参考Linux内核中的hash与bucket
    ),同一哈希值的所有桶被组织为一个单链表。哈希表使用HashTable结构体表示。相关源码在zend/Zend_hash.h下:

    typedef struct bucket {
    	/* Used for numeric indexing */
        ulong h;            // 对char *key进行hash后的值,或者是用户指定的数字索引值
        uint nKeyLength;    // hash关键字的长度,如果数组索引为数字,此值为0
        void *pData;        // 指向value,一般是用户数据的副本,如果是指针数据,则指向pDataPtr
        void *pDataPtr;     //如果是指针数据,此值会指向真正的value,同时上面pData会指向此值
        struct bucket *pListNext;   // 整个hash表的下一元素
        struct bucket *pListLast;   // 整个哈希表该元素的上一个元素
        struct bucket *pNext;       // 存放在同一个hash Bucket内的下一个元素
        struct bucket *pLast;       // 同一个哈希bucket的上一个元素
        char arKey[1];  
        /*存储字符索引,此项必须放在最未尾,因为此处只字义了1个字节,存储的实际上是指向char *key的值,
        这就意味着可以省去再赋值一次的消耗,而且,有时此值并不需要,所以同时还节省了空间。
        */
    } Bucket;
    
    typedef struct _hashtable { 
        uint nTableSize;        // hash Bucket的大小,最小为8,以2x增长。
        uint nTableMask;        // nTableSize-1 , 索引取值的优化
        uint nNumOfElements;    // hash Bucket中当前存在的元素个数,count()函数会直接返回此值 
        ulong nNextFreeElement; // 下一个数字索引的位置
        Bucket *pInternalPointer;   // 当前遍历的指针(foreach比for快的原因之一)
        Bucket *pListHead;          // 存储数组头元素指针
        Bucket *pListTail;          // 存储数组尾元素指针
        Bucket **arBuckets;         // 存储hash数组
        dtor_func_t pDestructor;
        zend_bool persistent;
        unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数(防止多次递归)
        zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问,不允许时,最多只能递归3次
    #if ZEND_DEBUG
        int inconsistent;
    #endif
    } HashTable;
    
    • HashTable结构体用于保存整个哈希表需要的基本信息,而Bucket结构体用于保存具体的数据内容。他们的字段名很清楚的表明其用途,注释上面也写得比较清楚了。

    重点明确下面几个字段:

    • Bucket中的“h”用于存储原始key;
    • HashTable中的nTableMask是一个掩码,一般被设为nTableSize - 1,与哈希算法有密切关系,后面讨论哈希算法时会详述;
    • arBuckets指向一个指针数组,其中每个元素是一个指向Bucket链表的头指针。

    哈希算法

    PHP哈希表最小容量是8(2^3),最大容量是0x80000000(2^31),并向2的整数次幂圆整(即长度会自动扩展为2的整数次幂,如13个元素的哈希表长度为16;100个元素的哈希表长度为128)。nTableMask被初始化为哈希表长度(圆整后)减1。具体代码在zend/Zend_hash.c的_zend_hash_init函数中,这里截取与本文相关的部分并加上少量注释。

    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;
        Bucket **tmp;
    
        SET_INCONSISTENT(HT_OK);
    
        //长度向2的整数次幂圆整
        if (nSize >= 0x80000000) {
            /* prevent overflow */
            ht->nTableSize = 0x80000000;
        } else {
            while ((1U << i) < nSize) {
                i++;
            }
            ht->nTableSize = 1 << i;
        }
    
        ht->nTableMask = ht->nTableSize - 1;
    
        /*此处省略若干代码…*/
    
        return SUCCESS;
    }
    

    值得一提的是PHP向2的整数次幂取圆整方法非常巧妙,可以背下来在需要的时候使用。

    Zend HashTable的哈希算法比较简单:

    hash(key)=key & nTableMask
    

    即简单将数据的原始key与HashTable的nTableMask进行按位与即可。

    如果原始key为字符串,则首先使用Times33算法将字符串转为整形再与nTableMask按位与。

    hash(strkey)=time33(strkey) & nTableMask
    

    下面是Zend源码中查找哈希表的代码:

    ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
    {
        uint nIndex;
        Bucket *p;
    
        IS_CONSISTENT(ht);
    
        nIndex = h & ht->nTableMask;
    
        p = ht->arBuckets[nIndex];
        while (p != NULL) {
            if ((p->h == h) && (p->nKeyLength == 0)) {
                *pData = p->pData;
                return SUCCESS;
            }
            p = p->pNext;
        }
        return FAILURE;
    }
    
    ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
    {
        ulong h;
        uint nIndex;
        Bucket *p;
    
        IS_CONSISTENT(ht);
    
        h = zend_inline_hash_func(arKey, nKeyLength);
        nIndex = h & ht->nTableMask;
    
        p = ht->arBuckets[nIndex];
        while (p != NULL) {
            if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
                if (!memcmp(p->arKey, arKey, nKeyLength)) {
                    *pData = p->pData;
                    return SUCCESS;
                }
            }
            p = p->pNext;
        }
        return FAILURE;
    }
    

    其中zend_hash_index_find用于查找整数key的情况,zend_hash_find用于查找字符串key。逻辑基本一致,只是字符串key会通过zend_inline_hash_func转为整数key,zend_inline_hash_func封装了times33算法,具体代码就不贴出了。

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [Python程序设计] Tornado 服务器环境配置 3 个条目
  2. [移动开发] Android里的ContentValues 2 个条目
  3. [PHP程序设计] PHP扩展模块安装 1 个条目
  4. [Python程序设计] Django模板系统 11 个条目
  5. [移动开发] Content Provider内容提供者 3 个条目
  6. [PHP程序设计] PHP与函数式编程 1 个条目
  7. [软件工程与项目管理] 浏览器初步介绍 8 个条目
  8. [移动开发] 从代码角度去认识HttpClient 2 个条目
  9. [移动开发] 从代码角度去认识 Handler 4 个条目
  10. [移动开发] Android开发基础知识 4 个条目
  11. [移动开发] Android 网络通信框架Volley 1 个条目
  12. [JavaScript程序设计] Web实时通信技术名词解析 5 个条目
窗口 -- [资讯]