数据结构哈希表

Ameilide

231人浏览 · 2026-05-29 09:54:05

Ameilide · 2026-05-29 09:54:05 发布

哈希表

哈希存储（散列存储）

将要存储数据的关键字和数据存储位置之间建立起对应的函数关系

当数据存储时，根据该关系映射数据的存储位置；

查找数据时，利用该函数关系

目的：为了快速检索数据

哈希冲突/哈希矛盾：key1！=key2 f(key1) == f(key2)

解决哈希冲突的方法：

开放定址法

不额外使用链表等外部空间，所有元素都存放在哈希表的数组本身中，通过“寻找下一个可以位置”来解决冲突

适合数据量小，占用内存小的数据

链地址法

将哈希值相同的元素，存储在同一个链表中，哈希表的每个位置对应一条链表

即哈希表本质是存放链表头指针的数组

原理：对关键字计算哈希地址，映射到哈希表数组的某一下标。

若该位置无元素，直接存入。

若已有元素（发送冲突），则把新结点追加到对应链表尾部。

查找，删除时：先定位哈希数组下标，再遍历该位置链表。

特点：无堆积冲突，最大时间复杂度是O(n)

封装哈希链表结点

包含存放的数据，指向下一个结点结构体的指针

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

封装数据结构体

举例，通讯录姓名电话

typedef struct info
{
    char name[32];
    char tel[16];
}DataType_t;

宏定义哈希表大小

哈希表（哈希数组）大小有限向内存申请有限的堆空间

#define HASH_MAX_SIZE 27

哈希函数

传入参数为选取的关键字此处为姓名拼音的首字母，

利用（26个小写英文字母和26个大写英文字母）字符对应的ASIIC码表，返回0~25的数字，

若输入的不是汉字而是其他字符，返回哈希表空间数-1（26）。

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_MAX_SIZE-1;   
    }
}

插入函数

传入参数为哈希数组的指针（二级指针）(要修改数组中的头指针必须传二级指针，即哈希数组的的指针)，及存入哈希表的数据

调用malloc函数申请哈希结点的堆空间，进行是否申请成功判断

初始化结点：赋值数据，指针指空

调用哈希函数，用data.name[0] （即姓名拼音的首字母）计算哈希地址，定位到对应的桶

头插法，不用遍历链表找链尾，时间复杂度O(1)

新结点指向原链表头，更新链表头为新结点

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

    int addr = hash_function(data.name[0]);
    pnode->pnext = hash_table[addr];
    hash_table[addr] = pnode; //phead 数组名
    return 0;
}

遍历哈希表

传入参数为哈希数组的指针（二级指针）

外层for循环，以哈希数组的容量为条件，更改哈希数组的指针，遍历哈希表里的每一个桶

内层while循环，以指针不为空为条件，遍历输出并打印桶里的每一个数据，注意添加换行符

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

哈希表查找函数

返回哈希结点的函数

传入参数为哈希数组的指针（二级指针），及指向主函数中表示查找到的数据的变量的指针（变量的地址）

调用哈希函数，用姓名拼音首字母计算哈希地址，定位到对应的桶

定义局部变量表示这个桶的链表头结点

while循环，遍历桶里的整条链表，调用strcmp函数，比较姓名，一致时直接返回结点

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 != NULL)
    {
        if(0 == strcmp(ptmp->data.name,name))
        {
            return ptmp;
        }
        ptmp = ptmp->pnext;
    }
    return NULL;
}

销毁哈希表函数

传入参数为哈希数组的指针（二级指针）

外层for循环，以哈希数组容量为条件，遍历每一个桶，定义局部变量表示桶的链表头结点

内层while循环，循环删除桶里的所有结点，采用头删法，

原头结点的下一个结点成为头结点，释放原头结点的内存，变量指针移动到下一个结点，继续删除

void destory_hash_table(HSNode_t**hash_table)
{
    for(int i = 0;i < HASH_MAX_SIZE;i++)
    {
        HSNode_t*ptmp = hash_table[i];
        while(hash_table[i]!= NULL)
        {
            hash_table[i] = ptmp->pnext;
            free(ptmp);
            ptmp = hash_table[i];
        }
    }
}