关于哈希表,你该了解这些!_代码随想录的博客-程序员秘密

技术标签: 算法  代码随想录  数据结构  哈希表  

> 更多干货文章持续更新,微信搜索「代码随想录」第一时间围观,本文[GitHub:https://github.com/TechCPP](https://github.com/youngyangyang04/TechCPP) 已经收录,里面有更多干货等着你,欢迎Star!

哈希表

首先什么是 哈希表,哈希表(英文名字为Hash table,国内也有一些算法书籍翻译为散列表,大家看到这两个名称知道都是指hash table就可以了)。

哈希表是根据关键码的值而直接进行访问的数据结构。

这么这官方的解释可能有点懵,其实直白来讲其实数组就是一张哈希表。

哈希表中关键码就是数组的索引下表,然后通过下表直接访问数组中的元素,如下图所示:

那么哈希表能解决什么问题呢,「一般哈希表都是用来快速判断一个元素是否出现集合里。」

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n),但如果使用哈希表的话, 只需要O(1) 就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里,在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了「hash function ,也就是哈希函数」

哈希函数

哈希函数,把学生的姓名直接映射为哈希表上的索引,然后就可以通过查询索引下表快速知道这位同学是否在这所学校里了。

哈希函数如下图所示,通过hashCode把名字转化为数值,一般hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值,这样就把学生名字映射为哈希表上的索引数字了。

如果hashCode得到的数值大于 哈希表的大小了,也就是大于tableSize了,怎么办呢?

此时为了保证映射出来的索引数值都落在哈希表上,我们会在再次对数值做一个取模的操作,就要我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了,哈希表我们刚刚说过,就是一个数组。

如果学生的数量大于哈希表的大小怎么办,此时就算哈希函数计算的再均匀,也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下表的位置。

接下来「哈希碰撞」登场

哈希碰撞

如图所示,小李和小王都映射到了索引下表 1的位置,「这一现象叫做哈希碰撞」

一般哈希碰撞有两种解决方法, 拉链法和线性探测法。

拉链法

刚刚小李和小王在索引1的位置发生了冲突,发生冲突的元素都被存储在链表中。这样我们就可以通过索引找到小李和小王了

(数据规模是dataSize, 哈希表的大小为tableSize)

其实拉链法就是要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法,一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置,放了小李,那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ,要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示:

其实关于哈希碰撞还有非常多的细节,感兴趣的同学可以再好好研究一下,这里我就不再赘述了。

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。

  • 数组

  • set (集合)

  • map(映射)

这里数组就没啥可说的了,我们来看一下set和map,在C++语言中,实现在C++中,set 和 map 分别提供了以下三种数据结构,其底层实现以及优劣如下表所示:

std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。

std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。

当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。

那么再来看一下map ,在map 是一个key value 的数据结构,map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。

其他语言例如:java里的 HashMap ,TreeMap 都是一样的原理。可以灵活贯通。

虽然set、multiset 的底层实现是红黑树,不是哈希表,但是set、multiset 依然使用哈希函数来做映射,只不过底层的符号表使用了红黑树来存储数据,所以使用这些数据结构来解决映射问题的方法,我们依然称之为哈希法。map也是一样的道理。

这里在说一下,一些C++的经典书籍上 例如STL源码剖析,说到了hash_set hash_map,这个与unordered_set,unordered_map又有什么关系呢?

实际上功能都是一样一样的, 但是unordered_set在C++11的时候被引入标准库了,而hash_set并没有,所以建议还是使用unordered_set比较好,这就好比一个是官方认证的,hash_set,hash_map 是C++11标准之前民间高手自发造的轮子。

总结

总结一下,当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法

但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。

都看到这了,还有sei!sei没读懂单独找我!

预告下篇讲解一波哈希表面试题的解题套路,我们下期见!

> 代码的一切,尽在「代码随想录」。 文章首发在公众号:「代码随想录」,你值得关注!

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/youngyangyang04/article/details/107242663

智能推荐

pycharm中使用清华镜像源方法(详细附图)_一只努力向上的佳佳怪的博客-程序员秘密_pycharm清华源

pycharm中使用阿里镜像源方法很多小伙伴因为导入包的时候因为下载速度过慢而头疼,这是因为pycharm下载包的默认源是国外网站(https://pypi.python.org/simple),这时候我们可以用清华镜像或者其他镜像源1、首先进入设置界面(File-Settings)2、进入安装包的界面,点击右边的+号3、点击Manage Repoditories,这个就是设置仓库4、添加清华镜像源,点击OK5、配置成功...

PyCharm vs Spyder:两个Python IDE的快速比较_cumei1658的博客-程序员秘密

If you have followed my blog you may have noticed that a lot of focus have been put on how to learn programming (particularly in Python). I have also written about Integrated Development Environments ...

961计算机组成原理,2018考研华中科技大学961计算机组成原理(二)考试大纲_祈盟的博客-程序员秘密

华中科技大学研究生考试大纲为广大想报考华中科技大学的考生划出了大致的考试范围以及试卷的结构和题型,是广大考研学生的重要参考文件之一。下面是研招网小编为大家整理的最新2018考研华中科技大学961计算机组成原理(二)考试大纲,以供大家参考。硕士研究生入学考试大纲――《计算机组成原理(二)》科目代码(961)一、考试性质《计算机组成原理》是报考我校协和医院生物医学工程学硕士的专业基础课,旨在考察学生是...

JS本地存储和会话存储的区别_Serena_tz的博客-程序员秘密_本地存储和会话存储的区别

1、localStorage本地存储localStorage生命周期是永久,这意味着除非用户显示在浏览器提供的UI上清除localStorage信息,否则这些信息将永远存在。存放数据大小为一般为5MB,而且它仅在客户端(即浏览器)中保存,不参与和服务器的通信。2、sessionStorage会话存储sessionStorage仅在当前会话下有效,关闭页面或浏览器后被清除。存放数据大小为一般为5MB,而且它仅在客户端(即浏览器)中保存,不参与和服务器的通信。源生接口可以接受,亦可再次封装来对Object

校本课程中计算机工作原理,信息技术校本课程纲要_成都蹦迪阿亮的博客-程序员秘密

《信息技术校本课程纲要》由会员分享,可在线阅读,更多相关《信息技术校本课程纲要(4页珍藏版)》请在人人文库网上搜索。1、信息技术校本课程纲要课程名称:如何构建家庭局域网课程类型:科学素养类教学材料:自编授课课时: 30 课时主讲教师:张刚授课对象:初一、初二学生一、 课程目标:(一)、知识与技能:1、通过本课程的学习, 培养学生在信息技术方面的动手能力, 拓 展学生的知识面,从而提高学生的综合信息...

产品经理看哪吒之魔童降世_weixin_30820077的博客-程序员秘密

前戏哪吒在这个暑假,一下子变成了红人。本来他人是红色的,这个也许是他能红的原因吧,一个小朋友这样说到。其实,对于整天对着电脑和媒体的程序员来说,哪吒的出现概率太高了,博客有介绍的,朋友圈内推荐的,同事饭后八卦的。都红成西红柿了,不想看都难。其实,每年出来那么多电影,能让大家广泛讨论并且有那么大群众基础的作品并不多。无论从什么角度,我都要去看一下。 看看这个新出的作品为什么火的一塌糊度...

随便推点

华中科技大学计算机组成原理慕课第四章 存储系统(一) 单元测验(习题+答案+详细解析)_Code_流苏的博客-程序员秘密_sram中的存储单元

华中科技大学计算机组成原理慕课第四章 存储系统(一) 单元测验(习题+答案+详细解析)

Pycharm IDE安装pandas库失败解决方法_ChiFanLAM的博客-程序员秘密_安装pandas库失败

Pycharm IDE安装pandas库失败解决方法作为一名python新手,我们利用Pychram IDE进行编程时总是会遇到一些配置上的难题。比如,在配置第三方库文件时,我们会遇到漫长的等待安装时间后,却发现安装失败!!!具体的安装失败错误提示为:Error occur when installing " "找遍了各种方法,发现下面的解决方案真的屡试不爽:进入Pycharm的terminal:输入:python -m pip install -upgrade pip或者在P

linux 挂载存储命令,Linux挂载存储及命令_知乎汽车的博客-程序员秘密

常用命令一、网卡部分1、确认IP地址命令ifconfigifconfig -aifconfig ethX2、关闭命令ifdown ethXservice network stop3、开启命令ifup ethXservice network start4、重启命令service network restart/etc/init.d/network restart5、修改IP地址命令vi /etc/s...

华东理工大学计算机组成原理试题,华中科技大学计算机组成原理1999年考研真题考研试题硕士研究生入学考试试题(原华东理工大学)..._Z-JO的博客-程序员秘密

华中理工大学1999硕士入学计算机组成原理真题一.填空(每空1分,共20分)1.计算机中数值数据表示长采用的格式有 和 两种。2.已知十进制数,则相应的二进制数X= ,[X]补= 。3.若X=-0.X1X2……Xn,则[X]原= ,[-X]补= 。4.主机与外部设备之间以软件方式控制信息交换的方式有 ...

python try catch finally_Java try catch finally异常处理(Exception)_金雪锋的博客-程序员秘密

1、Java Exceptions执行Java代码时,可能会发生不同的错误异常:程序员编写的编码错误,由于输入错误引起的错误或其他不可预见的情况。发生错误时,Java通常会停止并生成错误消息。 技术术语是:Java将引发异常(引发错误)。2、Java try catchtry语句允许定义要执行的错误代码块。如果在try块中发生错误,则catch语句允许定义要执行的代码块。try和catch关键字...

java异常处理_weixin_34228387的博客-程序员秘密

可直接看这篇文章即可:http://www.importnew.com/26613.htmljava异常类图非检查异常(unckecked exception):Error 和 RuntimeException 以及他们的子类。javac在编译时,不会提示和发现这样的异常,不要求在程序处理这些异常。所以如果愿意,我们可以编写代码处理(使用try…catch…finally)这样的异常,...

推荐文章

热门文章

相关标签