php HASHTABLE 实现

maxc1017

　　php大部分的语言特性都依赖于哈希表，比如变量的作用域和变量的存储，类的实现以及zend引擎内部的很多数据都是保存在哈希表中的
　　

　　PHP中的哈希表实现在Zend/zend_hash.c中

　　typedef struct _hashtable{
　　uint nTableSize;  //hash Bucket的大小 最小为8 以2X增长

　　uint nTableMask;  //nTableSize - 1 ,索引取值优化 应为nTableSize 为2x 他-1都是111的模式
　　uint nNumOfElements; //hash Buckets中当前存在的元素个数，count()返回的就是这个值，

　　ulong nNextFreeElement;//下一个数字索引的位置

　　Bucket *pInternalPointer;//当前遍历的指针(foreach 比for 快的原因之一)

　　Bucket *pListHead;//存储数组头元素指针

　　Bucket *pListTail;//存储数组尾元素指针

　　Bucket **arBuckets; //存储hash数组
　　dtor_func_t pDestructor;

　　zend_bool persistent;

　　unsigned char nApplyConut;//标记当前hash bucket被递归访问的次数（防止多次递归）

　　zend_bool bApplyProtection;//标记当前hash桶允许不允许被多次访问，不允许时，最多只能递归3次

　　#if ZEND_DEBUG

　　int inconsistent

　　#endif

　　}hashtble;

　　

　　

　　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 nTableSize = 1 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;}　　//自我理解  i默认的是3，1向右连续左移三次 就是*2的三次放 就是8 所以默认最小的值是8
ht->nTableMask = ht->nTableSize - 1; 这里的掩码是为了更好的将数据分散到范围内 因为2的n次方-1 的数据一定是1111的形式 用这个形式去做与运算，能较好的分布数据