哈希表（散列表）

定义：提高数据的查找效率

时间复杂度：

哈希存储：将要存储的数据的关键字和存储位置之间，建立起对应的关系，这个关系称之为哈希

                  函数。存储数据时，通过对应的哈希函数可以将数据映射到指定的存储位置，查找时

                  仍可通过该函数找到数据的存储位置。

哈希冲突/哈希矛盾：key1 ！= key2        f（key1） =  f（key2）

解决方法：

1.开放地址法

2.链地址法

#include <stdio.h>
#include "hash.h"


int main(void)
{
    Data_type_t pers[5] = {{"zhangsan", "110"}, {"lisi", "120"},
                            {"wanger", "119"}, {"Zhaowu", "122"},
                            {"maliu", "10086"}};


    HSNode_t *hash_table[HASH_TABLE_MAX_SIZE] = {NULL};

    insert_hash_table(hash_table, pers[0]);
    insert_hash_table(hash_table, pers[1]);
    insert_hash_table(hash_table, pers[2]);
    insert_hash_table(hash_table, pers[3]);
    insert_hash_table(hash_table, pers[4]);

    hash_for_each(hash_table);

    HSNode_t *pnode = find_hash_table(hash_table, "zhang");
    if (pnode != NULL)
    {
        printf("find : %s : %s\n", pnode->data.name, pnode->data.tel);
    }

    destroy_hash_table(hash_table);

    return 0;
}

#ifndef __HASH_H__
#define __HASH_H__

#define HASH_TABLE_MAX_SIZE 27


typedef struct per
{
    char name[32];
    char tel[32];
}Data_type_t;

typedef struct node
{
    Data_type_t data;
    struct node *pnext;
}HSNode_t;

extern int insert_hash_table(HSNode_t **hash_table, Data_type_t data);
extern void hash_for_each(HSNode_t **hash_table);
extern HSNode_t *find_hash_table(HSNode_t **hash_table, char *name);

extern void destroy_hash_table(HSNode_t **hash_table);

#endif

（1）创建哈希表

 HSNode_t *hash_table[HASH_TABLE_MAX_SIZE] = {NULL};

（2）设计哈希函数

int hash_function(char key)
{
    if (key >= 'a' && key <= 'z')
    {
        return key-'a';
    }
    else if (key >= 'A' && key <= 'Z')
    {
        return key-'A';

    }
    else
    {
        return HASH_TABLE_MAX_SIZE-1;
    }
}

（3）插入数据

int insert_hash_table(HSNode_t **hash_table, Data_type_t data)
{
    int addr = hash_function(data.name[0]);

    //申请结点保存数据
    //头插
    //hash_table[addr];   //---->phead

    HSNode_t *pnode = malloc(sizeof(HSNode_t));
    if (NULL == pnode)
    {
        printf("malloc error\n");
        return -1;
    }
    pnode->data = data;
    pnode->pnext = NULL;

    if (NULL == hash_table[addr])
    {
        hash_table[addr] = pnode;
    }
    else
    {
        if (strcmp(pnode->data.name, hash_table[addr]->data.name) <= 0)
        {
            pnode->pnext = hash_table[addr];
            hash_table[addr] = pnode;
        }
        else
        {
            HSNode_t *p = hash_table[addr];
            while (p->pnext != NULL && (p->pnext->data.name, pnode->data.name) < 0)
            {
                p = p->pnext;
            }
            pnode->pnext = p->pnext;
            p->pnext = pnode;
        }
    }

    return 0;
}

（4）查找数据

HSNode_t *find_hash_table(HSNode_t **hash_table, char *name)
{
    int addr = hash_function(name[0]);

    HSNode_t *ptmp = hash_table[addr];
    while (ptmp)
    {
        if (0 == strncmp(ptmp->data.name, name, strlen(name)))
        {
            return ptmp;
        }
        ptmp = ptmp->pnext;
    }

    return NULL;
}

（5）销毁哈希表

void destroy_hash_table(HSNode_t **hash_table)
{
    for (int i = 0;i < HASH_TABLE_MAX_SIZE; i++)
    {
        HSNode_t *pdel = hash_table[i];

        while (hash_table[i] != NULL)
        {
            hash_table[i] = pdel->pnext;
            free(pdel);
            pdel = hash_table[i];
        }
    }
}

（6）遍历哈希表

void hash_for_each(HSNode_t **hash_table)
{
    for (int i = 0; i < HASH_TABLE_MAX_SIZE; ++i)
    {
        HSNode_t *ptmp = hash_table[i];
        while (ptmp)
        {
            printf("%s : %s\n", ptmp->data.name, ptmp->data.tel);
            ptmp = ptmp->pnext;
        }
        printf("\n");
    }
}