• 【蓝桥杯冲击国赛计划第5天】哈希表


    在这里插入图片描述


    1. 哈希表(散列表)

    1.1 定义

    我们采用散列技术将记录存储在一块连续的存储空间中,这块连续的存储空间即称为哈希表(散列表)。而散列技术实际上就是 映射+存储 的过程。

    • 映射过程

      在这里插入图片描述

      在函数中,一个 x 只能对应一个 y ,但一个 y 可以对应多个 x 。而哈希表中一个 key 同样只能对应一个 value,而一个 value 同样可以对应多个 key。简单来说,key 是唯一的,但 value 不唯一。

      而要注意的是,key —> value 这个过程是单向的,无法反推。因为 value 可能对应多个 key。

    • 存储过程

      在这里插入图片描述

      通过映射,我们输入的多个 key,可以得到若干个 value,这里的 value 一般是 key 储存的位置,然后我们把 key 存入数组对应的 value 位中,这样就完成了哈希表的存储。散列主要是面向查找的存储结构,通过 key ,得到 value,通过表中的 value 位置,查看里面是否为 key。

    1.2 哈希表的作用

    我们为什么要那么麻烦,得专门做从 key --> value 的转化呢?或者说哈希表的作用是什么呢?

    当我们要判断现有数据集合中是否有某个元素,或者是否有满足条件的元素,如果我们使用数组的遍历去查找是否有某个元素,那么时间复杂度是 O(n)。而 Hash 算法通过 key --> value 的映射,得到哈希表中 key 存储的位置,然后再看里面的值是否为 key,这样它的时间复杂度为 O(1),因为数组中指定位置的查找的时间复杂度为 O(1) 。所以使用哈希表能大大减少我们查找的时间复杂度。


    1.3 如何映射

    从 key --> value 的方法有多种,我们介绍一种常用的方法:取余法。

    公式:value = key mod p

    这里的 p 可以当成我们给哈希表设置的最大长度,而 p 的设定,关乎我们的查找效率。p 太小,就很容易发生哈希冲突。而 p 太大又会增加消耗,p 的选取并没有什么特定的规范。

    1.4 哈希冲突

    我们在映射的时候说过:哈希表中一个 key 同样只能对应一个 value,而一个 value 可以对应多个 key。所以不同的 key 可以得到相同的 value ,这时候存储就会遇到问题(即哈希表中的 value 位置已经被占用),这个现象我们称为哈希冲突。

    在这里插入图片描述

    哈希冲突有多个解决方法,这里我们只介绍一种:建立公共溢出区。


    1.5 公共溢出区

    在这里插入图片描述

    我们将哈希表分为基本表和溢出表,将发生冲突的都存放在溢出表中。溢出表的本质就是一个普通数组。这时候,我查找的方式就发生了转变,先查哈希表,哈希表对应位置找不到,就直接在溢出表中遍历查找。


    1.6 哈希表的缺陷

    而哈希表的查找也不是万能的查找,存在一定的缺陷:

    1. 散列技术一般不适合存在太多的哈希冲突使用。

      因为这会降低查找效率,体现不出哈希表查找效率高的优点,并且如果一定要在这个情况下使用的话,还需要想办法消除冲突,这将花费大量时间,那么就失去了 O(1) 时间复杂度的优势,所以在存在大量的冲突情况下,我们就要弃用哈希表。

    2. 散列方法也不适用于范围查找,比如以下两个情况。

      • 查找最大值或者最小值

        因为哈希表的值是类似函数的,映射函数一个变量只能对应一个值,不知道其他值,也不能查找最大值、最小值,RMQ(区间最值问题)。

      • 查找范围记录

        比如查找小于 N 的数有多少个,是不能实现的,原因也是映射函数一个变量只能对应一个值,不知道其他值。


    1.7 实例「弗里的的语言」

    我们还是通过这个实例来了解一下,哈希表的定义和使用。

    题目描述

    小发明家弗里想创造一种新的语言,众所周知,发明一门语言是非常困难的,首先你就要克服一个困难就是,有大量的单词需要处理,现在弗里求助你帮他写一款程序,判断是否出现重复的两个单词。

    输入描述

    第 1 行,输入 N,代表共计创造了多少个单词。

    第 2 行至第 N+1 行,输入 N 个单词。

    1≤ N ≤10^4,保证字符串的总输入量不超过 10^6。

    输出描述

    输出仅一行。若有重复的单词,就输出重复单词,没有重复单词,就输出 NO,多个重复单词输出最先出现的。

    输入输出样例

    示例1

    输入

    6
    1fagas 
    dsafa32j
    lkiuopybncv
    hfgdjytr
    cncxfg
    sdhrest
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    输出

    NO
    
    • 1
    示例2

    输入

    5
    sdfggfds
    fgsdhsdf
    dsfhsdhr
    sdfhdfh
    sdfggfds
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    输出

    sdfggfds
    
    • 1

    运行限制

    • 最大运行时间:3s
    • 最大运行内存: 512M

    1.8 简单分析

    查找是否存在重复单词,这已经是很明显使用哈希表的题目了,因为哈希表可以判断是否存在某个元素。所以,这里使用哈希表来解题。


    1.9 哈希表和公共溢出区初始化

    这里 p 设置为相对较大的数就可以,但像 10001,10002 这些也不是不行,但设的太小会增加公共溢出区的查找,更容易发生哈希冲突。冲突后得去公共溢出区查找,由于公共溢出区每次需要从头开始遍历查找元素,时间消耗会变大。所以 p 设一个比较大的数可以减少公共溢出区的使用。

    p = 999999 # 设置相对较大的数,减少冲突
    value = ['']*p # 哈希表
    buffer = ['']*p # 溢出区
    buffer_number = 0 # 溢出区的个数
    
    • 1
    • 2
    • 3
    • 4

    1.10 hash 函数

    这里介绍一个 python 中的内置函数—— hash。因为我们数据是字符串,我们需要做映射的话,需要将字符串数字化,这里自己写也还好,但我们直接用 hash() 可以。hash 函数在每一次程序使用同一个字符串运行的值大不一样,但同一个程序运行出来的值时相等的。我们只要把 hash 得到的值当成是随机值即可,但同个变量的每一次运行自身的随机值相等。

    hash 函数的演示:

    if __name__ == '__main__':
        a1 = 'abs'
        a2 = 'abs'
        print(hash((a1)))
        print(hash((a2)))
    
    • 1
    • 2
    • 3
    • 4
    • 5

    第一次运行:

    在这里插入图片描述

    第二次运行:

    在这里插入图片描述


    1.11 数据插入表

    由取余法可以得到映射的位置 n ,数据在插入时,我们需要判断此时哈希表中位置 n 是否有值,如果值等于 key,说明该值重复,return False 。如果值是空的,就在这个位置插入 key,而还有一种情况就是位置上的值不是空的,但也不等于 key(发生了哈希冲突),这时候我们要到公共溢出区进行插入。

    公共溢出区的插入需要先查找有没有重复元素,如果找到,也是 return False。如果当前公共溢出区都找不到,那么就需要插入,插入后,溢出区的个数需要加1。
    所以整体思路就是:先查哈希再公共溢出区,有重复退出,没重复插入。

    def insTable(name):
        global buffer_number
        n = hash(name)%p # 映射的位置
        if value[n] == name: # 不用插入
            return False
        elif value[n] == "":
            value[n] = name
            return True
        else: # 产生哈希冲突
            for i in range(buffer_number):
                if buffer[i] == name:
                    return False
            # 过循环 --> 要增加溢出区元素个数
            buffer[buffer_number] = name
            buffer_number += 1
            return True
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    1.12 主函数

    if __name__ == '__main__':
        n = int(input())
        while n >0:
            n-=1
            res = 'NO'
            word = input() # 输入单词
            flag = insTable(word) # flag判断是否插入成功,插入成功:1,插入失败(重复):0
            if not flag: # 重复
                res = word # 结果替换,跳出循环
                break
    
        print(res)
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    2. 完整代码

    可在 我的仓库免费查看,如果无法使用可以及时私信我或在评论区指出,谢谢。


    本文主要参考蓝桥杯省赛14天夺奖冲刺营,有兴趣的可以自己在蓝桥杯官网搜索

    如有错误,敬请指正,欢迎交流🤝,谢谢♪(・ω・)ノ

  • 相关阅读:
    GBASE 8C——SQL参考6 sql语法(4)
    Git常用操作
    代码优化工具-测试程序执行时间-IDEAdebug+StopWatch
    云原生时代崛起的编程语言Go远程调用gRPC实战
    436-C++基础语法(71-80)
    无线电HAM:业余无线电入门【无线电操作人员考证】【干货收藏】【网络安全进阶】
    金仓数据库KingbaseES客户端编程接口指南-Gokb(2. 概述)
    CentOS 编译安装 nginx
    Django实战项目-学习任务系统-用户注册
    如何用 GPTs 帮你写科研项目申请书?
  • 原文地址:https://blog.csdn.net/m0_51302822/article/details/127820294