00:00
各位,我们来开始编写这个。哈希表管理雇员的一个小系统,来,我们写一个,首先呢,呃,我们新建一个包包,对,我们新建一个包。这个包呢,我们就取个名叫。对不对,我们专门讲还是table的。好,那在这里呢,我写一个类。我写一个类叫哈希。Table什么呢?DEMO?把主方法勾上。把主方法勾上。呃,那现在我们怎么写呢?根据刚才我们讲的这个规则,我先写个employee。这个表示各位同学,这个表示一个雇员,那刚才我们分析了,雇员呢,根据他的要求会有ID,有姓名,有年龄,有名字,有住址,那为了简化,我们只保留ID和名字好不好,这个没什么大的问题吧,那现现在我们写上public public先把ID做出来,那ID呢,就是就叫D吧,这样子。
01:07
那public它的一个名字对不对?好,那public它必须还有一个指向下一个节点的一个引用,或者是一个地址对不对,那就是employee next。然后呢,我们给他提供一个构造器,好,我们提供一个构造器。好,构造器的这个next默认空就可以了。这个没问题啊,这个是默认为空的,就next默认默认为空没有问题。好的,那这个呢,就是我们。这一个employee的对象我们就创建起来,紧接着呢,我们开始来写哪个呢?同学们,根据刚才的图解,我们现在应该写。Link的list,也就是这个列表。是不是好开始写,那么看干什么呢?呃,创建创建一个EMPLOYEE0可的list,它表示什么?同学们,表示一条链表,表示链表吧,表示链表,这个链表里面呢,会存放我们的数据,好开始写employee link的list。
02:21
没问题吧,那我们说了这个链表里面呢,需要有一个头指针,是不是刚才我们看这个图也看出来,这里面有个head的呀,对不对,需要一个投指针。来写上头指针指向哪里呢?指向第一个固原,那也就是说我们这个链表呢,没有没有投节点了,因为第一个。投资人就指向有效的employee,因此我们可以分析出来,因此因此我们这个链表,这个链表的hide是有效的,是直接。是直接。
03:00
直接指向。直接指向什么呢?第一个雇员的,也就是他没有投,没有我们原先写的那个那个害所谓的一个专门拿来做投节点的,投节点的一个那个节点的啊,这点大家一定要清晰,那就写起来就行了,怎么写呢,Private。Private,那employee employee,然后什么呢?Had。这个默认为空啊,默认是空的。那就是当列表为空的时候呢?就是111个信息都没有,那么employee就是no。好,紧接着。紧接着下一步是不是我们就来写添加员工添加员工。添加雇员到哪里呢?到链表是不是,那这个方法应该怎么写来public。Public void爱你给我一个雇员,我就把它加进去。你给我一个雇员,我就把它加进去,那么这地方我们有一个有有几点说明,同学们现在这个添加呢,我们假定,我们假定添加固原的时候,注意听啊,我们假定添加固原的时候就是什么呢。
04:16
啊,就是加在我们列表的最后好不好,后面我们可以按照呃编号的顺序来处理,以以前我们讲过这个东西假定,我们假设啊假定。假定什么呢?当添加雇员时固源时对不对?呃,ID是自增的,ID是自增长的。自增长的,那如果是自增长的话呢,即即什么呢?ID的分配总是从小到大是不是,那如果说它总是从小到大,我们直接把这个雇员加在这个链表的,就是当前这个链表的最后就可以了,是这意思吧,因为你们到公司里面去呢,这个ID号本身它就是自尊的,因此。
05:02
因此我们将该固原,固原直接直接加入到什么呀,加入到本。本条本链表的最后一个即可。最后一个。呃,最后即可,那你怎么样才能让它最后一个呢?首先这个害的,呃,我们是不能动的,因此呢,我们先要做,如果是添加第一个员工,如果是添加第一个雇员。啊,就是添加这条列表的第一个故意,这条列表的第一个故意,我就判断一下。如果我们的had,如果我们had等于no。说明你是添加第一个,那如果是添加第一个的话呢,Very easy hide,直接指向employee就可以了,Return返回。是吧,那如果不是定下第一个,我们需要定一个辅助,辅助的一个指针来帮助我们找到最后一点,好,如果不是不是第一个。
06:10
不是添加第一个雇员则使用一个辅助的指针,辅助的指针帮助我们帮助定位到最后。是这意思吧。同学们最后。呃,那么你怎么样定位到最后呢?非常的简单,我整一个current current employee等于had。是不是,然后呢,我就Y循环,Y循环错,如果什么呢?如果这个current。employee.next它等于空了,说明什么?说明现在我已经到最后了,是这意思吧,说明到最后了,说明到链表最后,如果到链表最后呢?我就不犹豫,直接break,否则我让这个current employee往下移动一位。
07:02
这个大家看能否理解对吧,就相当于说后移。后羿。对不对,后裔后后裔也就是他往后面移下,直到他到最后。他到最后好的。那么到了最后过后呢,我们退出时,退出时这个这个时候直接直接将这个employee挂在啊,或者加入到最后就行了,挂在什么呢?加到。加到最后即可加入,加入链表,这个很简单,一句话就搞定了,怎么写啊,Current。这样写对不对?我们叫current employee,点它的next就等于什么呢?Employee。是不是好添加我们就写完了,那添加写完过后呢,我们来写一个便利链表,现在注意啊,便利链表的这个雇员信息,那你怎么来便利呢,便利肯定我们。
08:05
用一个辅助指针来做就可以了,那我现在写代码了啊,Public public void什么呢?List。历史的哦,不着急,那你便利链表的话怎么便利?非常简单,我们先判断是否为空,如果这个hide它等于呢?说明什么问题?说明当前这个链表是空的。是不是说明链表为空,如果为空,我们就无需再往下面走了,所以说我直接打电话就行。那么当一种什么话呢?就说念表为空,就是当前。啊,当你这样写啊,当前链表为空。如果为空,下面我就不走,至于那否则他没有空,没有空的话呢,各位同学,下面呢,我们就可以把这个信息打出来,我就这样写啊。写当前链表,当前链表的这个信息为。
09:05
好,那信息为什么呢。那我肯定要用Y循环了,所以说我需要一个辅助指针,我还用employee指向head,这个大家能看懂吧,这个current employee仍然起到一个辅助的作用。辅助值。那辅助之人我就用Y循环嘛,我仍然用Y循环,怎么写呢?如果这一个呃,我这样写啊。呃,因为你你走到这这个hide肯定,呃就说这个这个雇员呢,肯定会有,呃肯定会有至少有一个人,为什么呢?因为你已经判断no是不等于空你才进来的是不是,所以说我们可以把这个信息先打一把。我这样输出好写,怎么写呢?就说呃,把ID打出来吧,咱们为了待会形成一个链表,我用一个箭头好不好,ID等于。用一个格式化的。百分号D。
10:01
I等于这个,那这个我们就百分,呃格式化一下ID等于它,然后呢,名字等于什么呢?百分号S,最后我们做完那个来一个制表符。然后我把我把这个信息取出current。的ID,然后employed什么呀。名字就搞定了,搞定以后是不是我们得判断他是不是最后一个了。是不是得判断最后一个,因此呢,我还要做一个判断,如果,呃,如果current。点next,如果等于空了,说明什么问题?各位同学。如果这个条件满足,说明说明这个current employee已经是最后节点。是不是同学们,那如果已经是最后节点,你就只能退出了,否则你你就会出现空指针异常,那如果不是怎么办呢?各位同学,如果不是也非常简单,我们让current指向下一个,这样形成一个便利。
11:08
这大家看能看懂吧,好,这个就是呃,后移,后移,然后便利。好,那整个这个while循环结束以后,我们整个编列表就打完了,然后呢,我们输出一个换行。完事同学们,那关于添加和便利我们就写完了,那现在呢,我们来测试一下。测试的时候注意听啊,我们是不是还得写我们的这个真正的哈希表啊,因为我们知道哈希表它之所以能够提高效效率,是因为它可以同时管理多条链表。那这样子的话呢。我们就可以根据散列函数决定这个ID,就是你这个固源应该加到哪一条列表里面去。原先只能加到一条链表,现在我把它散在七条链表,甚至八条链表。
12:00
那我性能是不是就提升了七倍或者八倍呢?肯定是这样子的。好,同学们,那现在我们才开始真正的写我们的哈希表。各位同学,现在呢,我们开始写哈希表了,先把这个哈希表写出来,我们才能进行它的一个使用,是这意思吧,好同学们,现在我们开始创建或者是呃,创建哈希表。创建哈希table,它用来管理什么呢?管理多条链表。是不是这样子的。好的,那现在开始,格拉。哈西。哈西table,各位同学是不是table怎么整呢?首先根据刚才的分析,我们会有一个数组,是不是多条里面数组,那现在呢,我们先把这个放进去吧,小employee。Employee linked list。Link的历史,现在我们把它创建起来。
13:01
把它创建起来,那因为。这个地方写啊,这个地方我们可以做成私有的。是有的,没问题,是有的。那这个地方呢,我们就直接取这样一个link link的link的,呃,List,这大家知道什么意思吧。也就是说我们这这个呢,是一个呃数组,这个数组里面放的是什么呀?放的是链表,放的是这个link list。那首先有了这个东西,是不是我们首先应该有一个构造器。是不是有个构造器?构造器构造器,那构造器我们怎么写呢?那同学们看public。好,Public哈希。Table。那这里面你要给我指定你到底有多少条链表,所以说我写一个size。Size,于是我就可以初始化,我们的这样写啊,初始化,初始化什么呢?我们的这一个,诶这写错了,叫初始化。
14:14
呃,初始化什么呢?初始化我们这一条列表。这个也很简单,咱们这样做就可以了,非常简单啊,大家看employee。对不对,它等于六,六什么呀?六这个数组大小是多少呢?大小是。Size。是不是就有了?呃,这点大家注意啊,我这里请同学们思考,我这样写,我这样写完,我我我写这样一句话,是不是代表就写完了。就说我现在这样写,能不能用这个所谓的链表数组了,能不能用。这地方我给他留一个啊,留一个坑,待会儿呢,我们来解决这个坑啊可可。
15:00
坑。啊,留一个坑,那有些同学在不小心的时候,他往往我说老师我用了一个这个链表数字就可以用了,其实这边会有问题,待会我们看问题在哪里啊,我故意留了一个坑。好,呃,现在构造器假如我们写完了,现在呢,我们来写这个添加添加固原,因为因为我们讲过。我们刚才讲过这个事情,就是说你真正的添加的行为,我们总是找哈希table,不会找link可的,呃,不会找我们的employee link list,为什么呢?因为你对对外层来看,我们只看到是这个蓝色的框框,至于你里面应该找哪条链表去加,是哈希table来完成的。只要他是把它包起来的,理解吗?OK,没问题吧,那现在我们开始写这个妈妈啦,Public。Void ad,你在添加的时候呢,你得给我一个雇员。这个没有问题吧,你给我一个雇员,那你给我一个雇员的话呢,我干什么呢?首先我要我要得到我要呃,根据根据员工的ID。
16:06
注意啊,根据。员工,诶,对小啊。员工的ID得到。得到A注意听得到,得到该员工,该员工。该员工应该应应当加入到,诶就添加啊,添加到哪条链表。是这样子的吧,因为你现在说白了,你现在链表有几条,有七条,那你下边应该是这样子的,你第一个就说,如果我们看。第一个它的下标应该是零。没问题吧,他第一个下标是零,是我们这个。这个链表数组里面的下标为零,这个应该是下标为一。问题吧,下面这个应该是下标为二。
17:03
好,下边这个下标为二,再下面这个下标为三。好,这个地方有点不好选哈,这个下标为三。好,放在这儿,下边为三,那以此类推,我就不画那么多了,下边为为四,为五,为六。对不对,那你那你来了一个ID,我到底是加到这条链表还是这条链表,还是这条链表,我是不是应该先要根据你的ID来进行哈希啊,也就闪开闪裂,这就不不是就达到我们效果了吗。好的,那我现在呢,要写一个散列函数。我们写一个什么呢?编写,编写一个,编写一个散列函数。那么同学们,散列函数有很多写法。其中有一个方法比较简单,就是取魔法。我们现在使用使用一个简单的简单的取魔法来处理,这个没问题吧,同学们,那现在开始写了啊public,呃,我返回一个int,那么我就写叫哈希。
18:07
那你给我一个int,你给我一个int,我返回它应该加到哪个列表里面去,怎么写呢?ID模上我们这个size。对不对,但size没有,Size没有的话呢,其实我们可以这样玩一把,怎么玩呢?我们再加一个刚才的信息叫size,这个size在这有了功能,我们上来过后这样子,呃,把它传进去,Z是size等于size。因为后面我在这用的时候会用到这这个size,这个size代表什么啊,表示共有。有。有多少?多少条?多少诶,多少条链表能理解我的意思吧,当然这里面除了这个取魔法,还有很多其他的方法,后面我们再给他说,哦,还给他说写完了过后,现在有了哈希放,那下面我们就比较easy了,怎么样呢?我写一个int,就说现在我们返回employee link的历史的RV就是这条链表的。
19:13
Number。就是我要知道你是放到哪一条链表去,怎么写呢?就用刚才我们写的哈希放。把ID传进去就可以了。是不是同学们有了这个东西,下一步我不用说,大家知道干什么呢,调用就是呃呃,就是干什么呢?加入到,将什么呢?将employee加到。加A就行啊,叫添,添加到添加到对应的链表中,怎么写呢?Very easy就这样写就可以了,怎么写就是我们的employee。Linkr走哪一个呀,Employee。点什么爱的,把employee方去就可以了。
20:00
是不是这样一个流程,但你呃,加进去这个事就完成了,这是添加。好,添加完了过后,是不是你这个哈希哈希table还应该给我一个list的方法呀,因为我们也讲了所有的操作,刚才看这里,不管你是添加还是便利,总是要找他的,因为你放,因为你这个哈希table里面管理的有七条链表。只有他才有有这个能力,或者有这个权限去把七条链表进行遍历,然后把条链表信息都输出来,是是这个意思吧,好同学们,那现在呢,我们把这个遍历遍历所有的链表。那方法也写出来,那这个方法其实特别的简单,Public VO list。VO list,好的,那相当于说便利所有链表就是便利哈希哈希表了,便利便利我们的哈希表。哈希表对不对?我再说一遍啊,什么叫哈希表?就是我们的这个数组加上我们的链表共同构成的哈希表,明白了这是一种数据结构,这是一种数据结构,好的,理解了这个东西过后呢,我再说理解这个哈希表,后面我们再去求理解数啊,或者理解这个B加数,就非常的轻松。
21:19
轻松,好,那现在开始写了,那现在一共有几条链表呢?各位同学好,我们for循环int I等于。0I小于size。是不是假设有七条,那个便便利七条I加加没毛病吧,I加加,那现在我们就link的瑞接上I点类似的I。就可以了。好,同学们,那关于我们这一个,就是我们所说的哈希table的一个最基本的添加和便利的代码,我们就写完了。我们就写完了,那待会儿呢,我们再继续为同学们编写它的查找测试这样的一些代码。
22:06
OK,好,那关于这这个哈希表的第一部分就是创建和便利,我们就先写到这儿,一会儿呢,我们写下一个功能。
我来说两句