00:00
我说一下,嗯。好,我们接着。为啥不上午,上午你们休息一会,老师也休息一会啊,下午你们是两点到五点对吧?啊,两点到五点我大概会占用会两个小时左右,好吧,好,我们接着往下讲,不多说了。好,下面呢,我们来看一个哈希。这个哈希也叫散列。哈希又叫散列,那么我们来看一下这个一个需求,先看一个实际需求来引出这个哈希表。好,这在以前有个谷歌啊,谷歌公司呢,他出了一个上级提他这个提示这样要求的,他说有一个公司当有新的员工来报道的时候,要求将员工信息加入。员工有哪些信息呢?有ID,有姓名,有年龄和住址。当输入。员工ID的时候,要求查找到该员工的所有信息。
01:03
要求不允许使用数据库。尽量节省内存,速度越快越好,这时呢,我们就会用到哈希表。那么哈希表如果再结合我们二叉树的这个搜索数,这个效率是非常高的,那首先我们来把这个哈希它的一个原理示意图,我先给同学们看一下。同学们看这这张图。哈希表呢?也叫散列表。也叫闪列表,它根据关键码值的这个K而进行一个,它是根据关键码值而进行访问的一种数据结构。这种结构呢?也就是说,它通过把关键码值映射到表中的一个位置来进行访问,加快查找的速度。这个映射函数叫闪离函数,存放记录的数组叫做闪离了。
02:00
那当然我念完这个呢,大家可能不是特别的理解我们。把这个图我用我用图解的方式再给大家画一下,待会呢,我也按这个来实现。那么我们来看看这个哈希表到底是什么意思啊,我们先看不用哈希表,或者说不用这个东西,我们一般是怎么做的,同学们看。比如说你这里有段程序。这里有一段程序,不管是用Java写的还是加va写的,我不管,那么在以前传统的,在以前传统的这个方式下面呢,一般是这样操作的。就是我们的,我们这个程序呢,就直接奔数据库去了。一般来讲是这么干的啊,然后这个数据库呢,会返回一个结果给到我们的程序,你拿到程序过后,你要么去进行数据处理,要么是进行数据显示,一般是这种结构,这种结构呢,在。
03:01
在那个以前,那个时代是没有任何问题的,为什么?因因为以前的数据量都很小,软件的规模也很小。所以说这种结构。当时是比较流行的,基本上往数据库里面操作一些,因为数据库也比较好解决啊,增删改查数据库都很方便,大不了就用多表嘛。但是随着这个程序和规模的变大,很多服务器,包括你们大数据处理呢,这种结构对数据库的压力又变得很大,于是就出现了一个叫缓存的东西,那么缓存呢,有很多现成的软现成的东西,比如说同学们看。我们把这个给大家画下。就是。就是你们在前面应该学过一个缓存产品叫red。好,同学们可以看到啊,它是怎么来,诶,这个我粘错了。诶,这个地方是怎么。
04:00
怎么变这个样子了,好,我我把这个在我就直接在这画啊。注意,那么因为这种结构速度太慢。大家知道为什么速度慢,因为我们数据库本质是文件。大家都学过,数据库的本质是文件,而且数据库慢的原因是因为你要建连接,建连接时间会很多很很长,所以说后面就就出现一些缓存产品,比如说大名鼎鼎的这些产品,我把它标下。比如说你们在前面学过的reading。RA或者是catch。你们还没有学是吗?啊,学了red是不是,它其实是一个可以做它的很多数据是在内存里面可以跑,对吧,它有很多数据结构,现在你们再去看那些结构就看的很清晰了,它是。定时把这个数据跟他进行一个同步,是这样子的吧,同学们。
05:00
就是它有一个机制嘛。他会有一个机制。就是他定时呢,把这个数据就是你操作数据,它在在这里面,这个其实就是内存产品。它是内存的,但是内存产品有一个问题,就是它如果一旦断电。整个这个数据就崩了,就没有了,所以说为了达到内存提高速度,而数据库保存数据呢,往往是red配合MYSQL来使用。也就是说在我们目前呢,还没有哪一个公司说我彻底的放弃了这种关系数据库MYSQL,他一般是red或者和一个其他产品进行进行一个绑定,当然red呢,也有可能把这个数据直接放到文件里面去。好好,它是这么一个结构。但是这种结构,这种结构当然很好,我们能不能自已写这样一个东西呢?也可以,那也就是说如果我们学完哈希表,我们可以做这样一个特别牛的数据结构,它会变成这个德行。
06:05
什么进结构呢?大家看啊,那么我们可以这样来玩。就是在有些情况下,我们没有必要用red或者memory这种数据产品史,我们直接在这自己建一个什么呢?哈希表。内存哈希表。啊OK,推荐一个类这个哈希表,哈希表哈希表啊哈希表。这个哈希表,我们可以把我们经常用的数据直接。缓存到这个哈希表里面去,那相当于说你自己做了一个内存级别的一个缓存数据结构。那这个哈希表可以做什么事情呢?我们先来看哈希表,有两种比较流行的结构,一种就是传统的。传统的这个哈希。
07:01
哈希加多条链表。多条列表。啊,当然这个链表呢,呃,这种结构也是比较OK的,就是因为你哈希到时候我可以建多链调链表,我通过哈希一一哈希,我可以把这个速度成倍的增长。第二种呢,就是我们的哈希加我们的二叉树。啊,这种结构就比较猛了。那你因为大家知道链表呢,通过哈希过后,我可以把它分分配到不同链表,这个速度本身就会提升,但是链表它的增删改查的速度比较慢,对不对。那么如果我们这个哈希每条数据数据的数据结构呢,跟二叉树关联,那这个结构就相当不错了,因为二叉树里面有一种二叉树,我后面要就是要给大家讲的叫做搜索二叉树,叫二叉搜索树。啊,二叉排序术啊排序呃叫嗯,这个排序术我叫搜索术都可以收,叫排序吧,排序术这个术这种结构呢,它特别适合我们的生产改查,那这样子这个内存产品就非常的棒了,我们现在呢,先把这个讲完,因为你现在还没学二叉树说这个二叉术讲完了过后,你们也就自然知道怎么去做了。
08:18
那么现在我们就来看传统的这个,呃,哈希这个这个链表,它是在内存里面怎么跑的,来同学们看。OK,呃,当然这个地方你可以写个定时的啊,定时刷新的一个任务。定时更新的。一段代码,那么我们来分析一下这个哈希长什么样子呢?我们就结合刚才我们要出的这个题来分析一把。这个。我们待会儿要写的这个哈希表长什么样子?好,我先截一段视频。
我来说两句