本站消息

站长简介/公众号


站长简介绍:高级工程师,爱好交友,无偿辅导python和前端,技术交流,面试指导,找工作指导,瞎聊都可加我微信i88811i哈,欢迎欢迎!也欢迎加入程序员交流群,专属程序员的圈子,加我微信拉你进群.欢迎关注我的微信公众号:程序员总部,程序员的家,探索程序员的人生之路!分享IT最新技术,关注行业最新动向,让你永不落伍。了解同行们的工资,生活工作中的酸甜苦辣,谋求程序员的最终出路!

  价值13000svip视频教程,java大神匠心打造,零基础java开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-07(9)

2021-08(57)

2021-09(50)

2021-10(32)

2021-11(59)

【数据结构】什么是哈希表?为什么哈希表的查询时间复杂度是O(1)?

发布于2022-05-30 19:32     阅读(1081)     评论(0)     点赞(3)     收藏(1)



大家好,我是卷心菜,可以叫我菜菜,大二学生一枚。本篇主要讲解一种数据结构:哈希表。如果您看完文章有所收获,可以三连支持博主哦~,嘻嘻。


一、前言

  • 实话实说,我算法贼菜,为了提高自己的算法能力,自己也是慢慢开始积累刷题经验,在做题中学习数据结构和算法。为了说明今天所要讲的哈希表这一个数据结构,还是从经典的两数之和开始吧

  • 题目如下,自己第一次写这道题,也是循环遍历,效率可以说是非常的慢,就像评论区那样所说:“有人相爱,有人夜里看海,有人力扣第一题做不出来”在这里插入图片描述


二、数组

在正式开始讲解哈希表之前,让我们来简单认识一下数组。我们经常使用 数组,它也是一种数据结构,那么数组有什么优点呢?
在这里插入图片描述
简单来说,数组的优点是:我们可以通过数组的下标快速定位到该位置下的数值,获取这个数值是非常非常的快, O(1)级别的时间复杂度而哈希表的出现,就很好的解决了这个问题。

但是大家有没有想过,如果我们不知道该数值的下标,想要获取这个值,只能通过从头遍历数组,这时候,查询的时间复杂度就是O(N)级别的


三、哈希表

1、百度百科

哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数(哈希函数),存放记录的数组叫做哈希表。给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

读起来有些吃力,我们只需要抓住两点:哈希函数、哈希表,接下来我会介绍它们


2、问题引用

前面讲过了,哈希表的出现可以解决数组的缺点,让我们从一个小案例来慢慢理解哈希表~

假如周末到了,你要去图书馆借一本书《活着》,图书馆的管理员管理书籍很随意,是按照数组的方式来放书的,就像下图一样。而恰巧你要的《活着》是在最后一个位置,管理员从头开始找,你是不是要等好久好久?
在这里插入图片描述
最后你等的不耐烦了,就举报这个管理员,图书馆的老板把这个管理员给解雇了,来了一个新的管理员,她很聪明,她通过一种方式把每种书籍都编上一个号,并记录下来。你向她借《活着》,她通过"一种方式"一计算,哦,是在下标为6的位置,就直接走过去,给你拿了过来。你很满意,老板也很满意,给她升职加薪~
在这里插入图片描述


3、哈希函数

上文说的"一种方式",就是哈希函数,它有三个很重要的性质:

  • 当给哈希函数传入相同的输入值时,返回值一样
  • 当给哈希函数传入不同的输入值时,返回值可能一样,也可能不一样,也就是我们所说的哈希碰撞
  • 很多不同的输入值所得到的返回值会均匀的分布在输出域上,这一点很重要

4、哈希表结构

前面说了数组和哈希函数,就引出了我们的哈希表结构:
在这里插入图片描述
我们输入一个值,通过哈希函数计算后 % 上数组的长度,就可以让值放入数组中,所以当我们使用哈希表结构的时候,它的时间复杂度在理想状态下是O(1),接下来给大家举例分析一下:


5、举例分析

在这里插入图片描述
当我们输入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;
    }
}

感谢阅读,一起进步,嘻嘻~

站长简介:高级工程师,爱好交友,无偿辅导python和前端,技术交流,面试指导,找工作指导,瞎聊都可加我微信i88811i哈,欢迎欢迎!也欢迎加入程序员交流群,专属程序员的圈子,加我微信拉你进群.
欢迎关注我的公众号:程序员总部,关注公众号回复java,免费领取 全套java视频教程,关注公众号回复java充值+你的账号,免费为您充值1000积分



所属网站分类: 技术文章 > 博客

作者:你不要惹我

链接:http://www.javaheidong.com/blog/article/442951/73c4eca9f1c091a3d909/

来源:java黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

3 0
收藏该文
已收藏

评论内容:(最多支持255个字符)