Shark Deng

Interactive Designer @Shanju Design in Shanghai

touched caffe / mxnet / python / wordpress / bootstrap / Arduino / Raspberry Pi / webgl / three.js / PIXI / 3dMax

Email

Github

HashTable

2019-11-20 16:46:37

转载地址:https://www.cnblogs.com/wuhen781/p/6188564.html

哈希表在数据结构中也叫散列表。是根据键名经过hash函数计算后,映射到表中的一个位置,来直接访问记录,加快了访问速度。在理想情况下,哈希表的操作时间复杂度为O(1)。数据项可以在一个与哈希表长度无关的时间内,计算出一个值hash(key),在固定时间内定位到一个桶(bucket,表示哈希表的一个位置),主要时间消耗在于哈希函数计算和桶的定位。

键名(Key):在哈希函数转换前,数据的标识。

桶(Bucket):在哈希表中,真正保存数据的容器。

哈希函数(Hash Function):将Key通过哈希函数,得到一个指向bucket的指针。MD5,SHA-1是我们在业务中常用的哈希函数。

哈希冲突(Hash Collision):两个不同的Key,经过哈希函数,得到同一个bucket的指针。

//Zend/zend_hash.h

 typedef struct _hashtable {
        uint nTableSize;                    //哈希表的长度,不是元素个数
        uint nTableMask;                  //哈希表的掩码,设置为nTableSize-1
        uint nNumOfElements;          //哈希表实际元素个数
        ulong nNextFreeElement;      //指向下一个空元素位置
        Bucket *pInternalPointer;       //用于遍历哈希表的内部指针
        Bucket *pListHead;               //哈希表队列的头部
        Bucket *pListTail;                 //哈希表队列的尾部
        Bucket **arBuckets;               //哈希表存储的元素数组
        dtor_func_t pDestructor;          //哈希表的元素析构函数指针
        zend_bool persistent;              //是否是持久保存,用于pmalloc的参数,可以持久存储在内存中
        unsigned char nApplyCount;     // zend_hash_apply的次数,用来限制嵌套遍历的层数,限制为3层
        zend_bool bApplyProtection;     //是否开启嵌套遍历保护
#if ZEND_DEBUG
        int inconsistent; //debug字段,查看哈希表的操作记录
#endif
} HashTable;

 typedef struct bucket {
        ulong h;                               //数组索引的哈希值
        uint nKeyLength;                  //索引数组为0,关联数组为key的长度
        void *pData;                         //元素内容的指针
        void *pDataPtr;                    // 如果是指针大小的数据,用pDataPtr直接存储,pData指向pDataPtr
        struct bucket *pListNext;     //哈希链表中下一个元素
        struct bucket *pListLast;     //哈希链表中上一个元素
        struct bucket *pNext;          //解决哈希冲突,变为双向链表,双向链表的下一个元素
        struct bucket *pLast;          //解决哈希冲突,变为双向链表,双向链表的上一个元素
        const char *arKey;             //最后一个元素key的名称
} Bucket;

 



——By SharkDeng
如果你喜欢我的文章,欢迎红包赞赏

Leave a Reply

Your email address will not be published. Required fields are marked *