当前位置： 首页 > article >正文

数据结构(哈希表)

article 2025/1/4 5:03:02

背景

在对数据的日常处理中，查找是一项基本操作。通常，查找算法都是基于对比的，比如在一条链表中有n个节点，要找到其中的某个节点，最基本的思路就是从头到尾依次遍历每个节点，依次对比每个节点是否是想要的节点，这样的查找方式，称为顺序查找。很显然，顺序查找并不会给查找效率带来任何惊喜，其时间复杂度是提高查找效率的办法有很多，比如可以将这些数据按照二叉搜索树的逻辑结构组织起来，那么从根部开始查找某节点的时间复杂度就变成又或者使用顺序存储并将节点排序，那么每次查找可以从中间开始，进行折半查找，时间复杂度也是不管是顺序查找，还是改良后的BST、折半算法，查找一个节点都需要花一定的时间，之所以要花时间是因为存储节点的时候，节点的位置与节点的字段之间没有对应关系，因此我们需要一个个比对每一个节点，上述算法的差异只是改变了比对的规则，使得效率提高，但仍然是一个一个比对的过程。如果查找节点不需要比对，那就可以节省大量的时间。

哈希表

为了避免节点比对，我们可以在存储节点的时候，让节点的位置和节点本身做一个映射关系，这样一来就可以直接根据节点本身的特征值计算得到节点的位置了，注意：此时节点的位置不是“找”出来的，而是计算出来的。

这种存储数据的方式，被称为哈希表（Hash Table），也被称为散列表。时间复杂度是O(1)，即查找任何一个数据理论上不需要时间，直接给出数据所在的位置。

基本概念

哈希表的思路简单易懂，将相关的概念陈述如下：

  • 键（Key）：即用来作为节点特征的字段。比如学生的姓名、分数、学号等。

  • 值（Value）：节点存储的位置，也被称为哈希地址。

  • 冲突（Conflict）：当不同的键映射到相同的值时，称为冲突

  • 哈希函数（Hash Function）：将键转换为值的映射关系。

哈希存储就是将键映射为哈希地址，存入右侧的某个空位中。右侧实际上是一个数组，所谓的哈希地址一般指的是数组的下标，哈希表一般指的是该数组。

哈希表主要就是解决两件事情：

  1. 确定一个哈希函数
  2. 解决可能会出现的冲突问题

哈希函数

将节点某字段（即键）转换为哈希地址（值）的过程，就是哈希映射。举个例子，假设要将班级里的学生用哈希表的方式来存储，将姓名作为键，可以有如下哈希映射：

  • 将姓名笔画数，作为节点的哈希地址。
    在这里插入图片描述

从上面的例子可以看到，以笔画数作为映射规则是很不理想的，因为大多数人的姓名笔画数都集中在10-20之间，这不利于将各个元素均匀地分布在哈希表中，并且这种算法很容易有冲突。

哈希函数的选取没有一定之规，但一个大的原则是：尽量充分地使用键的信息，尽量使得值均匀分布。符合这个大原则的其中一种哈希函数，称为除留余数法，即：将键对不大于哈希表长度的最大质数求余，将其结果作为哈希地址。

以上面学生为例，假设班级中学生人数在50人左右，将哈希表数组的长度定为50，那么哈希函数可以是：
在这里插入图片描述

此处，47是不大于50的最大的质数，之所以不能大于50，是因为哈希地址最终是数组的下标，如果比数组的长度还大的话就可能会越界。选取质数则有利于值域分布更加均匀。另外，为了让数据分布更加均匀，可以使用姓名拼音的ASCII码之和来作为键。

采取这种除留余数法获得哈希地址后，映射关系变成：

在这里插入图片描述

可见，经过对哈希函数的改良，使得哈希地址分布更加均匀了，冲突概率也降低了。但从另一方面讲，冲突就像物理实验中的误差，可以被降低，但很多时候无法根除，比如上述例子，假如现在入学一位名字为马化腾的学生，那么将会出现：

在这里插入图片描述

此时，马化腾跟张三虽然姓名信息毫不相干，但是计算出来的哈希地址却是冲突的。如何解决冲突？这是哈希表的第二项重要工作。

解决冲突

1. 开放地址法
解决冲突跟选取哈希函数一样，是可以很灵活的。最简单的想法是：既然某个哈希地址已经有别的数据了，那就换一个位置。比如将数据挪到已冲突的位置的旁边，如果旁边还是冲突那么再试试旁边，这就是所谓的开发地址法解决冲突。

这种看似简单的做法，有很多弊端：

  1. 必须保证哈希表的总大小要大于数据节点数目，否则如果数据填满了整张哈希表，那么除非扩充哈希存储数组，否则不管怎么调整位置，都不可能找到空余的地方。
  2. 多个哈希值冲突的数据节点会在冲突点附近形成“堆积”，每个形成冲突的节点都要将前面冲突所走过的路线再走一遍。
  3. 由于节点所处的真实位置与其从哈希函数计算出来的理论位置可能不一致（被冲突就不一致了），这就导致一个位置的状态不是两种，而必须是三种：有节点、无节点、之前有现在无节点。

关于上述第3个弊端，可以用如下例子加以解释：

  • 张三入学时，根据哈希函数计算被安排到了43号桌，然后麻花藤入学时计算出来的哈希地址也是43号，于是小麻同学只能乖乖地坐在小张的旁边，44号桌。

  • 然后，小张退学了。

  • 然后，我们要查找小麻同学，根据哈希函数，计算出来的哈希地址是43，此时43号桌的状态如果是 没人 的话，那么就会误判以为班级里面没有小麻这位同学，于是产生了错误。

  • 解决这个谬误的办法，要将这样的43号做标记为 之前有人但现在无人 的状态，这样才能顺着解决冲突的办法挨个找去，最终才能找到小麻同学。

2. 链地址法
为了解决开放地址法的弊端，可以在冲突点处设置一条链表，让所有哈希地址冲突的节点链起来，这样就既无需担心节点数量超过哈希表大小，也无需设置节点的第三种状态。

假设有如下数据节点：

23，34，14，38，46，16，68，15，07，31，2623，34，14，38，46，16，68，15，07，31，26

假设按照如下除留余数法得到它们的哈希地址：

H(key)=key%13

练习实例

编写一个程序，产生若干长度与内容都随机的字符串，将字符串存入哈希表中，并在程序中提供查表算法演示。

解析：
使用除留余数法计算每个字符串的哈希地址，使用链地址法解决冲突问题。

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <strings.h>
#include <time.h>

#define SIZE 20

typedef int datatype;

struct node
{
    datatype data;
    struct node *next;
};

typedef struct
{
    unsigned long table_size;
    struct node **table_entry;

}hash_table;

void show(hash_table *ht, unsigned long pos, datatype data);

hash_table *init_ht(unsigned long size)
{
    hash_table *ht = malloc(sizeof(hash_table));
    ht->table_size = size;
    ht->table_entry = calloc(size, sizeof(struct node *));

    return ht;
}

void hash_add(datatype data, hash_table *ht)
{
    // 使用保留除数法，获得哈希地址（即数组的下标值）
    unsigned long hash_addr = data % (SIZE-1);

    struct node *new = malloc(sizeof(struct node));
    new->data = data;
    new->next = NULL;

    show(ht, hash_addr, data);
    printf("=================================\n");

    // 1：该哈希地址可用，直接将新节点放进去
    if(ht->table_entry[hash_addr] == NULL)
    {
        ht->table_entry[hash_addr] = new;
    }
    // 2：该哈希地址不可用，将新节点链到冲突链表的末尾
    else
    {
        struct node *p = ht->table_entry[hash_addr];
        while(p->next != NULL)
        {
            p = p->next;
        }
        p->next = new;
    }
}

void show(hash_table *ht, unsigned long pos, datatype data)
{
    struct node *p;

    int i;
    for(i=0; i<ht->table_size; i++)
    {
        p = ht->table_entry[i];

        printf("table_entry[%d]: ", i);

        if(p != NULL)
        {
            struct node *q = p;
            while(q != NULL)
            {
                printf("%d\t", q->data);
                q = q->next;
            }
        }
    
        if(pos == i)
        {
            printf("\t <-- %d\n", data);
        }
        else
        {
            printf("\n");
        }
    }
}

int main(void)
{
    hash_table *ht = init_ht(SIZE);

    srand(time(NULL));
    int i;
    for(i=0; i<10; i++)
    {
        hash_add(rand()%1000, ht);
        sleep(1);
    }
    show(ht, -1, -1);

    return 0;
}

该代码实现了一个使用哈希表解决冲突的散列表。

首先定义了一个结构体node，表示链表中的节点，包含一个整型数据data和指向下一个节点的指针next。

然后定义了一个结构体hash_table，表示哈希表，包含一个表的大小table_size和指向存储链表的数组的指针table_entry。

接着定义了函数init_ht，用于初始化哈希表，根据给定的大小创建哈希表并返回。

接下来是函数hash_add，用于向哈希表中添加元素。首先根据数据的哈希值计算哈希地址，然后创建一个新的节点，将数据保存在节点中。如果对应的哈希地址没有冲突，直接将新节点放入哈希表中；如果有冲突，将新节点加入到冲突链表的末尾。

最后是函数show，用于显示哈希表的内容。遍历整个哈希表，打印每个位置上的链表内容。如果指定了位置pos和数据data，则在对应位置显示指示箭头。

在main函数中，首先调用init_ht函数初始化哈希表。然后使用rand函数生成随机数，调用hash_add函数将随机数添加到哈希表中，并通过sleep函数暂停1秒。最后调用show函数显示哈希表的内容。

整个代码实现了使用哈希表解决冲突的散列表。


http://www.kler.cn/a/460322.html

相关文章：

  • 【详解】AndroidWebView的加载超时处理
  • 铁路轨道缺陷数据集，4278张原始图片，支持YOLO，PASICAL VOC XML，COCO JSON格式的标注，可识别是否有裂缝，和间隙缺陷
  • Redis 使用redisTemplate获取某个规则下的key的全量数据(示例Set结构)
  • SQL-leetcode-197. 上升的温度
  • Singleton: WebRTC中ThreadManager中的单例模式
  • 机器人C++开源库The Robotics Library (RL)使用手册（四）
  • 如何在TikTok上成功推广国际品牌？
  • HTML——20 自定义属性
  • 改进爬山算法之七：动态邻域爬山法（Dynamic Neighborhood Hill Climbing，DNHC）
  • 【项目实战】Apache JMeter HTTP 接口测试
  • CP AUTOSAR标准之FlexRayDriver(AUTOSAR_SWS_FlexRayDriver)（更新中……）
  • ROS2+OpenCV综合应用--9. AprilTag标签码识别
  • 深度学习中的迁移学习：如何利用现有模型加速训练？
  • Rust语言的数据库编程
  • 按照人们阅读Excel习惯来格式化BigDecimal
  • 头歌实训数据结构与算法-二叉树及其应用（第9关：二叉树的顺序存储及基本操作）
  • 云电脑市场正在爆发！2025新风口出现了？
  • 【QT】QT 的窗口坐标 信号与槽
  • opencv实现KNN算法识别图片数字
  • 网络基础入门到深入(3):网络协议-HTTP/S
  • 时间序列预测算法---LSTM
  • 网络爬虫性能提升：requests.Session的会话持久化策略
  • HTML——38.Span标签和字符实体
  • 优秀的 Verilog/FPGA开源项目介绍（十七）- AXI
  • 【翻译】优化加速像素着色器执行的方法
  • 打印进度条