【数据结构】什么是哈希表？为什么哈希表的查询时间复杂度是O(1)? 淩亂°似流年 2023-10-04 18:33 3阅读 0赞 -------------------- `大家好，我是卷心菜，可以叫我菜菜，大二学生一枚。本篇主要讲解一种数据结构：哈希表。如果您看完文章有所收获，可以三连支持博主哦~，嘻嘻。` -------------------- #### 文章目录 #### * 一、前言 * 二、数组 * 三、哈希表 * * 1、百度百科 * 2、问题引用 * 3、哈希函数 * 4、哈希表结构 * 5、举例分析 * 6、哈希冲突 * 7、哈希表的优缺点 ## 一、前言 ## * 实话实说，我算法贼菜，为了提高自己的算法能力，自己也是慢慢开始积累刷题经验，在做题中学习数据结构和算法。为了说明今天所要讲的哈希表这一个数据结构，还是从经典的两数之和开始吧 > 这道题是牛客网的一道算法题：题目链接如下：[两数之和][Link 1] > 可能刚接触编程的小伙伴们还不知道什么是牛客网：他是一个可以学习编程，比如JAVA、C++、C、Python等等编程语言；内推找工作；面经复习知识的神器，非常适合用来日常的学习，：[点击开始注册吧][Link 2] * 题目如下，自己第一次写这道题，也是循环遍历，效率可以说是非常的慢，就像评论区那样所说：“有人相爱，有人夜里看海，有人两数之和做不出来”![在这里插入图片描述][1fa78590723744e7a9ad607ef722a5cf.png] -------------------- ## 二、数组 ## 在正式开始讲解哈希表之前，让我们来简单认识一下数组。我们经常使用 **数组**，它也是一种数据结构，那么数组有什么优点呢？ ![在这里插入图片描述][30abb4ef4b1147e7806f66e710122ef3.png] 简单来说，数组的优点是：我们可以通过数组的下标快速定位到该位置下的数值，获取这个数值是非常非常的快， O(1)级别的时间复杂度。而哈希表的出现，就很好的解决了这个问题。 但是大家有没有想过，如果我们不知道该数值的下标，想要获取这个值，只能通过从头遍历数组，这时候，查询的时间复杂度就是O(N)级别的 -------------------- ## 三、哈希表 ## ### 1、百度百科 ### 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数(哈希函数)，存放记录的数组叫做哈希表。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。 > 读起来有些吃力，我们只需要抓住两点：哈希函数、哈希表，接下来我会介绍它们 -------------------- ### 2、问题引用 ### 前面讲过了，哈希表的出现可以解决数组的缺点，让我们从一个小案例来慢慢理解哈希表~ 假如周末到了，你要去图书馆借一本书《活着》，图书馆的管理员管理书籍很随意，是按照数组的方式来放书的，就像下图一样。而恰巧你要的《活着》是在最后一个位置，管理员从头开始找，你是不是要等好久好久？ ![在这里插入图片描述][4ccb71e1b154448d879154fbbd36c255.png] 最后你等的不耐烦了，就举报这个管理员，图书馆的老板把这个管理员给解雇了，来了一个新的管理员，她很聪明，她通过一种方式把每种书籍都编上一个号，并记录下来。你向她借《活着》，她通过“一种方式”一计算，哦，是在下标为6的位置，就直接走过去，给你拿了过来。你很满意，老板也很满意，给她升职加薪~ ![在这里插入图片描述][ae41893c1c514882ad483af9af45a0f5.png] -------------------- ### 3、哈希函数 ### 上文说的“一种方式”，就是哈希函数，它有三个很重要的性质： * 当给哈希函数传入相同的输入值时，返回值一样 * 当给哈希函数传入不同的输入值时，返回值可能一样，也可能不一样，也就是我们所说的哈希碰撞 * 很多不同的输入值所得到的返回值会均匀的分布在输出域上，这一点很重要 -------------------- ### 4、哈希表结构 ### 前面说了数组和哈希函数，就引出了我们的哈希表结构： ![在这里插入图片描述][42d90b5a65d641e38e031dbdd587298d.png] 我们输入一个值，通过哈希函数计算后 % 上数组的长度，就可以让值放入数组中，所以当我们使用哈希表结构的时候，它的时间复杂度在理想状态下是O(1)，接下来给大家举例分析一下： -------------------- ### 5、举例分析 ### ![在这里插入图片描述][9232ac6ee3dd4ae594595e95d0dccc45.png] 当我们输入`abc`时，由哈希函数计算得到一个哈希值10，10求%后得到1，就把`abc`放到数组下标为1的位置；然后输入`edg`，再次由哈希函数计算得到一个哈希值13,13求%后得到4，就把`edg`放到数组下标为4的位置，后面的操作也是这样。 -------------------- ### 6、哈希冲突 ### 最后再来提一提哈希冲突：当我们输入`future`时，假如通过哈希函数计算得到哈希值是15，我们就发现跟`love`的位置冲突了，解决这个方式有好几种，比如：`拉链法`、`再次哈希法`等等，这个我准备在写HashMap源码的时候，通过讲解HashMap的底层实现原理时，说一说Java的API的哈希表是什么样的时候再说。 -------------------- ### 7、哈希表的优缺点 ### * `优点：`处理元素很快，添加、删除、修改、查找元素性能好 * `缺点：`元素在数组中是无序的，不能重复 最后，讲解了哈希表的数据结构，那么力扣第一题你会了吗？ class Solution { public int[] twoSum(int[] nums, int target) { int[] arr = new int[2]; HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { //如果为true，说明target-num[i-1]的值在数组中存在 arr[0] = map.get(nums[i]); arr[1] = i; return arr; } map.put(target - nums[i], i);//这条语句不能放到if语句的前面！ } return arr; } } -------------------- `感谢阅读，一起进步，嘻嘻~` [Link 1]: https://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f?tpId=196&tqId=37090&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=%25E4%25B8%25A4%25E6%2595%25B0&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=&title=%E4%B8%A4%E6%95%B0 [Link 2]: https://www.nowcoder.com/link/pc_csdncpt_wsykqxc_python [1fa78590723744e7a9ad607ef722a5cf.png]: https://img-blog.csdnimg.cn/1fa78590723744e7a9ad607ef722a5cf.png [30abb4ef4b1147e7806f66e710122ef3.png]: https://img-blog.csdnimg.cn/30abb4ef4b1147e7806f66e710122ef3.png [4ccb71e1b154448d879154fbbd36c255.png]: https://img-blog.csdnimg.cn/4ccb71e1b154448d879154fbbd36c255.png [ae41893c1c514882ad483af9af45a0f5.png]: https://img-blog.csdnimg.cn/ae41893c1c514882ad483af9af45a0f5.png [42d90b5a65d641e38e031dbdd587298d.png]: https://img-blog.csdnimg.cn/42d90b5a65d641e38e031dbdd587298d.png [9232ac6ee3dd4ae594595e95d0dccc45.png]: https://img-blog.csdnimg.cn/9232ac6ee3dd4ae594595e95d0dccc45.png
还没有评论，来说两句吧...