Sword 哈希表

哈希表
哈希表是一种典型的以空间换取时间的数据结构，在没有冲突的情况下，对任意元素的插入、索引、删除的时间复杂度都是O(1)。
这样优秀的时间复杂度是通过将元素的key值以hash方法f映射到哈希表中的某一个位置来访问记录来实现的，即键值为key的元素
必定存储在哈希表中的f(key)的位置。当然，不同的元素的hash值可能相同，这就是hash冲突，有两种解决方法(分离链表发和开
放地址发)，ngx采用的是开放地址法.

分离链表法是通过将冲突的元素链接在一个哈希表外的一个链表中，这样，找到hash表中的位置后，就可以通过遍历这个单链表来找到这个元素

开放地址法是插入的时候发现自己的位置f(key)已经被占了，就向后遍历，查看f(key)+1的位置是否被占用，如果没被占用，就占用它，
否则继续相后，查询的时候，同样也如果f(key)不是需要的值，也依次向后遍历，一直找到需要的元素。

哈希表的本质
普通哈希表的查找比较简单，思想就是先根据hash值找到对应桶，然后遍历这个桶的每一个元素，逐字匹配是否关键字完全相同，
完全相同则找到，否则继续，直至找到这个桶的结尾(value = NULL)。

nginx的hash表是固定元素长度的，就是一开始已知所有的键值对。无法动态添加,但是可以修改值

gtc_hash_t * gtc_internal_hash_build(unsigned int max_bucket_count
　　　　　　　　, unsigned int max_bucket_size
　　　　　　　　, gtc_pool_t *pool
　　　　　　　　, gtc_hash_key_t *names
　　　　　　　　, unsigned int nelts)
{
    gtc_hash_t * hash = NULL;
    unsigned int n = 0, i = 0;
    unsigned int *test = NULL;
    unsigned int bucket_size = 0, start = 0, index = 0;
    unsigned int key = 0, len = 0;
    unsigned char *elts = NULL;
    gtc_hash_elt_t **buckets = NULL;
    gtc_hash_elt_t *elt = NULL;

    //1.校验哈希表初始化参数
    if (0 == max_bucket_count)
    {
        //哈希表桶的数目不可以是0
        return NULL;
    }

    if (GTC_MAX_BUCKET_SIZE - GTC_CACHELINE_SIZE < max_bucket_size)
    {
        //哈希表桶的大小必须小于 GTX_MAX_BUCKET_SIZE
        /*
        为啥要小于 GTX_MAX_BUCKET_SIZE - GTC_CACHELINE_SIZE?
            这是为了内存对齐，因为hash表所有的内存都在内存池上
        */
        return NULL;
    }

    /*
    设计说明:
        下面操作的目的是为了确认 需要建立哈希表的每一个元素所占内存空间都必须小于 哈希表中桶的大小
        hinit->bucket_size < GTC_HASH_ELT_SIZE(&names[n]) + sizeof(void *)说明
        hinit->bucket_size 桶的大小
        GTC_HASH_ELT_SIZE(&names[n]) 一个哈希元素的大小
        sizeof(void *) 哈希表中每个桶都是以NULL结尾
        因此 这个 if 判断的意义是 最起码保证 一个桶可以装一个元素(一个桶可以装多个元素，当然更好)
    */
    for (n = 0; n < nelts; n++)
    {
        if (max_bucket_size < GTC_HASH_ELT_SIZE(&names[n]) + sizeof(void *))
        {
            return NULL;
        }
    }

    do 
    {
        //2.计算出桶的数量
        test = (unsigned int *)calloc(max_bucket_count, sizeof(unsigned int));
        if (NULL == test)
        {
            break;
        }

        /*
        设计说明:
            a. bucket_size = hinit->bucket_size - sizeof(void *);说明
                bucket_size 为实际可以存放元素的大小
                hinit->bucket_size - sizeof(void *) 因为每个桶都是NULL结尾，所以实际大小需要 - sizeof(void *)

            b. start = nelts / (bucket_size / (2 * sizeof(void *))) + 1;
                2 * sizeof(void *) 这个是 gtc_hash_elt_t 最小的值，根据 结构体对齐规则 gtc_hash_elt_t最小就是 2 * sizeof(void *) 大小
                bucket_size / (2 * sizeof(void *) 这是桶里最多可以装 多个元素
                nelts / (bucket_size / (2 * sizeof(void *))) 计算出最少需要多少个桶
                + 1 为什么需要加1，因为 nelts / (bucket_size / (2 * sizeof(void *))) 本质上是向下取整，最少也应该有一个，所以应该向上取整

        */
        bucket_size = max_bucket_size - sizeof(void *);    //bucket_size 为实际可以存放元素的大小
        start = nelts / (bucket_size / (2 * sizeof(void *))) + 1;
        //优化start
        if (max_bucket_count > 10000 && nelts && max_bucket_count / nelts < 100) 
        {
            start = max_bucket_count - 1000;
        }

        //计算出实际桶的数量
        for (index = start; index < max_bucket_count; index++)
        {
            //部分清零策略，提高效率
            memset(test, 0x00, (index + 1) * sizeof(unsigned int));
            for (n = 0; n < nelts; n++)
            {
                if (NULL == names[n].key.data)
                {
                    //不处理空数据
                    continue;
                }

                //计算当前元素所在桶的位置
                key = names[n].key_hash % index;
                //计算当前桶的大小
                len = test[key] + GTC_HASH_ELT_SIZE(&names[n]);
                if (len > bucket_size)
                {
                    //如果当前长度超过桶的最大长度,说明桶的数目不够，需要更加离散
                    break;
                }
                test[key] = len;
            }

            if (n == nelts)
            {
                //已经找到最合适的桶的数目
                break;
            }

            continue;
        }

        if (index == max_bucket_count)
        {
            //当前桶的数量太少，不够存放所有的数据
            break;
        }

        //将每个桶最后的NULL 补上
        for (i = 0; i < index; i++)
        {
            test[i] += sizeof(void *);
        }

        //计算哈希表的总长度，分配内存空间
        len = 0;
        for (i = 0; i < index; i++)
        {
            if (sizeof(void *) == test[i])
            {
                /*
                设计说明:
                    空桶直接不会分配内存，因为哈希表元素固定且不支持添加
                */
                continue;
            }
            //数字对齐，加快内存检索
            test[i] = gtc_align(test[i], GTC_CACHELINE_SIZE);
            len += test[i];
        }

        //创建桶链表
        /*
        设计说明:
            桶里面存储的是 元素的指针，并非元素本身
            buckets 的个数一定是 index 个，但是不是每个Index里都有元素的
        */
        buckets = gtc_pcalloc(pool, index * sizeof(gtc_hash_elt_t *));
        if (NULL == buckets)
        {
            break;
        }
        //申请元素内存空间，所有的元素被放置在一块连续的内存上
        elts = gtc_pcalloc(pool, len);
        if (NULL == elts) 
        {
            break;
        }

        //指针内存对齐
        elts = gtc_align_ptr(elts, GTC_CACHELINE_SIZE);
        for (i = 0; i < index; i++)
        {
            if (sizeof(void *) == test[i])
            {
                //空桶，跳过
                continue;
            }
            buckets[i] = (gtc_hash_elt_t *)elts;
            elts += test[i];
        }

        //清空探测器,此时test[i] 实际上是 i 这个桶的偏移量
        memset(test, 0x00, index * sizeof(unsigned int));

        //将元素一一赋值
        for (n = 0; n < nelts; n++)
        {
            if (NULL == names[n].key.data)
            {
                //空元素不管
                continue;
            }
            //找到桶的位置
            key = names[n].key_hash % index;
            //找到一个元素块
            elt = (gtc_hash_elt_t *)((unsigned char *)buckets[key] + test[key]);
            //浅拷贝 value
            elt->value = names[n].value;
            elt->len = (unsigned short)names[n].key.len;
            //字符串拷贝
            gtc_strlow(elt->name, names[n].key.data, names[n].key.len);
            //更新当前桶偏移
            test[key] = (unsigned short) (test[key] + GTC_HASH_ELT_SIZE(&names[n]));
        }

        for (i = 0; i < index; i++) 
        {
            if (NULL == buckets[i])
            {
                //空桶不处理
                continue;
            }

            elt = (gtc_hash_elt_t *)((unsigned char *)buckets[i] + test[i]);

            //每个桶最后一个元素是 NULL
            elt->value = NULL;
        }

        //哈希表赋值
        hash = (gtc_hash_t *)gtc_pcalloc(pool, sizeof(gtc_hash_t));
        if (NULL == hash)
        {
            break;
        }
        hash->buckets = buckets;
        hash->size = index;

    } while (0);

    //资源释放
    if (test)
    {
        free(test);
        test = NULL;
    }

    return hash;
}