查找算法之散列表

一.说明

刚好复习数据结构,前面几篇博客我们知道了顺序查找、二分查找、分块查找、树形查找(二叉排序树、平衡二叉树、红黑树、B树和B+树),这一篇博客介绍常用查找算法中的最后一个算法——散列表(哈希查找)。

同时,刚好参加的新星计划:数据结构与算法通道在周末结束,这一篇博客也是本周的学习任务。

二.散列表的基本概念

1.名词解释

散列表(Hash table)是一种基于哈希表实现的数据结构,它通过将给定的键值映射到一个特定的索引位置来存储和查找数据元素。散列表通常使用数组作为底层数据结构,并且需要一个可靠的散列函数来计算每个键对应的索引位置。

散列函数(Hash function)是一种将任意长度的输入数据映射到固定长度输出的函数。散列函数通常用于计算散列表中元素的索引位置,它将每个键值转换为一个唯一的整数值,这个整数值可以作为该元素在散列表中的索引。散列函数的设计非常重要,因为它直接影响散列表的性能和效率。一个好的散列函数应当尽可能避免哈希碰撞,即不同的键值映射到相同的索引位置。

哈希冲突(Hash collision)指的是两个或多个键值被散列到了相同的索引位置。由于散列表的大小是有限的,因此哈希冲突是不可避免的。当发生哈希冲突时,我们需要采取一些方法来解决它,以确保散列表的正确性和效率。常见的解决哈希冲突的方法包括链式存储法和开放地址法等。

同义词(Synonyms)是指具有相同或相似含义的单词。在散列表中,不同的键值可能被映射到相同的索引位置,这些键值即为同义词。解决同义词问题的方法之一是使用拉链法进行链式存储,在相同的散列值下将多个数据元素连接成一个链表,以避免发生冲突。

2.百度补充

散列表(Hash table)是一种常见的数据结构,它具有快速插入、查找和删除元素的能力。散列表通过将每个元素映射到一个唯一的索引位置来实现这些操作,这个索引位置可以称为哈希值或散列值。

散列表包含一个固定大小的数组,通常被初始化为空。当要插入一个元素时,首先需要计算该元素的哈希值,并将其作为数组索引来存储该元素。如果两个元素具有相同的哈希值,则会发生哈希冲突,解决哈希冲突的方法包括使用链式存储或开放地址法等。

在查询一个元素时,我们首先计算该元素的哈希值,并在数组中检查该位置是否存在元素。如果该位置为空,则表示该元素不存在于散列表中;否则,需要进行进一步的比较来确定该元素是否是所需的元素。

散列表是一种高效的数据结构,在大多数情况下,它的插入、查找和删除操作的时间复杂度都是 O(1)。但是,由于哈希冲突的存在,最坏情况下的时间复杂度可能会退化到 O(n),因此合理的哈希函数设计和处理哈希冲突的方法非常重要。

3.个人补充

散列表 == 哈希表

散列函数 == 哈希函数

散列查找 == 哈希查找

它们是在不同编程语言的不同称呼而已,其实本质上是一个概念。

三.散列函数的构造方法

1.设计注意事项

设计散列函数时需要注意以下几个点:

  1. 均匀性:散列函数应该将输入的数据均匀地散布到整个哈希表中,这样可以使得每个桶中的元素数量尽可能平衡,避免出现某些桶特别拥挤而导致性能急剧下降的情况。
  2. 碰撞率:碰撞是指两个不同的键映射到了同一个散列表位置的情况。散列函数的设计应该尽可能减少碰撞的发生。一般来说,可以采用开放寻址法或者链式哈希表来解决碰撞问题。但是过多的碰撞也会影响哈希表的性能,因此需要在散列函数设计中尽量避免碰撞。
  3. 易计算:散列函数的计算速度应该足够快,否则会影响哈希表的性能。不同类型的数据可能需要使用不同的散列函数实现。
  4. 抗攻击:散列函数应该能够有效地防止故意构造的输入数据,如恶意攻击者故意制造出大量的碰撞,使得哈希表的性能急剧下降。
  5. 随机性:散列函数应该尽可能地随机,这样可以降低攻击者进行散列冲突攻击的难度。随机性可以通过在散列函数中使用随机数或者加盐等方式实现。

2.除留余数法

这是一种最简单、最常用的方法,假设散列表表长为m,取一个不大于m但最接近m的质数p,利用以下公式把关键字转换成散列地址。

散列函数为 H(key) = key % p

除留余数法的关键是选好p,使得每个关键字通过该函数转换后等概率地映射到散列空间上的任意一个地址,从而尽可能减少冲突的可能性。

适用场景:较为常用,只要关键字是整数即可

3.直接定址法

直接取关键字的某个线性线性函数值为散列地址,散列函数为

H(key) = key 或 H(key) = a*key + b

式中,a和b是常数。这种方法最简单,且不会产生冲突。他适合关键字的分布基本连续的情况,若关键字分布不连续,空位较多、则会造成存储空间的浪费。

适用场景:关键字分布基本连续

4.数字分析法

数字分析法是散列函数构造方法之一,它的基本思想是利用待存记录的关键字中的数字特征来构造散列地址。

具体地说,数字分析法将关键字看做一个r进制数(r通常取10),然后从右往左取出若干个数位,将它们组成一个新的数,再对哈希表长m取模,作为该记录的散列地址。如果不足m位,则在左边补0。

这里需要注意的是,选择哪些数位作为新数的数位,以及新数的长度,都会直接影响到散列的性能。一般来说,应该选择数字分布比较均匀的数位,并且尽可能地选取多的数位才能保证较好的散列效果。

需要注意的是,数字分析法虽然简单易行,但是它对数据的要求比较高,而且也容易受到数据规律的影响,因此其散列性能可能并不理想。在实际应用中,还需要根据具体情况,结合其他散列函数构造方法,综合考虑选取最合适的散列函数。

5.平方取中法

平方取中法是散列函数构造方法之一,它的基本思想是将关键字的平方值取中间几位作为散列地址。

具体地说,假设关键字为n位数字,首先将其平方得到一个2n位的数,然后从中间取出m(通常取m=3或4)位数作为散列地址。如果不足m位,则在左边右边补0,如果超过m位,则截取中间的m位。

这种方法的优点是简单易行,且能够较好地利用关键字的各个位上的信息,提高散列性能。但是需要注意的是,在实际应用中,由于平方操作可能导致结果溢出,因此需要对溢出进行处理,以免影响散列效果。

总的来说,平方取中法是一种比较基础的散列函数构造方法,适用于一些简单的应用场景。在实际应用中,还需要根据具体情况选择其他散列函数构造方法,并综合考虑多个因素,如时间、空间复杂度等,才能构造出最优秀的散列函数。

四.处理冲突的方法

1.拉链法

拉链法(链接法、链地址法)(Chaining)是一种使用哈希表来解决冲突的方法,也称为链接法。在这种方法中,哈希表中每个位置都存储一个链表,如果多个键值映射到同一个位置,则它们将被添加到同一个链表中。

当需要查找一个键时,先计算它的哈希值,然后定位到对应的链表,并在链表中顺序查找。由于哈希表的大小有限,而数据量可能很大,所以在设计时需要考虑好哈希函数的设计,以减少冲突的发生,从而提高查询效率。

当添加一个新的键值对时,也需要先计算其哈希值,然后定位到对应的链表,将其添加到链表的末尾即可。

拉链法虽然处理冲突的效果较好,但它会占用更多的内存空间,因为每个位置都需要维护一个链表。此外,在遍历整个链表时,查询效率可能会受到影响,特别是当链表过长时。

2.开放地址法

开放地址法是一种常见的解决哈希冲突问题的方法。

当使用哈希表时,可能会出现多个键被映射到同一个哈希槽上,这就是哈希冲突。开放地址法的主要思想是在发生冲突时,继续探测下一个哈希槽,直到找到空槽或者已经探测过所有的槽为止。

开放地址法有几种不同的探测方法,包括线性探测、二次探测、双重哈希等。其中,线性探测是最简单、最常用的一种方法,其基本思路是:如果当前哈希槽已经被占用,则依次查看下一个槽,直到找到一个空槽。

例如,假设使用哈希表来存储字符串类型的键,哈希函数为将字符串转换为整数后取余数,当出现冲突时,采用线性探测。当插入键值对时,如果计算出的哈希值已经被占用,则从该位置往后一个一个查找,直到找到一个空槽为止。如果整个哈希表都被查找过了,但仍然没有找到空槽,那么就需要扩容,重新分配内存空间。

虽然开放地址法是一种简单有效的解决哈希冲突的方法,但是它仍然存在一些问题,例如当哈希表中元素过多时,探测时间会变长,甚至可能导致性能下降。因此,在实际应用中,需要根据具体情况选择合适的哈希函数和解决冲突的方法。

五.散列查找及性能分析

散列查找(Hash Lookup)是一种基于哈希表的查找算法。它通过将关键字映射到哈希表的一个位置上,从而加快查找速度。在散列查找中,哈希函数起着关键作用。哈希函数可以将待查找的关键字映射到哈希表中的一个位置上,并且保证不同的关键字映射到不同的位置上。

散列查找的时间复杂度通常为O(1),因为只需要计算一次哈希值即可在常数时间内访问到对应的数据。但是,在实际应用中,由于哈希冲突的出现,可能会导致查找效率下降。因此,如何解决哈希冲突也是散列查找性能优化的关键。

一些常见的解决哈希冲突的方法包括:链式法、开放地址法等。在使用链式法时,每个哈希槽都保存一个指向链表头结点的指针。如果哈希冲突发生,就将新元素插入到对应槽的链表尾部。在使用开放地址法时,当哈希冲突发生时,可以尝试探测下一个空槽,直到找到合适的位置为止。

在实际应用中,选择合适的哈希函数和解决哈希冲突的方法非常重要。一个好的哈希函数应当具有较低的哈希冲突率,并且能够均匀地将关键字映射到哈希表上。而解决哈希冲突的方法则需要根据具体情况来选取,不同的方法对应着不同的性能表现。

总之,散列查找是一种高效的查找算法,在大规模数据处理中得到了广泛的应用。在实际应用中,通过优化哈希函数和解决哈希冲突的方法,可以进一步提高散列查找的性能。

六.C语言实现散列查找

下面是一个简单的C语言实现散列查找的例子,使用链式法解决哈希冲突:

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

#define TABLE_SIZE 10

// 定义哈希表中的数据结构
typedef struct node {
    char key[20]; // 键值
    int value; // 值
    struct node *next; // 指向下一个节点的指针
} Node;

// 定义哈希表结构体
typedef struct hashtable {
    Node *table[TABLE_SIZE]; // 存储元素的数组
} Hashtable;

// 初始化哈希表
void initHashtable(Hashtable *ht) {
    int i;
    for (i = 0; i < TABLE_SIZE; i++) {
        ht->table[i] = NULL;
    }
}

// 计算哈希值
int hash(char *key) {
    int sum, i;
    for (sum = 0, i = 0; key[i] != '\0'; i++) {
        sum += key[i];
    }
    return sum % TABLE_SIZE;
}

// 向哈希表中插入元素
void insertElement(Hashtable *ht, char *key, int value) {
    int h = hash(key);
    // 创建新节点
    Node *newNode = (Node *) malloc(sizeof(Node));
    strcpy(newNode->key, key);
    newNode->value = value;
    newNode->next = NULL;

    if (ht->table[h] == NULL) { // 如果该位置没有元素,则直接插入
        ht->table[h] = newNode;
    } else { // 如果该位置已经有元素,则使用链式法解决冲突
        Node *p = ht->table[h];
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = newNode;
    }
}

// 从哈希表中查找元素
int findElement(Hashtable *ht, char *key) {
    int h = hash(key);
    Node *p = ht->table[h];
    while (p != NULL) {
        if (strcmp(p->key, key) == 0) {
            return p->value;
        }
        p = p->next;
    }
    return -1; // 没有找到
}

// 测试函数
int main() {
    Hashtable ht;
    initHashtable(&ht);

    insertElement(&ht, "apple", 10);
    insertElement(&ht, "banana", 20);
    insertElement(&ht, "orange", 30);

    printf("The value of apple is %d\n", findElement(&ht, "apple"));
    printf("The value of banana is %d\n", findElement(&ht, "banana"));
    printf("The value of orange is %d\n", findElement(&ht, "orange"));

    return 0;
}

在上面的例子中,我们定义了一个哈希表结构体Hashtable,其中包含一个数组table,用于存储元素。每个元素都是一个指向链表头节点的指针,如果哈希冲突发生,则将新元素插入到对应槽的链表尾部。

在实现中,我们先通过hash函数计算出待查找元素的哈希值,然后根据哈希值找到元素所在槽的指针。如果该指针为NULL,则说明该位置还没有元素,直接插入即可;否则,我们需要遍历链表,将新元素插入到链表尾部。

在查找时,我们也是先计算出哈希值,然后遍历对应槽的链表,在其中查找待查找的元素。如果找到了,则返回对应的值;否则,返回-1表示没有找到。

以上就是一个简单的C语言实现散列查找的例子,你可以参考此例子来实现自己的散列查找程序。

说明:

新星计划:数据结构与算法,@西安第一深情,创作打卡4!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/24170.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C Primer Plus第四章编程练习答案

学完C语言之后&#xff0c;我就去阅读《C Primer Plus》这本经典的C语言书籍&#xff0c;对每一章的编程练习题都做了相关的解答&#xff0c;仅仅代表着我个人的解答思路&#xff0c;如有错误&#xff0c;请各位大佬帮忙点出&#xff01; 1.编写一个程序&#xff0c;提示用户输…

自学网络安全最细规划(建议收藏)

01 什么是网络安全 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、“安全运营”、“安全运维”则研究防御技术。 无论网络、Web、移动、桌面、云等哪个领域&#xff0c;都有攻与防两面…

自古以来,反射也是兵家必争之地

成文耗时1小时&#xff0c;阅读5min&#xff0c;有用指数5颗星。 这几天收到一个战术性需求&#xff0c;将一大坨字段序列化为特定格式的字符串。 大概是下表&#xff1a; 序号字段名描述是否必填0logVersion日志版本是1productName产品是2serviceName服务是.........25extend3…

8项seo的日常工作

SEO的日常工作涵盖了一系列任务和活动&#xff0c;旨在优化网站以提高在搜索引擎中的排名和可见性。 以下是SEO的日常工作内容&#xff1a; 关键词研究和优化&#xff1a;定期进行关键词研究&#xff0c;寻找与目标受众和业务相关的热门关键词。优化网站内容、标题、元描述和链…

这些脑洞大开的论文标题,也太有创意了O(∩_∩)O

microRNAs啊microRNAs&#xff0c;谁是世界上最致命的髓母细胞瘤microRNAs&#xff1f; 这个标题很容易让人联想到白雪公主后妈说的那句话&#xff1a;Mirror mirror on the wall, who is the fairest of them all? 02 一氧化碳&#xff1a;勇踏NO未至之境 NO 指 nitric oxide…

合并两个有序链表(java)

leetcode 21题&#xff1a;合并两个有序链表 题目描述解题思路&#xff1a;链表的其它题型。 题目描述 leetcode21题&#xff1a;合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例&#xff1a; 输入&…

MySQL 数值函数

文章目录 数值函数1. abs(num)2. ceil(num)3. floor(num)4. mod(num1,num2)5. rand()6. round(num,n)7. truncate(num,n)8. sqrt(num) 数值函数 数值函数用来处理数值方面的运算&#xff0c;能够提高用户的工作效率。常用的数值函数如下表所示&#xff0c;函数括号内为输入的参…

四足机器人A1目标跟踪

四足机器人A1目标跟踪 前期准备工作1.安装TeamViewer2.将四足机器人所有线连接好3.将四足机器人调至运动模式 运行流程1.开机阶段2.运行阶段 效果展示代码配置 前期准备工作 1.安装TeamViewer 由于外接屏幕损坏&#xff0c;故四足机器人内部配置了TeamViewer&#xff0c;因此…

【Linux】线程同步

文章目录 条件变量相关函数初始化条件变量-pthread_cond_init销毁条件变量-pthread_cond_destroy等待条件变量-pthread_cond_wait唤醒等待条件变量pthread_cond_broadcastpthread_cond_signal 小例子关于等待函数的补充条件变量使用规范 条件变量相关函数 初始化条件变量-pthr…

如何让自动化测试框架更自动化?

一、引言 ​对于大厂的同学来说&#xff0c;接口自动化是个老生常谈的话题了&#xff0c;毕竟每年的MTSC大会议题都已经能佐证了&#xff0c;不是大数据测试&#xff0c;就是AI测试等等&#xff08;越来越高大上了&#xff09;。不可否认这些专项的方向是质量智能化发展的方向&…

IMX6ULL裸机篇之IIC协议

一. IIC实验简介 I2C 是最常用的通信接口&#xff0c;众多的传感器都会提供 I2C 接口来和主控相连。 比如摄像头、 加速度计、触摸屏等。 I.MX6U-ALPHA开发板 使用 I2C1 接口连接了一个距离传感器 AP3216C &#xff0c;本章我们就来学习如何使用 I.MX6U 的 I2C 接口…

【JavaSE】Java基础语法(十):构造方法

文章目录 ⛄1. 构造方法的格式和执行时机⛄2. 构造方法的作用⛄3. 构造方法的特点⛄4. 构造方法的注意事项⛄5. 构造方法为什么不能被重写 在面向对象编程的思想中&#xff0c;构造方法&#xff08;Constructor&#xff09;是一个特殊的函数&#xff0c;用于创建和初始化类的对…

华为OD机试之模拟商场优惠打折(Java源码)

模拟商场优惠打折 题目描述 模拟商场优惠打折&#xff0c;有三种优惠券可以用&#xff0c;满减券、打折券和无门槛券。 满减券&#xff1a;满100减10&#xff0c;满200减20&#xff0c;满300减30&#xff0c;满400减40&#xff0c;以此类推不限制使用&#xff1b; 打折券&…

GoWeb -- gin框架的入门和使用

认识gin go流行的web框架 go从诞生之初就带有浓重的开源属性&#xff0c;其原生库已经很强大&#xff0c;即使不依赖框架&#xff0c;也能进行高性能开发&#xff0c;又因为其语言并没有一定的设计标准&#xff0c;所以较为灵活&#xff0c;也就诞生了众多的框架&#xff0c;各…

视频怎么加水印?如何录制带水印的视频?

案例&#xff1a;如何给视频添加水印&#xff1f; 【我发布在短视频平台的视频&#xff0c;总是被别人盗用&#xff0c;我想给自己的视频添加水印。有没有视频添加水印的方法&#xff1f;在线等&#xff01;】 很多视频制作者或者爱好者&#xff0c;都希望自己的视频作品得到…

腾讯云轻量服务器镜像安装宝塔Linux面板怎么使用?

腾讯云轻量应用服务器宝塔面板怎么用&#xff1f;轻量应用服务器如何安装宝塔面板&#xff1f;在镜像中选择宝塔Linux面板腾讯云专享版&#xff0c;在轻量服务器防火墙中开启8888端口号&#xff0c;然后远程连接到轻量服务器执行宝塔面板账号密码查询命令&#xff0c;最后登录和…

【P31】JMeter 循环控制器(Loop Controller)

这文章目录 一、循环控制器&#xff08;Loop Controller&#xff09;参数说明二、测试计划设计2.1、设置循环次数2.2、勾选永远2.3、设置线程组的持续时间 一、循环控制器&#xff08;Loop Controller&#xff09;参数说明 可以对部分逻辑按常量进行循环迭代 选择线程组右键 …

Lua学习笔记:C/C++和Lua的相互调用

前言 本篇在讲什么 C/C和Lua的相互调用 本篇适合什么 适合初学Lua的小白 适合需要C/C和lua结合开发的人 本篇需要什么 对Lua语法有简单认知 对C/C语法有简单认知 依赖Lua5.1的环境 依赖VS 2017编辑器 本篇的特色 具有全流程的图文教学 重实践&#xff0c;轻理论&…

【2023 · CANN训练营第一季】基于昇腾910的TF网络脚本训练(ModelArts平台)

准备工作: 1.注册华为云账号&#xff0c;获取AK/SAK&#xff0c;授权ModelArts&#xff0c;并申请华为云代金券 2.获取训练数据集&#xff0c;并进行数据预处理&#xff0c;比如离线制作成tfrecords(建议&#xff0c;可选) 3.将数据集(训练脚本)上传到OBS 4.安装PycharmIDE及To…

Word控件Spire.Doc 【其他】教程(4):在 Word 中插入上标和下标

Spire.Doc for .NET是一款专门对 Word 文档进行操作的 .NET 类库。在于帮助开发人员无需安装 Microsoft Word情况下&#xff0c;轻松快捷高效地创建、编辑、转换和打印 Microsoft Word 文档。拥有近10年专业开发经验Spire系列办公文档开发工具&#xff0c;专注于创建、编辑、转…
最新文章