00:00
啊,好,我们来看看这个哈希表长什么样子,待会儿呢,我要做的事情,我要做的事情就是用一个哈希表来管理我们的员工,但是呢,要充分考虑到效率,就是你不能用单条链表,单链表太慢了,你可以用多条链表来解决。好,各位同学,现在呢,我们来看看这个结构,待会我会怎么写,就说我要画的是这个结构啊,大家要理解我待会儿要画一个什么结构出来。好,首先呢,我会建一个表,建我会建一个,呃,建一个这个数组。这个地方会是一个数组。OK,我把它标成一个颜色。OK,这是到现在这个是一个数组,这是一个什么数组呢。这是一个链表数组。我们知道我们数组有整数数组,有小数数组,有这这那个那个对象数组,我这个数组是什么数组呢?是链表数组,就是它这个每一个元素放的是一条链表。
01:06
好,我们把这个A这个地方稍等一下啊,这个地方我会写个叫link的。这个整个是一个link link的。林可的list。它呢,指向我们的这个链表。OK。那么这个listrra到时间是在哪个地方,这个listr我我我先把这个画完啊里面呢,我们就有很多的这个列表了。好,每个代表一个一一个元素,它是一个数组啊同学们大家看这我写的是链表数组,它是一个链表数组。好,写到这,这是一个链表数组。链表数组,然后呢,它这里面会有很多的元素,没有问题,我把它给同学们试一下。
02:02
假设呢,我们有有这么几个人,有有有有这个五条链表。那么五五条链表里边呢,这个里里面它会有一个投指针,就这个链表里面呢。每每个列表里面,它是什么列表呢?它是一个employee。A linked list。啊,它这里面有一个有有一个头指针。到时我们会写到这个有个投指针,这个投指针呢,它指向。哦哦,这话它指向一条链表出去。好,这边呢,我们就会有很多的学生,待会大家我这个说完了再说啊,比如说这边有个EMPLOYEE1。好,同样呢,我在后面还有很多其他的学生。固原啊,说错了,我们就画四个吧。
03:00
就画四个,那一到时间就会形成这样一个,这个头呢指向了我们的这些学生,当然我这是用的单链表,将来这条链表可以改成二叉树。OK。好。当然你这个地方有链表过后呢,下边我仍然可以有新的链表来看。这又是一条链表。再来。这又是一条链表。好,因为这个画的有点没有对齐,我让他用,这就说这这边的元素都是这个东西啊,都是一个。都是一个头节点。都是一个头。就它里面每个元素是一个链表的,这这么一个类型。这儿也是一个头。好这边也是个头,好这边我就下面我就不画了。那有些同学老师,那怎么怎么个意思呢,就代表这是这个数组里边是我的第第零个元素。
04:05
这个下面这个是我的第二个元素。好,待会我要把这个分析啊,这是下面这个,依此类推。就是我的这个链表数组的第三个元素。好,这是第三个元素,就是二。然后。这边是我们的第四个元素。好,下面这个是我们第五个元素。好,那这样子有什么好处呢?大家看啊。同学们。我们把这个放到这来。这样的好处是我将来在存放这个员工的时候,我会这么存放,大家看一下我的这个这个这个思路。我比如说,比如我们需要添加ID等于12的。这个雇员。
05:00
那我上来呢?先步骤如下,第一步,先哈希一把。先进行这个哈希处理。处理。因为目前我这个链表数组。他有五个。5555个元素,所以说待会呢,我会这样处理12模五。那么我就得到。一个值,这个值是不是应该等于二,那相当于说我就会把这个。ID为12的人往这个列表里,往这条列表里面放。往这条列表里面放。好,当然,如果我这儿有一个11的这么一个雇员,他也模糊。它等于一呢,就等于一,那么这个11的它就会放到这个列表里面去。OK。当然呃,后面这个,你后面这个如果第一次加的时候,他肯定就没有啊,诶我把这个画出来。
06:01
好,我把这个,诶,这个地方有点问题放到这,其他以此类推,那这样的好处是什么呢?当我要查找的时候,我的速度就会比原先快很多。我有什么好处呢?大家看,因为你这个哈希为什么也把它叫做散列的道理大家看出来了,就是它能够根据你的这个标号把它散略到不同的。不同的这个列表里面去,如果我要查找,比如说我要查找有没有一个等于十,等于这个112的这么一个员工。查找这么一个查找,找出这么一个员工,那你看我,如果我原先只有一条链表。那我就傻了。我就只能。只能找信条列表,一个个找。那我现在如果我用这个哈希了。我用这卡西,我上来过后先先确定,就说这个112在在哪哪条列表里面去,我一模是不是就得到一个值,我直接在这条列表里面去找,如果这条列表没有,就说明没有了是吧。
07:03
因为我在家的时候,我就已经把它散开了,我在查的时候自然已经散开了,那大家想一想是不是这种方式,至少它的速度。速度就提高了五倍。是不是就至少提高了五倍?这是大家能够直观看出来的,就提高这个五倍。哎,这个背怎么没出来呢?啊,五倍。那当然有些老师我如果闪离的更大怎么样呢?更多,而且如果将来我们把这个地方,把这条链表换成就说每个吃出来去不是一条单链表了,而是一棵二叉树,这个就更厉害了。直接会怎么做呢?做的好的,他会这样做。他直接,呃,当然这个我我就试一下啊,这个吃出来的就是一条。二叉树。这个有些同学可能已经学过一些这种数据结构,知道二叉树里面有一种数叫做叫做这个搜索二叉树,那个效率很高。
08:09
好,到时候你这吃出来就是这样一个结构了,那就更快。就是。哎,比如说我这指直接指向它,然后这边呢,指向它,这边指向它,这是一棵搜索二叉树,那效率就会更快。就基本上就能哈希,结合我们二叉搜索术,这个效率就大大提升。那这样就相当于说你自己都可以做出一个,根据你的业务需求,你自己可以做一个缓存的一个数据结构来解决一个优化问题。啊,因为你你你说白了,你这个优化不就是为了提升速度吗?你提升速度不就是用这个数据结构来玩的吗?好最后。大家看到。我这个链表数组会放在哪里呢?这个链表数组我会放在一个叫做哈希的这个结构里面去。
09:05
大家看这里,哈希就出来了,我会写一个哈希table。这个哈希table里面有一个元素,就是我们的link list。怎么来了,那么我们这个employee它是什么呢?它就是一个一个的employee的对象。我会写个。一个类class employee里面就是我们的,也就是说,也就是说这个employee它是是一个这样的东西,而我们的这个link list是在一个哈希里面。好呃,然后这个employee历史的这个链表呢,我还要写一份,就是它是它是有三个比较重要的地方啊,到时到时候呢,这还有个东西就是我们的employee。Link的list,这个里面呢,就会含有一个头指针。
10:02
啊,这个投指针呢,我们直接就指向一个真正的employee,不,这个指针就跟我们原先那个带头减点的单列不一样,它是直接。啊,直接指向有效数据。有效数据。啊,直接指向一个数据啊,直接指向。数据。好大题,我们来再回顾一下,待会我要做的事情啊。待会我要见的是一个哈希table。这个table里面呢,会有一个link list,这个link list里面放的就是什么呢?放的是employee list。就是它是个链表数组,而链表数组里面每一条链表数组里面有个投指针,这个投指针就直接指向我们的各个雇员,然后我再进行这个。添加和查找的时候,我们都先进行一个散裂的处理,然后决定应该加到哪去。
11:04
这是我们今天要做的,等到我们把这个二叉搜索数讲完了,可以将这个单向的这个链表改成二叉树,那这个结构就相对来说比较完美了。就说至少这个效率会提升多少倍呢。可以这么说,就说如果你用了这种优化的方案,只要用的合理,你的速度至少成百上千倍的提升,提升没有问题,为什么?因为我们整个都在内存里面,大家都知道内存它的速度比我们磁盘和数据库快很多,因为内存它是电,它存的是0101,它是电的那种是吧,而我们磁盘它是硬件的,它是通过那个磁道,就那个磁针来转。那你想这两个根本不在一个级别上。所以说这样子一个结构呢,几乎就说你只要应用得当,可以解决很多优化问题。而我们的。
12:01
包括这个RA或者M,它的底层呢,也是使用了类似的这种方式。好,同学们,这个我要写的这个哈希迈普呢,呃,思路我已经给大家分析清楚了,我们截取一段。
我来说两句