图解哈希表及其原理

要点回顾

此部分方便知识点快速回顾,首次阅读请从引言部分开始。

  • 哈希表(Hash Table)其实也叫散列表,是一个数据结构。

  • 哈希表本质上就是一个数组,只不过数组存放的是单一的数据,而哈希表中存放的是键值对(key – value pair)。

  • key 通过哈希函数(hash function)得到数组的索引,进而存取索引位置的值。

  • 不同的 key 通过哈希函数可能得到相同的索引值,此时,产生了哈希碰撞。

  • 通过在数组中插入链表或者二叉树,可以解决哈希碰撞问题。

引言

哈希这个词想必大家经常听到,这也说明了它使用的频繁程度,HashMap 和 HashTable 都与哈希这个词有关系。那哈希是什么,要搞清楚它,我们得先来说下哈希表。

什么是哈希表?

哈希表(Hash Table) 是一种用于存储 键值对 的基本数据结构。在 C++ 中,哈希表使用 哈希函数 来计算数组的索引,进而存取数组中对应索引位置的值。

百科定义:

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

计算索引的过程被称为 哈希(hash)

哈希表实现原理

用一个简单的例子来说明哈希表的原理:

假设:有一本中文词典,里面包含了所有的汉字,但是这些汉字是按任意顺序随意排版的,那么想要在其中找到某一个汉字,你就需要从头至尾一个一个核查,如果运气差,这个汉字正好在词典的末尾,那你需要遍历整本词典才能找到你要查的汉字。

优化:因为汉字和拼音之间存在着一种确定的关系,为了提高查找速度,现在将所有汉字按照拼音(key)进行排序(拼音可以根据首字母,第二个字母依次进一步排序),并且每个拼音都有一个对应页码(index),从该页开始,存放拼音对应的汉字(value)。所以找到拼音,也就能在对应的页码找到对应的汉字。其中,拼音和页码之间,有着某种固定的映射关系,可以通过某种方式计算出来(hash function)。

由此可见,哈希表可以根据一个 key 值来直接访问数据,因此查找速度快。

但是,上面的例子,还存在一个问题,放在同一页码(具有相同拼音)的汉字可能不止一个(同音字),这时候通过拼音(key)获取到的汉字(value)应该是哪个呢?这就出现了碰撞(hash collision)

为了解决碰撞,实现哈希表可以有以下两种方式:

  • 数组 + 链表
  • 数组 + 二叉树

所以,哈希表本质上就是一个数组。只不过数组存放的是单一的数据,而哈希表中存放的是键值对。

链表或二叉树是用来解决碰撞的。

下面用图例说明哈希表以及解决哈希碰撞的链表实现:

因为哈希表中 key 必须是唯一的,所以图示给拼音加了后缀 _1 和 _2。key han_1han_2 通过哈希函数 F(x) 计算出来的页码都是 244。这时就产生了哈希碰撞。为了解决碰撞问题,新建了一个链表,链表的每个结点都包含了一个键值对,当输入 key han_2 时,哈希表在 244 位置找到了键值对 [han_1 – 汉],但是通过比对发现找到的键值对的 key 是 han_1,不等于 han_2,所以继续遍历到链表的下一个结点,下一个结点存放了键值对 [han_2 – 汗],通过比较发现 key 确实是 han_2,因此返回了汉字(value)

引用

https://www.educba.com/c-plus-plus-hash-table/

https://mp.weixin.qq.com/s/AkPIN6Ugno9vkQ2AAmCEAA

给TA买糖
共{{data.count}}人
人已赞赏
经验教程

《Asp.Net Core3 + Vue3入坑教程》 - Vue 2.使用Ant Design of Vue编写页面 & vue-router 初试

2021-3-9 14:22:00

经验教程

不用任何框架,Java 就能实现定时任务的 3 种方法!

2021-3-9 14:37:00

⚠️
免责声明:根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。 本站为个人博客非盈利性站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途,网站会员捐赠是您喜欢本站而产生的赞助支持行为,仅为维持服务器的开支与维护,全凭自愿无任何强求。本站部份代码及教程来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
无意侵害您的权益,请发送邮件至 momeis6@qq.com 或点击右侧 私信:momeis 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索