转载地址：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;