怎么样是hash,以致哪些是hash表

在nginx中使用的hash中一个非常核心的函数就是ngx_hash_init,由于nginx这个hash表是静态只读的,即不能在运行时动态添加新元素的,一切的结构和数据都在配置初始化的时候就已经规划完毕,所以“init”过程的优劣,对运行时查找的性能影响非常大。在正式分析之前,下面的这个连接给出了一个非常详细的hash结构的整体布局,对理解代码帮助会很大,一定要仔细看一下。

代码转自:https://code.csdn.net/snippets/227183

hashmap jdk 起到了一个以点概面的作用

转自:

1、哈希表概念

先思考这样一个问题,假设让你来设计一个静态的hash表,对于一批确定数量的关键字,如何建立一个合理并且高效的hash表,让运行时的查找足够高效呢?你的hash表槽位多少合适?key冲突问题如何解决,用链式?链表长度该如何确定,太长效率低,那么多长合适?想想这些问题,然后我们看看nginx是如何去做的。

/*********************************************************************
*哈希表算法实现
*(c)copyright 2013,jdh
*All Right Reserved
*文件名:main.c
*程序员:jdh
*补充:cyan  通过构造一个桶,将不同id(即hash的key)按一定规则,放在不同的桶里面。
        桶里面是一个链接,每个桶的开头是一个哨兵节点。
        查找key时,先定位到桶,然后再从桶里面去遍历。
**********************************************************************/

#include <stdio.h>
#include <stdlib.h>

#define uint8_t unsigned char
#define uint16_t unsigned short
#define uint32_t unsigned long

#define HASH_TABLE_LEN  100 /*哈希表长度*/

//链表节点
typedef struct _Link_Node  
{  
    uint16_t id;
    uint16_t data;
    struct _Link_Node *next;  
}Link_Node,*Link_Node_Ptr; 

//哈希表头
typedef struct _Hash_Header  
{  
    struct _Link_Node *next;  
}Hash_Header,*Hash_Header_Ptr;


//哈希表
Hash_Header_Ptr Hash_Table[HASH_TABLE_LEN];



/*********************************************************************
*哈希表函数
*说明:
*1.用哈希函数生成id对应的哈希表中的位置
输入:id
返回:位置
**********************************************************************/

uint8_t hash_func(uint16_t id)
{
    uint8_t pos = 0;

    pos = id % HASH_TABLE_LEN;

    return pos;
}

/*********************************************************************
*                           初始化节点
*返回:结点指针
**********************************************************************/

Link_Node_Ptr init_link_node(void)
{
    Link_Node_Ptr node;

    //申请节点
    node = (Link_Node_Ptr) malloc(sizeof(Link_Node));
    //初始化长度为0
    node->next = NULL;

    return node;
}

/*********************************************************************
*                           初始化哈希表头结点
*返回哈希表头结点指针
**********************************************************************/

Hash_Header_Ptr init_hash_header_node(void)
{
    Hash_Header_Ptr node;

    //申请节点
    node = (Hash_Header_Ptr) malloc(sizeof(Hash_Header));
    //初始化长度为0
    node->next = NULL;

    return node;
}


/*********************************************************************
*                           哈希表初始化
*说明:
*1.初始化哈希表Hash_Table
*2.哈希表长度最大不能超过256
**********************************************************************/

void init_hash_table(void)
{
    uint8_t i = 0;

    for (i = 0;i < HASH_TABLE_LEN;i++)
    {
        Hash_Table[i] = init_hash_header_node();
        Hash_Table[i]->next = NULL;
    }
}

/*********************************************************************
*                           在哈希表增加节点
*说明:
*1.在哈希表的某个链表末增加数据
输入:new_node:新节点
**********************************************************************/

void append_link_node(Link_Node_Ptr new_node)
{
    Link_Node_Ptr node;
    uint8_t pos = 0;

    //新节点下一个指向为空
    new_node->next = NULL;

    //用哈希函数获得位置
    pos = hash_func(new_node->id);

    //判断是否为空链表
    if (Hash_Table[pos]->next == NULL)
    {
        //空链表
        Hash_Table[pos]->next = new_node;
    }
    else
    {
        //不是空链表
        //获取根节点
        node = Hash_Table[pos]->next;

        //遍历
        while (node->next != NULL)
        {
            node = node->next;
        }

        //插入
        node->next = new_node;
    }
}

/*********************************************************************
*                           在哈希表查询节点
*说明:
*1.知道在哈希表某处的单链表中,并开始遍历.
*2.返回的是查询节点的前一个节点指针.这么做是为了做删除操作.
输入:pos:哈希表数组位置,从0开始计数
     id:所需要查询节点的id
     root:如果是根节点,则*root = 1,否则为0
返回:所需查询的节点的前一个节点指针,如果是根节点则返回根节点,失败返回0
**********************************************************************/

Link_Node_Ptr search_link_node(uint16_t id,uint8_t *root)
{
    Link_Node_Ptr node;
    uint8_t pos = 0;

    //用哈希函数获得位置
    pos = hash_func(id);

    //获取根节点
    node = Hash_Table[pos]->next;

    //判断单链表是否存在
    if (node == NULL)
    {
        return 0;
    }

    //判断是否是根节点
    if (node->id == id)
    {
        //是根节点
        *root = 1;
        return node;
    }
    else
    {
        //不是根节点
        *root = 0;
        //遍历
        while (node->next != NULL)
        {
            if (node->next->id == id)
            {
                return node;
            }
            else
            {
                node = node->next;
            }
        }

        return 0;
    }
}

/*********************************************************************
*                           在哈希表删除节点
*说明:
*1.删除的不是当前节点,而是当前节点后的一个节点
输入:node:删除此节点后面的一个节点
     new_node:新节点
**********************************************************************/

void delete_link_node(Link_Node_Ptr node)
{
    Link_Node_Ptr delete_node;

    //重定向需要删除的前一个节点
    delete_node = node->next;
    node->next = delete_node->next;

    //删除节点
    free(delete_node);
    delete_node = NULL;
}

/*********************************************************************
*在哈希表删除根节点
输入:node:根节点
**********************************************************************/

void delete_link_root_node(Link_Node_Ptr node)
{
    uint8_t pos = 0;

    //用哈希函数获得位置
    pos = hash_func(node->id);

    //哈希表头清空
    if (node != NULL)
    {
        Hash_Table[pos]->next = node->next;
        //删除节点
        free(node);
        node = NULL;
    }
}

/*********************************************************************
*                           获得哈希表中所有节点数
输入:node:根节点
**********************************************************************/

uint16_t get_node_num(void)
{
    Link_Node_Ptr node;
    uint16_t i = 0;
    uint16_t num = 0;

    //遍历
    for (i = 0;i < HASH_TABLE_LEN;i++)
    {
        //获取根节点
        node = Hash_Table[i]->next;
        //遍历
        while (node != NULL)
        {
            num++;
            node = node->next;
        }
    }

    return num;
}

/*********************************************************************
*                           从哈希表中获得对应序号的节点
*参数:index:序号.从1开始,最大值为节点总数值
*     root:如果是根节点,则*root = 1,否则为0
返回:所需查询的节点的前一个节点指针,如果是根节点则返回根节点,失败返回0
**********************************************************************/

Link_Node_Ptr get_node_from_index(uint16_t index,uint8_t *root)
{   
    Link_Node_Ptr node;
    uint16_t i = 0;
    uint16_t num = 0;

    //遍历
    for (i = 0;i < HASH_TABLE_LEN;i++)
    {
        //获取根节点
        node = Hash_Table[i]->next;
        //判断单链表是否存在
        if (node == NULL)
        {
            continue;
        }

        //根节点
        num++;
        if (num == index)
        {
            //是根节点
            *root = 1;
            return node; 
        }

        //遍历
        while (node->next != NULL)
        {
            num++;
            if (num == index)
            {
                //不是根节点
                *root = 0;
                return node; 
            }
            node = node->next;
        }
    }

    return 0;
}

/*********************************************************************
*                           删除hash表中所有节点
**********************************************************************/

void drop_hash()
{
    Link_Node_Ptr node;
    uint16_t i = 0;
    Link_Node_Ptr node_next;

    //遍历
    for (i = 0;i < HASH_TABLE_LEN;i++)
    {
        //获取根节点
        node = Hash_Table[i]->next;

        while (1)
        {
            //判断单链表是否存在
            if (node == NULL)
            {
                //不存在
                Hash_Table[i]->next = NULL;
                break;
            }

            //根节点下一个节点
            node_next = node->next;
            //删除根节点
            free(node);
            //重指定根节点
            node = node_next;
        }
    }
}

/*********************************************************************
*                           输出所有节点
**********************************************************************/

void printf_hash()
{
    Link_Node_Ptr node;
    uint8_t root = 0;
    uint8_t i = 0;
    uint8_t num = 0;

    printf("-------------打印hash表-------------\n");

    num = get_node_num();
    for (i = 1;i <= num;i++)
    {
        node = get_node_from_index(i,&root);
        if (node != 0)
        {
            if (root)
            {
                printf("根节点:节点号%d,id为%d\n",i,node->id);
            }
            else
            {
                printf("普通节点:节点号%d,id为%d\n",i,node->next->id);
            }
        }
    }
}

/*********************************************************************
*                           主函数
*说明:实现对哈希表的新建,建立节点,查询及增加,删除节点的操作
**********************************************************************/

int main()
{
    Link_Node_Ptr node;
    uint8_t temp = 0;
    uint8_t root = 0;
    uint8_t i = 0;

    init_hash_table();

    //插入数据id = 1,data = 2;
    node = init_link_node();
    node->id = 1;
    node->data = 2;
    append_link_node(node);

    //查询节点数
    printf("1节点数为%d\n",get_node_num());

    node = init_link_node();
    node->id = 100;
    node->data = 101;
    append_link_node(node);

    node = init_link_node();
    node->id = 1002;
    node->data = 1001;
    append_link_node(node);

    node = init_link_node();
    node->id = 10000;
    node->data = 10001;
    append_link_node(node);

    node = init_link_node();
    node->id = 1000;
    node->data = 10001;
    append_link_node(node);

    node = init_link_node();
    node->id = 2;
    node->data = 10001;
    append_link_node(node);

    //查询节点数
    printf("2节点数为%d\n",get_node_num());

    //查询id = 1000;
    node = search_link_node(100,&temp);
    if (node != 0)
    {
        if (temp == 0)
        {
            printf("删除普通节点:所需查询id的值为%d,数据为%d\n",node->next->id,node->next->data);

            //删除
            delete_link_node(node);
        }
        else
        {
            //根节点
            printf("删除根节点所需查询id的值为%d,数据为%d\n",node->id,node->data);

            //删除
            delete_link_root_node(node);
        }
    }
    else
    {
        printf("查询失败\n");
    }

    //查询id = 1001;
    node = search_link_node(1001,&temp);
    if (node != 0)
    {
        if (temp == 0)
        {
            printf("所需查询id的值为%d\n",node->next->data);
        }
        else
        {
            //根节点
            printf("所需查询id的值为%d\n",node->data);
        }
    }
    else
    {
        printf("查询失败\n");
    }

    //查询节点数
    printf("节点数为%d\n",get_node_num());

    printf_hash();


    getchar();
    return 0;
}

#include<string.h>
#include<ctype.h>
#include<malloc.h>
#include<limits.h>
#include<stdio.h> 
#include<stdlib.h>
#include<math.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define NULLKEY 0 // 0为无记录标志
#define N 10 // 数据元素个数
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
typedef int KeyType; // 设关键字域为整型

struct ElemType // 数据元素类型
{
    KeyType key;
    int ord;
};

int hashsize[]={11,19,29,37}; // 哈希表容量递增表,一个合适的素数序列
int m=0; // 哈希表表长,全局变量

struct HashTable
{
    ElemType *elem; // 数据元素存储基址,动态分配数组
    int count; // 当前数据元素个数
    int sizeindex; // hashsize[sizeindex]为当前容量
};

Status InitHashTable(HashTable &H)// 操作结果: 构造一个空的哈希表
{ 
    int i;
    H.count=0; // 当前元素个数为0
    H.sizeindex=0; // 初始存储容量为hashsize[0]
    m=hashsize[0];
    H.elem=(ElemType*)malloc(m*sizeof(ElemType));
    if(!H.elem)
        exit(OVERFLOW); // 存储分配失败
    for(i=0;i<m;i++)
        H.elem[i].key=NULLKEY; // 未填记录的标志
    return OK;
}

void DestroyHashTable(HashTable &H)// 初始条件: 哈希表H存在。操作结果: 销毁哈希表H
{ 
    free(H.elem);
    H.elem=NULL;
    H.count=0;
    H.sizeindex=0;
}

unsigned Hash(KeyType K)// 一个简单的哈希函数(m为表长,全局变量)
{ 
    return K%m;
}

void collision(int &p,int d) // 线性探测再散列
{ 
    p = (p + d) % m;// 开放定址法处理冲突
}

Status SearchHash(HashTable H,KeyType K,int &p,int &c)// 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据
{ 
    p=Hash(K); // 求得哈希地址
    while(H.elem[p].key!=NULLKEY&&!EQ(K,H.elem[p].key))
    { // 该位置中填有记录.并且关键字不相等
        c++;
        if(c<m)
            collision(p,c); // 求得下一探查地址p
        else
            break;
    }
    if EQ(K,H.elem[p].key)
        return SUCCESS; // 查找成功,p返回待查数据元素位置
    else
        return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY),p返回的是插入位置
}

Status InsertHash(HashTable &,ElemType); // 对函数的声明

void RecreateHashTable(HashTable &H) // 重建哈希表
{
    int i,count=H.count;
    ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType));
    p=elem;
    printf("重建哈希表\n");
    for(i=0;i<m;i++) // 保存原有的数据到elem中
        if((H.elem+i)->key!=NULLKEY) // 该单元有数据
            *p++=*(H.elem+i);
    H.count=0;
    H.sizeindex++; // 增大存储容量
    m=hashsize[H.sizeindex];
    p=(ElemType*)realloc(H.elem,m*sizeof(ElemType));
    if(!p)
        exit(OVERFLOW); // 存储分配失败
    H.elem=p;
    for(i=0;i<m;i++)
        H.elem[i].key=NULLKEY; // 未填记录的标志(初始化)
    for(p=elem;p<elem+count;p++) // 将原有的数据按照新的表长插入到重建的哈希表中
        InsertHash(H,*p);
}

Status InsertHash(HashTable &H,ElemType e)// 查找不成功时插入数据元素e到开放定址哈希表H中,并返回OK;
{
    int c,p;
    c=0;
    if(SearchHash(H,e.key,p,c)) // 表中已有与e有相同关键字的元素
        return DUPLICATE;
    else if(c<hashsize[H.sizeindex]/2) // 冲突次数c未达到上限,(c的阀值可调)
    { // 插入e
        H.elem[p]=e;
        ++H.count;
        return OK;
    }
    else
        RecreateHashTable(H); // 重建哈希表
    return ERROR;
}

void TraverseHash(HashTable H,void(*Vi)(int,ElemType))// 按哈希地址的顺序遍历哈希表
{ 
    printf("哈希地址0~%d\n",m-1);
    for(int i=0;i<m;i++)
        if(H.elem[i].key!=NULLKEY) // 有数据
            Vi(i,H.elem[i]);
}

Status Find(HashTable H,KeyType K,int &p)// 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据
{
    int c=0;
    p=Hash(K); // 求得哈希地址
    while(H.elem[p].key!=NULLKEY&&!EQ(K,H.elem[p].key))// 该位置中填有记录.并且关键字不相等
    {
        c++;
        if(c<m)
            collision(p,c); // 求得下一探查地址p
        else
            return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
    }
    if EQ(K,H.elem[p].key)
        return SUCCESS; // 查找成功,p返回待查数据元素位置
    else
        return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}


void print(int p,ElemType r)//输出
{
    printf("address=%d (%d,%d)\n",p,r.key,r.ord);
}

void main()
{
    ElemType r[N]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{60,9},{13,10}};
    HashTable h;
    int i,p;
    Status j;
    KeyType k;
    InitHashTable(h);
    for(i=0;i<N-1;i++)// 插入前N-1个记录
    { 
        j=InsertHash(h,r[i]);
        if(j==DUPLICATE)
            printf("表中已有关键字为%d的记录,无法再插入记录(%d,%d)\n",r[i].key,r[i].key,r[i].ord);
    }
    printf("按哈希地址的顺序遍历哈希表:\n");
    TraverseHash(h,print);
    printf("请输入待查找记录的关键字: ");
    scanf("%d",&k);
    j=Find(h,k,p);
    if(j==SUCCESS)
        print(p,h.elem[p]);
    else
        printf("没找到\n\n");
    j=InsertHash(h,r[i]); // 插入第N个记录
    if(j==ERROR) // 重建哈希表
        j=InsertHash(h,r[i]); // 重建哈希表后重新插入
    printf("按哈希地址的顺序遍历重建后的哈希表:\n");
    TraverseHash(h,print);
    printf("请输入待查找记录的关键字: ");
    scanf("%d",&k);
    j=Find(h,k,p);
    if(j==SUCCESS)
        print(p,h.elem[p]);
    else
        printf("没找到\n");
    DestroyHashTable(h);
}

是根据关键码值(key,value)而直接进行访问的数据结构,把key值通过hash函数转换成一个整形数字,然后将该数字对数组长度取余,取余的结果当成数组的下标,value存储在以该数字为下标的数组空间里。

  1. ngx_int_t  
  2. ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts)  
  3. {  
  4.     u_char          *elts;  
  5.     size_t           len;  
  6.     u_short         *test;  
  7.     ngx_uint_t       i, n, key, size, start, bucket_size;  
  8.     ngx_hash_elt_t  *elt, **buckets;  
  9.       
  10.     /* nelts是关键字的数量,bucket_size为一个bucket的大小,这里注意的就是一个bucket至少可以容得下一个关键字, 
  11.      * 而下面的NGX_HASH_ELT_SIZE(&name[n] + sizeof(void *))正好就是一个关键字所占的空间。 
  12.      * 通过判断条件来看,如果我们设定的bucket大小,必须保证能容得下任何一个关键字,否则,就报错,提示bucket指定的太小。 
  13.      * 关于NGX_HASH_ELT_SIZE这个宏,这里提一下,nginx把所以定位到某个bucket的关键字,即冲突的,封装成ngx_hash_elt_t结构 
  14.      * 挨在一起放置,这样组成了一个ngx_hash_elt_t数组,这个数组空间的地址,由ngx_hash_t中的buckets保存。对于某个关键字来说, 
  15.      * 它有一个ngx_hash_elt_t的头结构和紧跟在后面的内容组成,从这个角度看一个关键字所占用的空间正好等于NGX_HASH_ELT_SIZE宏的值 
  16.      * 只是里面多了一个对齐的动作。 
  17.      */  
  18.     for (n = 0; n < nelts; n++) {  
  19.         /*  
  20.          * 这里考虑放置每个bucket最后的null指针所需要的空间,即代码中的sizeof(void *),这个NULL在find过程中作为一个bucket 
  21.          * 的结束标记来使用。 
  22.          */  
  23.         if (hinit->bucket_size < NGX_HASH_ELT_SIZE(&names[n]) + sizeof(void *))  
  24.         {  
  25.             return NGX_ERROR;  
  26.         }  
  27.     }  
  28.       
  29.     /* max_size是bucket的最大数量, 这里的test是用来做探测用的,探测的目标是在当前bucket的数量下,冲突发生的是否频繁。 
  30.      * 过于频繁则说明当前的bucket数量过少,需要调整。那么如何判定冲突过于频繁呢?就是利用这个test数组,它总共有max_size个 
  31.      * 元素,即最大的bucket。每个元素会累计落到该位置关键字长度,当大于256个字节,即u_short所表示的最大大小时,则判定 
  32.      * bucket过少,引起了严重的冲突。后面会看到具体的处理。 
  33.      */  
  34.     test = ngx_alloc(hinit->max_size * sizeof(u_short), hinit->pool->log);  
  35.     if (test == NULL) {  
  36.         return NGX_ERROR;  
  37.     }  
  38.       
  39.     /* 每个bucket的末尾一个null指针作为bucket的结束标志, 这里bucket_size是容纳实际数据大小,故减去一个指针大小 */  
  40.     bucket_size = hinit->bucket_size – sizeof(void *);  
  41.       
  42.     /*  
  43.      * 这里考虑NGX_HASH_ELT_SIZE中,由于对齐的缘故,一个关键字最少需要占用两个指针的大小。 
  44.      * 在这个前提下,来估计所需要的bucket最小数量,即考虑元素越小,从而一个bucket容纳的数量就越多, 
  45.      * 自然使用的bucket的数量就越少,但最少也得有一个。 
  46.      */  
  47.     start = nelts / (bucket_size / (2 * sizeof(void *)));  
  48.     start = start ? start : 1;  
  49.       
  50.     /*  
  51.      * 调整max_size,即bucket数量的最大值,依据是:bucket超过10000,且总的bucket数量与元素个数比值小于100 
  52.      * 那么bucket最大值减少1000,至于这几个判断值的由来,尚不清楚,经验值或者理论值。 
  53.      */  
  54.     if (hinit->max_size > 10000 && nelts && hinit->max_size / nelts < 100) {  
  55.         start = hinit->max_size – 1000;  
  56.     }  
  57.       
  58.     /* 在之前确定的最小bucket个数的基础上,开始探测(通过test数组)并根据需要适当扩充,前面有分析其原理 */  
  59.     for (size = start; size < hinit->max_size; size++) {  
  60.   
  61.         ngx_memzero(test, size * sizeof(u_short));  
  62.   
  63.         for (n = 0; n < nelts; n++) {  
  64.             if (names[n].key.data == NULL) {  
  65.                 continue;  
  66.             }  
  67.   
  68.             key = names[n].key_hash % size;  
  69.             test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));  
  70.   
  71.             if (test[key] > (u_short) bucket_size) {  
  72.                 goto next;  
  73.             }  
  74.         }  
  75.   
  76.         goto found;  
  77.           
  78.     next:  
  79.         /* 到next这里,就是实际处理bucket扩充的情况了,即递增表示bucket数量的size变量 */  
  80.         continue;  
  81.     }  
  82.   
  83.     ngx_free(test);  
  84.   
  85.     return NGX_ERROR;  
  86.   
  87. found:  
  88.     /* 确定了合适的bucket数量,即size。 重新初始化test数组,初始值为一个指针大小。*/  
  89.     for (i = 0; i < size; i++) {  
  90.         test[i] = sizeof(void *);  
  91.     }  
  92.       
  93.     /* 统计各个bucket中的关键字所占的空间,这里要提示一点,test[i]中除了基本的数据大小外,还有一个指针的大小 
  94.      * 如上面的那个for循环所示。 
  95.      */  
  96.     for (n = 0; n < nelts; n++) {  
  97.         if (names[n].key.data == NULL) {  
  98.             continue;  
  99.         }  
  100.   
  101.         key = names[n].key_hash % size;  
  102.         test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));  
  103.     }  
  104.   
  105.     len = 0;  
  106.       
  107.     /* 调整成对齐到cacheline的大小,并记录所有元素的总长度 */  
  108.     for (i = 0; i < size; i++) {  
  109.         if (test[i] == sizeof(void *)) {  
  110.             continue;  
  111.         }  
  112.   
  113.         test[i] = (u_short) (ngx_align(test[i], ngx_cacheline_size));  
  114.   
  115.         len += test[i];  
  116.     }  
  117.       
  118.     /*  
  119.      * 申请bucket元素所占的空间,这里注意的一点就是,如果之前hash表头结构没有申请, 
  120.      * 那么在申请时将ngx_hash_wildcard_t结构也一起申请了。 
  121.      */  
  122.     if (hinit->hash == NULL) {  
  123.         hinit->hash = ngx_pcalloc(hinit->pool, sizeof(ngx_hash_wildcard_t)  
  124.                                              + size * sizeof(ngx_hash_elt_t *));  
  125.         if (hinit->hash == NULL) {  
  126.             ngx_free(test);  
  127.             return NGX_ERROR;  
  128.         }  
  129.   
  130.         buckets = (ngx_hash_elt_t **)  
  131.                       ((u_char *) hinit->hash + sizeof(ngx_hash_wildcard_t));  
  132.   
  133.     } else {  
  134.         buckets = ngx_pcalloc(hinit->pool, size * sizeof(ngx_hash_elt_t *));  
  135.         if (buckets == NULL) {  
  136.             ngx_free(test);  
  137.             return NGX_ERROR;  
  138.         }  
  139.     }  
  140.   
  141.     elts = ngx_palloc(hinit->pool, len + ngx_cacheline_size);  
  142.     if (elts == NULL) {  
  143.         ngx_free(test);  
  144.         return NGX_ERROR;  
  145.     }  
  146.   
  147.     elts = ngx_align_ptr(elts, ngx_cacheline_size);  
  148.       
  149.     /* 设置各个bucket中包含实际数据的空间的地址(或者说位置) */  
  150.     for (i = 0; i < size; i++) {  
  151.         if (test[i] == sizeof(void *)) {  
  152.             continue;  
  153.         }  
  154.   
  155.         buckets[i] = (ngx_hash_elt_t *) elts;  
  156.         elts += test[i];  
  157.   
  158.     }  
  159.       
  160.     /* 用来累计真实数据的长度,不计结尾指针的长度 */  
  161.     for (i = 0; i < size; i++) {  
  162.         test[i] = 0;  
  163.     }  
  164.       
  165.     /* 依次向各个bucket中填充实际的内容,代码没什么好分析的。*/  
  166.     for (n = 0; n < nelts; n++) {  
  167.         if (names[n].key.data == NULL) {  
  168.             continue;  
  169.         }  
  170.   
  171.         key = names[n].key_hash % size;  
  172.         elt = (ngx_hash_elt_t *) ((u_char *) buckets[key] + test[key]);  
  173.   
  174.         elt->value = names[n].value;  
  175.         elt->len = (u_short) names[n].key.len;  
  176.   
  177.         ngx_strlow(elt->name, names[n].key.data, names[n].key.len);  
  178.         /* test[key]记录当前bucket内容的填充位置,即下次填充的开始位置 */  
  179.         test[key] = (u_short) (test[key] + NGX_HASH_ELT_SIZE(&names[n]));  
  180.     }  
  181.       
  182.     /* 设置bucket结束位置的null指针,*/  
  183.     for (i = 0; i < size; i++) {  
  184.         if (buckets[i] == NULL) {  
  185.             continue;  
  186.         }  
  187.         /*  
  188.          * 由于前面bucket的处理中多留出了一个指针的空间,而此时的test[i]是bucket中实际数据的共长度, 
  189.          * 所以bucket[i] + test[i]正好指向了末尾null指针所在的位置。处理的时候,把它当成一个ngx_hash_elt_t结构看, 
  190.          * 在该结构中的第一个元素,正好是一个void指针,我们只处理它,别的都不去碰,所以没有越界的问题。 
  191.          */  
  192.         elt = (ngx_hash_elt_t *) ((u_char *) buckets[i] + test[i]);  
  193.   
  194.         elt->value = NULL;  
  195.     }  
  196.   
  197.     ngx_free(test);  
  198.   
  199.     hinit->hash->buckets = buckets;  
  200.     hinit->hash->size = size;  
  201.   
  202.     return NGX_OK;  
  203. }  

1.什么是hash

2、哈希表最常见的实现方法为拉链法如图所示:

图片 1

它是将一个任意长度的二进制值通过一个映射关系转换成一个固定长度的二进制。

图片 2

(1)任意长度的二进制值

最左边的数组存储指针,每个指针指向一个链表的头。当通过hash函数获得的存储位置下标相同的,存在同一个链表了,数组该下标位置存储链表的头指针。

(2)映射关系(哈希算法-就相当于一个大学里面的学号的一个映射规则)

 

(3)固定的二进制值(哈希值-相当于我们大学里面的学号)

hash函数的构造方法:

任意长度的二进制值 和 固定长度的二进制值 是一个一一对应关系

1、直接定址法:

固定长度的二进制值相当于任意一个二进制值的一个摘要

         取关键字或关键字的某个线性函数值为哈希地址:H(key)=key 或
H(key)=a·key+b

固定长度的二进制值 相当于一个关键字key

其中a和b为常数,这种哈希函数叫做自身函数。

真正有效的数据,就是学员的基本信息,一个任意长度的二进制值 value

例:有一个从1岁到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。这样,若要询问25岁的人有多少,则只要查表的第25项即可。

key—-value

        
由于直接定址所得地址集合和关键字集合的大小相同。因此,对于不同的关键字不会发生冲突。但实际中能使用这种哈希函数的情况很少。

hash 只是确定了一个key和一个value的唯一关系。

2、  相乘取整法

为什么这么做:

该方法包括两个步骤:首先用关键字key乘上某个常数A(0<A<1),并抽取出key.A的小数部分;然后用m乘以该小数后取整。即:
         图片 3

2.hash表

该方法最大的优点是m的选取比除余法要求更低。比如,完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用,但对某些值效果会更好。Knuth建议选取
             图片 4

特定:最重要的特点—它的存储效率很高,去数据的时间负责读是1 o(1)

3、平方取中法

图片 5

         取关键字平方后的中间几位为哈希地址。

通过平方扩大差别,另外中间几位与乘数的每一位相关,由此产生的散列地址较为均匀。这是一种较常用的构造哈希函数的方法。

例:将一组关键字(0100,0110,1010,1001,0111)

平方后得(0010000,0012100,1020100,1002001,0012321)

若取表长为1000,则可取中间的三位数作为散列地址集:(100,121,201,020,123)。

4、折叠法

将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法(folding)。

如国际标准图书编号0-442-20586-4的哈希地址分别如

图片 6

 

5、除余法:

取关键字被数p除后所得余数为哈希地址:H(key)=keyMOD p (p≤m)

这是一种最简单,也最常用的构造哈希函数的方法。它不仅可以对关键字直接取模(MOD),也可在折迭、平方取中等运算之后取模。值得注意的是,在使用除留余数法时,对p的选择很重要。一般情况下可以选p为质数或不包含小于20的质因素的合数。

6、随机数法

   选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H(key)=random
(key),其中random为随机函数。通常,当关键字长度不等时采用此法构造哈希函数较恰当。

冲突的解决

1)开放定址法

  即当一个关键字和另一个关键字发生冲突时,使用某种探测技术在Hash表中形成一个探测序列,然后沿着这个探测序列依次查找下去,当碰到一个空的单元时,则插入其中。比较常用的探测方法有线性探测法,比如有一组关键字{12,13,25,23,38,34,6,84,91},Hash表长为14,Hash函数为address(key)=key%11,当插入12,13,25时可以直接插入,而当插入23时,地址1被占用了,因此沿着地址1依次往下探测(探测步长可以根据情况而定),直到探测到地址4,发现为空,则将23插入其中。

2)链地址法

   采用数组和链表相结合的办法,将Hash地址相同的记录存储在一张线性表中,而每张表的表头的序号即为计算得到的Hash地址。(拉链法)

3)再哈希。就是当冲突时,采用另外一种映射方式来查找。

4)建立一个缓冲区,把凡是拼音重复的人放到缓冲区中。当我通过名字查找人时,发现找的不对,就在缓冲区里找。

相关文章