算法数据结构基础——哈希表(Hash Table)

这篇具有很好参考价值的文章主要介绍了算法数据结构基础——哈希表(Hash Table)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 哈希表简介

哈希表(Hash Table):也叫做散列表。是根据关键码值(Key Value)直接进行访问的数据结构。

哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」,把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做「哈希函数(散列函数)」,存放记录的数组叫做「哈希表(散列表)」。

哈希表的关键思想是使用哈希函数,将键 key 映射到对应表的某个区块中。我们可以将算法思想分为两个部分:

  • 向哈希表中插入一个关键码值:哈希函数决定该关键字的对应值应该存放到表中的哪个区块,并将对应值存放到该区块中。

  • 在哈希表中搜索一个关键码值:使用相同的哈希函数从哈希表中查找对应的区块,并在特定的区块搜索该关键字对应的值。

哈希表的原理示例图如下所示:

哈希表,算法面试精选汇编,数据结构,散列表,算法,哈希表,Hash Table

在上图例子中,我们使用 value = Hash(key) = key // 1000 作为哈希函数。// 符号代表整除。我们以这个例子来说明一下哈希表的插入和查找策略。

  • 向哈希表中插入一个关键码值:通过哈希函数解析关键字,并将对应值存放到该区块中。

    • 比如:0138 通过哈希函数 Hash(key) = 0138 // 100 = 0,得出应将 0138 分配到0 所在的区块中。

  • 在哈希表中搜索一个关键码值:通过哈希函数解析关键字,并在特定的区块搜索该关键字对应的值。

    • 比如:查找 2321,通过哈希函数,得出 2321 应该在 2 所对应的区块中。然后我们从 2 对应的区块中继续搜索,并在 2 对应的区块中成功找到了 2321

    • 比如:查找 3214,通过哈希函数,得出 3214 应该在 3 所对应的区块中。然后我们从 3 对应的区块中继续搜索,但并没有找到对应值,则说明 3214 不在哈希表中。

哈希表在生活中的应用也很广泛,其中一个常见例子就是「查字典」。

比如为了查找 这个字的具体意思,我们在字典中根据这个字的拼音索引 zan,查找到对应的页码为 599。然后我们就可以翻到字典的第 599 页查看 字相关的解释了。

哈希表,算法面试精选汇编,数据结构,散列表,算法,哈希表,Hash Table

在这个例子中:

  • 存放所有拼音和对应地址的表可以看做是 「哈希表」

  • 字的拼音索引 zan 可以看做是哈希表中的 「关键字 key

  • 根据拼音索引 zan 来确定字对应页码的过程可以看做是哈希表中的 「哈希函数 Hash(key)

  • 查找到的对应页码 599 可以看做是哈希表中的 「哈希地址 value

2. 哈希函数

哈希函数(Hash Function):将哈希表中元素的关键键值映射为元素存储位置的函数。

哈希函数是哈希表中最重要的部分。一般来说,哈希函数会满足以下几个条件:

  • 哈希函数应该易于计算,并且尽量使计算出来的索引值均匀分布。

  • 哈希函数计算得到的哈希值是一个固定长度的输出值。

  • 如果 Hash(key1) 不等于 Hash(key2),那么 key1key2 一定不相等。

  • 如果 Hash(key1) 等于 Hash(key2),那么 key1key2 可能相等,也可能不相等(会发生哈希碰撞)。

在哈希表的实际应用中,关键字的类型除了数字类,还有可能是字符串类型、浮点数类型、大整数类型,甚至还有可能是几种类型的组合。一般我们会将各种类型的关键字先转换为整数类型,再通过哈希函数,将其映射到哈希表中。

而关于整数类型的关键字,通常用到的哈希函数方法有:直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。下面我们介绍几个常用的哈希函数方法。

2.1 直接定址法

  • 直接定址法:取关键字本身 / 关键字的某个线性函数值 作为哈希地址。即:Hash(key) = key 或者 Hash(key) = a * key + b,其中 ab 为常数。

这种方法计算最简单,且不会产生冲突。适合于关键字分布基本连续的情况,如果关键字分布不连续,空位较多,则会造成存储空间的浪费。

举一个例子,假设我们有一个记录了从 1 岁到 100 岁的人口数字统计表。其中年龄为关键字,哈希函数取关键字自身,如下表所示。

年龄 1 2 3 ... 25 26 27 ... 100
人数 3000 2000 5000 ... 1050 ... ... ... ...

比如我们想要查询 25 岁的人有多少,则只要查询表中第 25 项即可。

2.2 除留余数法

  • 除留余数法:假设哈希表的表长为 m,取一个不大于 m 但接近或等于 m 的质数 p,利用取模运算,将关键字转换为哈希地址。即:Hash(key) = key % p,其中 p 为不大于 m 的质数。

这也是一种简单且常用的哈希函数方法。其关键点在于 p 的选择。根据经验而言,一般 p 取素数或者 m,这样可以尽可能的减少冲突。

比如我们需要将 7 个数 [432, 5, 128, 193, 92, 111, 88] 存储在 11 个区块中(长度为 11 的数组),通过除留余数法将这 7 个数应分别位于如下地址:

索引 00 01 02 03 04 05 06 07 08 09 10
数据 88 111 432 92 5 193 128

2.3 平方取中法

  • 平方取中法:先通过求关键字平方值的方式扩大相近数之间的差别,然后根据表长度取关键字平方值的中间几位数为哈希地址。

    • 比如:Hash(key) = (key * key) // 100 % 1000,先计算平方,去除末尾的 2 位数,再取中间 3 位数作为哈希地址。

这种方法因为关键字平方值的中间几位数和原关键字的每一位数都相关,所以产生的哈希地址也比较均匀,有利于减少冲突的发生。

2.4 基数转换法

  • 基数转换法:将关键字看成另一种进制的数再转换成原来进制的数,然后选其中几位作为哈希地址。

    • 比如,将关键字看做是 13 进制的数,再将其转变为 10 进制的数,将其作为哈希地址。

343246 为例,哈希地址计算方式如下:

$343246{13} = 3 \times 13^5 + 4 \times 13^4 + 3 \times 13^3 + 2 \times 13^2 + 4 \times 13^1 + 6 \times 13^0 = 1235110{10}$

3. 哈希冲突

哈希冲突(Hash Collision):不同的关键字通过同一个哈希函数可能得到同一哈希地址,即 key1 ≠ key2,而 Hash(key1) = Hash(key2),这种现象称为哈希冲突。

理想状态下,我们的哈希函数是完美的一对一映射,即一个关键字(key)对应一个值(value),不需要处理冲突。但是一般情况下,不同的关键字 key 可能对应了同一个值 value,这就发生了哈希冲突。

设计再好的哈希函数也无法完全避免哈希冲突。所以就需要通过一定的方法来解决哈希冲突问题。常用的哈希冲突解决方法主要是两类:「开放地址法(Open Addressing)」「链地址法(Chaining)」

3.1 开放地址法

开放地址法(Open Addressing):指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时,处理冲突时需要尝试另外的单元,直到找到空的单元为止。

当发生冲突时,开放地址法按照下面的方法求得后继哈希地址:H(i) = (Hash(key) + F(i)) % mi = 1, 2, 3, ..., n (n ≤ m - 1)

  • H(i) 是在处理冲突中得到的地址序列。即在第 1 次冲突(i = 1)时经过处理得到一个新地址 H(1),如果在 H(1) 处仍然发生冲突(i = 2)时经过处理时得到另一个新地址 H(2) …… 如此下去,直到求得的 H(n) 不再发生冲突。

  • Hash(key) 是哈希函数,m 是哈希表表长,对哈希表长取余的目的是为了使得到的下一个地址一定落在哈希表中。

  • F(i) 是冲突解决方法,取法可以有以下几种:

    • 线性探测法:$F(i) = 1, 2, 3, ..., m - 1$。

    • 二次探测法:$F(i) = 1^2, -1^2, 2^2, -2^2, ..., \pm n^2(n \le m / 2)$。

    • 伪随机数序列:$F(i) = 伪随机数序列$。

举个例子说说明一下如何用以上三种冲突解决方法处理冲突,并得到新地址 H(i)。例如,在长度为 11 的哈希表中已经填有关键字分别为 284918 的记录(哈希函数为 Hash(key) = key % 11)。现在将插入关键字为 38 的新纪录。根据哈希函数得到的哈希地址为 5,产生冲突。接下来分别使用这三种冲突解决方法处理冲突。

  • 使用线性探测法:得到下一个地址 H(1) = (5 + 1) % 11 = 6,仍然冲突;继续求出 H(2) = (5 + 2) % 11 = 7,仍然冲突;继续求出 H(3) = (5 + 3) % 11 = 88 对应的地址为空,处理冲突过程结束,记录填入哈希表中序号为 8 的位置。

  • 使用二次探测法:得到下一个地址 H(1) = (5 + 1*1) % 11 = 6,仍然冲突;继续求出 H(2) = (5 - 1*1) % 11 = 44 对应的地址为空,处理冲突过程结束,记录填入哈希表中序号为 4 的位置。

  • 使用伪随机数序列:假设伪随机数为 9,则得到下一个地址 H(1) = (9 + 5) % 11 = 33 对应的地址为空,处理冲突过程结束,记录填入哈希表中序号为 3 的位置。

使用这三种方法处理冲突的结果如下图所示:

哈希表,算法面试精选汇编,数据结构,散列表,算法,哈希表,Hash Table

3.2 链地址法

链地址法(Chaining):将具有相同哈希地址的元素(或记录)存储在同一个线性链表中。

链地址法是一种更加常用的哈希冲突解决方法。相比于开放地址法,链地址法更加简单。

我们假设哈希函数产生的哈希地址区间为 [0, m - 1],哈希表的表长为 m。则可以将哈希表定义为一个有 m 个头节点组成的链表指针数组 T

  • 这样在插入关键字的时候,我们只需要通过哈希函数 Hash(key) 计算出对应的哈希地址 i,然后将其以链表节点的形式插入到以 T[i] 为头节点的单链表中。在链表中插入位置可以在表头或表尾,也可以在中间。如果每次插入位置为表头,则插入操作的时间复杂度为 $O(1)$。

  • 而在在查询关键字的时候,我们只需要通过哈希函数 Hash(key) 计算出对应的哈希地址 i,然后将对应位置上的链表整个扫描一遍,比较链表中每个链节点的键值与查询的键值是否一致。查询操作的时间复杂度跟链表的长度 k 成正比,也就是 $O(k)$。对于哈希地址比较均匀的哈希函数来说,理论上讲,k = n // m,其中 n 为关键字的个数,m 为哈希表的表长。

举个例子来说明如何使用链地址法处理冲突。假设现在要存入的关键字集合 keys = [88, 60, 65, 69, 90, 39, 07, 06, 14, 44, 52, 70, 21, 45, 19, 32]。再假定哈希函数为 Hash(key) = key % 13,哈希表的表长 m = 13,哈希地址范围为 [0, m - 1]。将这些关键字使用链地址法处理冲突,并按顺序加入哈希表中(图示为插入链表表尾位置),最终得到的哈希表如下图所示。

哈希表,算法面试精选汇编,数据结构,散列表,算法,哈希表,Hash Table

相对于开放地址法,采用链地址法处理冲突要多占用一些存储空间(主要是链节点占用空间)。但它可以减少在进行插入和查找具有相同哈希地址的关键字的操作过程中的平均查找长度。这是因为在链地址法中,待比较的关键字都是具有相同哈希地址的元素,而在开放地址法中,待比较的关键字不仅包含具有相同哈希地址的元素,而且还包含哈希地址不相同的元素。

4. 哈希表总结

本文讲解了一些比较基础、偏理论的哈希表知识。包含哈希表的定义,哈希函数、哈希冲突以及哈希冲突的解决方法。

  • 哈希表(Hash Table):通过键 key 和一个映射函数 Hash(key) 计算出对应的值 value,把关键码值映射到表中一个位置来访问记录,以加快查找的速度。

  • 哈希函数(Hash Function):将哈希表中元素的关键键值映射为元素存储位置的函数。

  • 哈希冲突(Hash Collision):不同的关键字通过同一个哈希函数可能得到同一哈希地址。

哈希表的两个核心问题是:「哈希函数的构建」「哈希冲突的解决方法」

  • 常用的哈希函数方法有:直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。

  • 常用的哈希冲突的解决方法有两种:开放地址法和链地址法。文章来源地址https://www.toymoban.com/news/detail-648024.html

到了这里,关于算法数据结构基础——哈希表(Hash Table)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构(五):哈希表及面试常考的算法

    哈希表,也叫散列表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。例如,下列键(key)为人名,value为性别。 数组 map(映射) 映射 底层实现 是否有序 数值是否可以重复 能否更改数

    2024年02月05日
    浏览(42)
  • 数据结构 in Golang:Hash Tables(哈希表)

    水果店的价格表: 苹果 Apple:3元 香蕉 Banana:4元 桃子 Peach:2元 梨 Pear:3元 找到一种水果的价格: 可以使用 binary search,通过名称来查找,耗时:O(logn) 如何只耗时 O(1) 来找到价格呢? Hash 函数:通过一个字符串 - 一个数值 例如: \\\"Apple\\\" - 1 \\\"Banana\\\" - 2 \\\"Peach\\\" - 7 \\\"Pear\\\" - 8 将字符

    2024年02月08日
    浏览(41)
  • AcWing 算法基础课二 数据结构 链表 栈 队列 并查集 哈希表

    链表题目:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 AcWing. 826.单链表 双链表 AcWing 827.双链表 AcWing 828.模拟栈 AcWing 3302.表达式求值 AcWing 829. 模拟队列 AcWing 830.单调栈 AcWing 154.滑动窗口 AcWing 831. KMP字符串 AcWing 835. Trie字符串统计 AcWing 143. 最大异或对 AcWing 836.合并集合

    2024年02月15日
    浏览(44)
  • 【地铁上的面试题】--基础部分--数据结构与算法--动态规划和贪心算法

    一、动态规划的基本概念和思想 1.1 动态规划的定义和特点 动态规划是一种解决多阶段决策问题的算法思想,它通过将问题划分为若干个子问题,并保存子问题的解来求解原问题的方法。动态规划的特点包括以下几个方面: 最优子结构性质:动态规划问题具有最优子结构,即

    2024年02月12日
    浏览(52)
  • 【数据结构】盘点那些经典的 [哈希面试题]【哈希切割】【位图应用】【布隆过滤器】(10)

    前言 大家好吖,欢迎来到 YY 滴 数据结构 系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁 主要内容含: 欢迎订阅 YY 滴C++专栏!更多干货持续更新!以下是传送门! YY的《C++》专栏 YY的《C++11》专栏 YY的《Linux》专栏 YY的《数据结构》专栏 YY的《C语言基础》专栏 YY的《

    2024年02月04日
    浏览(48)
  • 【数据结构与算法】前缀和+哈希表算法

    关于前缀和和哈希这两个概念大家都不陌生,在之前的文章中也有过介绍:前缀和与差分算法详解 而哈希表最经典的一题莫过于 两数之和 题目链接 题目描述: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它

    2024年02月01日
    浏览(108)
  • 数据结构,查找算法(二分,分块,哈希)

    一、查找算法         1、二分查找:(前提条件: 必须有序的序列) 2、分块查找:(块间有序,块内无序)     索引表  +  源数据表     思路:     (1)先在索引表中确定在哪一块中     (2)再遍历这一块进行查找 //索引表 typedef  struct  {     int max; //块中最大值

    2024年02月11日
    浏览(50)
  • 【数据结构】哈希表(算法比赛向)

    目录 一:介绍 一:什么是哈希表 二、哈希表的应用 二:存储结构 a.拉链法: b.开放寻址法: 三:扩展 a.字符串哈希: 例题:      一:什么是哈希表 1、哈希表也叫散列表,哈希表是一种数据结构,它提供了快速的插入操作和查找操作,无论哈希表总中有多少条数据,插

    2023年04月25日
    浏览(43)
  • 【数据结构与算法】哈希—— 位图 | 布隆过滤器 | 哈希切割

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 哈希是一种映射思想,这里再讲解两种应用哈希思想的数据结构。 问题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数

    2024年02月02日
    浏览(51)
  • 数据结构算法设计——哈希表(散列表)

            哈希表 又叫 散列表 ,他们两个是同一个东西,本文全文采用“散列表”的叫法。散列表的本质其实就是一个 数组 ,他的作用就像使用数组时一样,输入下标可以得到对应元素,散列表可以实现 输入一个的时候得到这个的地址信息 。 下面是百科给出

    2024年02月03日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包