00:00
下面我们接着来完成这个哈希table,那首先呢,我们把刚才写的这个添加和便利给大家测一下,看看OK不OK,好吧,那首先呢,我们先第一步创建一个哈希哈希表。那这个很简单,我们六一个has table就是我们自己写的,然后呢,我们假定有七条链表。好的,然后这边呢,我们去接收一下,比如哈希。Table。Tab,那么我们就叫哈希table就可以了,对吧,这是我们创建的电表,那创建链表过呢,我们这里写一个简单的菜单。啊,写一个简单菜单来测试,因为你要没有菜单,你看起来很不舒服,所以说我先写一个K,这是待会呢我要接收的,呃,用户的输入,然后呢,我们再创建一个scanner。对不对。呃,就是我们的扫描器。好,然后这边呢,我们输入它的一个标准,标准输入system.in。
01:06
好设点设置里面点映呢,我们分配一个变量叫scanner。然后拿到这个以后呢,我们怎么做呢?呃,我们现在就让他输一个内容进去。好。呃,这个地方菜单显然是一个怎么样while循环,是不是只要他退出嘛,所以说我写一个true。这个这个scan我们提到外边去。是这样子的吗?好,先把这菜单打出来。这个时候呢,我们把这个菜单打出来就可以了。怎么做呢?同学们看这里。先把这个删掉,我们这样写。写个菜单,System。好,如果说用户输一个ID,我们表示添加雇员。没问题吧?添加固源,如果他输的是一个list,我们就叫做显示雇员。
02:03
把这个挪一下,那如果说他输的是一个退出指引exit。好,如果用户输的是exciting,那么我们就知道他是要退出系统。对不对,他要退出系统,这个呢很简单,写完写完以后我们就来用K接收一把。Scanner。点什么呢?Read。Read read,一个next。好的,Read,诶这个地方按next直接是next啊,这比解说了,然后我们用Switch来进行一个判断。对不对?Switch,那如果说呃,我们发现他输的是爱的,我们应该怎么办呢,同学们?是不是我们就让他输入ID和用户的名字对吧,我就简写一下,输入ID提示他一下就可以了,ID呢,我接收一把ID等于SC。
03:03
怎么样点next int拿到了,拿到这个过后我们继续让他输什么呀,输入名字。输入这个雇员的名字,输入名字呢?我们仍然用name接收一下scan。这个时候呢,点next。拿到是不是,呃,拿到以后我们现在就可以创建一个雇员。是不是创建雇员?好,这方写错了。史俊。创建一个柜员,那创建一个柜员,我们就六一个呗,六一个employee怎么样,ID就是刚才得到的名字是这个,诶这个地方怎么样调出来了,然后我们让他分配一个变量。就employee就可以了。那拿到一个employee过后,我们是不是就调用我们哈希table.add把这个放进去就完事了是吧?这个就是我们的I操作写完了,那如果说用户他输的是一个list。是不是我们就这个简单就直接干什么呢?调用我们哈希table的这个历史的方法就完事了,不要忘了啊,有个break。
04:11
不要忘了一个break。好,同学们,现在。现在我们来看一下啊,这个地方他说没,他说没有,没有关掉,我们加一句话吧。如果他出的是退出指令,我们这样处理啊,如果他加的是一个。这样的一个指令,比如说。呃,Next,我们干什么呢?我们就把这个scan。看到点close一下,然后用system。点exit退出就可以了,这样他就不会再报警告了,对吧?退出指令就这么简单,那现在我们来玩一把,看看能否呃完成这样一个功能呢?我刚才讲过,其实这里面我留了一个坑。大家有没有发现我在这儿构建的时候,我说这边会有个坑,看看这个坑会发生一个什么样的异常啊,来运行一下。
05:03
那运行过程它会检测。我们先添加雇员吧,艾。他说输入ID,比如说我输入第一个ID为一名字,比如叫汤姆回车。可以,同学们可以看到已然报了一个空子帧,这个空子针在哪里呢?各位同学看,在第54行这发生的,也就是说当我们去调用这个链表的爱的方法时,它抛抛出空指针的,为什么呢?同学们知道为什么吗?其实是因为你现在这个就,也就是老师高量的这一部分,它是一个no,为什么是no呢?大家看你在创建这一个。链表的时候,你仅仅是把这个数组本身创建起来,也就是说你这个蓝色的部分。的的确确创建起来了,但是里面的这个employee,它整个这个是什么呀?空,你怎么可能把一个空直接直接把一个employee放在一个空的这个上面去呢,所以他就报错了。
06:02
那应该怎么播,应该怎么办呢?好,同学们,这时。不要忘了啊,我提醒大家就是不要忘了,因为很多同学写这个哈希表的时候老在这犯错,所以说我专门给家给大家点出来,这时不要忘了,分别初始化。出。史化什么呢?我们的美这个。每一条链表,每个链表。这个其实很简单,用个for循环就可以了,I我们是零,I小于什么呢?SI加加是这样子的吧,那就是说我们这个数组里面的每一个元素,你都需要去创建一把。就这意思。就这句话千万别忘了,好,现在我们再来测试一下,就不会再报控制针异常了。来玩一把爱招一输入名字,汤姆没报错了吧?
07:00
别标错了,那么我们现在历一下,当我们list的时候呢,你们有没有发现他爆出。报出当前链表为空,当前列表信息为,你看这是一条链表信息,这是第二条链表信息,这是第三条、第四条、第五条、第六条、第七条,对的,但是我们这打印出当前链表为空,很不舒服,我希望能够把链表的这个编号打出来。怎么做呢?非常简单,大家看啊,因为这样信息看起来太难受了嘛,是不是,所以说我们希望把链表的编号打出来,那大家想我们在历史的时候。我们在历史的时候,大家看。历在这地方,我们去调用每一条链表的时候,是不是我们顺带可以把这个I传进去啊,传给到我们这条链表,然后呢,把这个I打出来不就完了吗。是这样子,所以说我们需要改写。这个employ link list的这个历史的方法。那我这写一个啊,我们就写一个叫做employee,就就叫编号吧,就是这这个编号,如果有了这个编号的话呢,我就写D。
08:10
这条链表D。D啊,把它写进去啊D。Number填链条,那如果是零就是零,这个无所谓啊,第零条列表我们知道第零条就是第一条就可以了,那么这个地方呢,同学们看这个地方也不需要换行了,因为你换行下面接着呃就就会换行,看起来很很很难受是吧?呃,那这边我们也把它改成第多少条链表。对不对?D多少条电表呢?加上我们这个no。是这样子吧,就是第这么条链表信息为这个,这样看起来就会舒服很多,我们再来看一下。好,我们运行一把,同学们看。我们运行吧,同学们看一下,诶,这有错误,哪里有错看一看啊。哦,这忘了传,把这个I传进去了。
09:01
是吧,来玩一把。好,首先呢,我们爱的。第一个汤姆他历史的看情况啊,说第一条列表为空,第呃第零条列表就是我们说第一条第一条链表就第二条啊链表为空,那当然你这个看起来不舒服,你可以改一下吧,我们把这个no。加一不就完了吗?对吧,那看起来确实很不舒服,所以说我把这个稍微调一调。对不对,这边呢,我们也把这个编号给它加一下就可以了,是不是这样的道理啊,好,这边我们打一个空格,那好看。好朋友们,我们再来预习一下,这个效果就非常的清晰了,来艾特。第一个人汤姆list看啊呃,第一条列表为空,第二条链表ID等于一是个汤姆,第三条没有,第四条没有,第五条第七条没有,那么接着再加。爱的,我们再来加一个,同学们看啊,比如说我们加二号,加二号,加二号呢是Jackie Jackie,我们list一下Jackie,你看它会坐落在。
10:06
第三条链表为什么呢?因为编号为二,二模上这一个七等于二,那么第三条链表它的下标其实对应二,所以说这个没问题,好,这次我们再来加一个,呃,会重复放在的一个链表上,比如说我们加的是八号链表,八号链表的话,八模七等于一,它会继续落在第二条链表,对不对?因为八模上七等于一一。它对应它的下标为一,其实它是第二条链表,这个大家能绕过来吧,好,我加一个,比如说现在我加一个八号,这个人叫史密斯。回车,好,各位同学,看历史的同学们有没有发现在第二条链表上?放入了我们的八号史密斯这个人。没问题吧?好,那现在我退出一把。好,代码正确退出,那现在呢,我们添写了这一个,添加写了这个,呃,便利是不是我们还要写一个查找,这是最基本的,那现在呢,我把查找方法给各位同学编写一下,比如说我们现在需要把。
11:16
查找这个方法给大家写出来,现在我们干什么呢?根据IDID查找,查找什么呢?雇员来吧,现在我们来体验一下啊,Public干什么呢?你查找到了,我们返回一个in的这个雇员,Find employee by。BY什么呢?ID?办ID好,诶D,那你给我一个ID吧,你给我一个ID,我就给你返回来一个employee,那我这先做一个说明。我这先做一个说明,呃,如果查找到,查找到就返回employee。是不是,那如果没有找到呢?没关系,如果没有找到就返回什么呢?空就可以了,明白这个意思吧,好,现在呢,我们来做这个工作,先判断当前是不是为空。
12:10
啊,判断判断链表是否为空。对不对?是否为空?那就这样写,如果head它等于空,说明什么?说明你这个链表是空的,肯定是找不到的是吧?就写个链表空。链表空。也没有空,没有办法查到,那就直接一个空就可以了。好,那么如果它不为空怎么办呢?不为空是不是我们仍然要用一个辅助指针来帮助我们查找啊?那还是老规矩。我们建一个当前的雇员。让他指向害。那么现在呢?我们用一个Y循环反复的找。处。假定我们ID是不重复的啊,假定ID不重复,那么我们找到一个就返回,我们先比较一下。
13:02
如果你这个current,如果你个current的。ID就等于这个ID说明什么?说明什么找到?是不是说明找到了,那如果找到的话呢,实际上这个c employee就只限你要查找的公园,就break。我跟你说一下啊,这时这时u CR employee就指向要查找的这个雇员。是样子吧。同学们过远。那么有一种情况下,呃,他们他还不他不等于这个ID怎么办呢?我们让它往下移一下。是不是我们可以让它往下移一下。那往下这个后移后移。后移,后移呢?继续判断下一个ID,等不等于,那问题来了,你什么时候退出呢?
14:00
退出条件是不是要写出来呀,不然的话是个死循环,什么时候退出,同学们,如果我们这一个current。它的next,它等于空了,说明什么?说明你遍历完这一个这条链表,但是没有找到,是不是就是说说明。说明便利便利,当前列表没有找到该雇员。是这样子的吗?没有找到该公园,肯定的,那这个时候怎么办呢?怎么办呢?各位同学,我们这边聪明一点,因为你待会这个上面这个情况是current指向要找相等,那你如果这个情况那current employee呢,把它制成一个空就完事了。因为空就代表没找到嘛,但是你不治的话,这个current employee其实是指向最后一个的,只是这个最后一个呢,并不满足条件而已,这样子吧,所以说我上来过后呢,不用犹豫,不用彷徨,直接将其吃空。
15:01
就完事了,那最后当while循环结束以后,你也不要做其他判断,直接把current employee返回就完事了。好,这就是查找,那查找过后我们讲过查找雇务员的代码,你是写在这个链表里面的,但真正调用是在人家哈希table里面调,是这样子的吧,所以说我们这个地方呢,仍然要在哈希table里面再写一段代码,哪里各位同学请看哈希table,我们增加一个方法。好,根据输入的。二输入输入的ID查找什么呢?查找这一个雇员,那这个就比较简单了,老师就直接写了public voed,我们就把信息写到这,Find employee by ID能理解意思吧?好,那你肯定要给我一个ID号,ID号好我在这找,那首先呢,我仍然使用使用什么散列。
16:02
散列函数确定。确定到哪条链表,哪条链表查找是不是好,那跟前面一样了。跟前面一样,那我把这个写过来。那当然这个地方就直接填ID了,是不是,那直接填ID以后呢,我们调用的就是哪个呢?我们就接收一下了,Employee等于什么呢?就是我们当前的。这个。链表数组里面的employee link的这个,然后点什么呢?放把ID把ID传进去就行了。是这样子的吧,那现在有一种可能性是找到了,有一种可能性是。没有找到是吧?所以说我现在写一句话,If,如果这个employee等于不等于空,说明什么?说明找到了,给出信息就行了,找到。是不是找到了吧,找到,那么如果没有找到呢?那就是等于空,这时我们提示一句话,就说没有找到该顾眼。
17:06
在哈希表中,在哈希表中没有找到该雇员,那你没雇员啊,不是官员雇员。是不是,那如果上面找到的话呢,我们就这样提示一句话,怎么写呢,说在哪一条链表呢,在D。DX调。条链表中找到该雇员。雇ID等于多少呢?把它导出来就行了啊,就是确定一下这个事。好,然后呢,我们把它格式化一下。这事就解决了。嗯,那首先呢,这这个I dxq呢,我们也用一个百分号D。ID也打出来啊,那是哪一条呢?其实就是刚才我们算出来的这条列表,但是呢,因为好为了好看呢,我们加一个一能理解我的意思吧,这就跟刚才我们显示那条链表呃结合起来了,那下面这个ID呢,ID当然就是你输的ID。
18:07
代码就写完了。但我就喜欢了。好,这是我们find,那现在呢,我们把这个find写加到这里面去,加到菜单里面去,是不是同学们好,我写个find,那么这个是干什么呢?查找雇员。查找雇,那查找雇源,我们增加这个逻辑,增加这个逻辑,增加到历史的后面吧,Case如果他是范的,我们首先会提示这个哥们,提示一句什么话呢?说诶请输入请。请输入要查找的ID,那我就接收一把ID等于什么呢?scan.next。是这样子的吧,诶这个地方它有重复,因为上面呢已经有个ID了,是重复了是吧?呃,那这个地方如果重复的话,我就直接在这用它上面那个就行了,是这样是吧,那现在呢,我们调用high table。
19:02
点什么呢?Find ID把它传进去完事。是不是好?同学们,我们来玩一把,看看这个查找是否能够正确的工作。来,那首先呢,我们要加一点用户进去,加一个一。汤姆好,再加一个二,再加一个二,Jack好。我们历史一下,现在呢,第二条,第三条,我们分别。分别就拥有了。呃,两个雇员我们再加一个吧,为了做测试呢,再加一个,再加一个多少号的呢?比如说加了一个123号啊,我随意的。书文名字叫史密斯。对不对,然后呢,我们历史了一下。我发现呢,很幸运,呃,123号是在第五条链表,我们再加一个爱的,这是我们再加一个比较大的6782不知道哦到哪去了啊啊,比如这个人叫做什么呢?叫做米兰。
20:03
回撤。我们看到米兰呢,这个6782是在第七条列表,好大致就可以了,现在我们来find一下,我们来find一下find。好,我查输入,要要有的ID,我就随便写个八号,显示八号是没有的。好,同学们看我在这里呢,抛出了一个异常。好,也是空指针异常。那么为什么会抛出这个异常呢?我们来看一下,首先找到异常是从这个地方发生的,看到没有,你看你在这里,你做了一个工作,你先判断这个ID。拿到了,拿到了,但是你有没有发现在这里你没有退出语句,也就是说当等于这个时候你已经写了。这是退出条件,但是你把这个自控路过,你忘了写了break。是不是我们这有个坑,留在这儿的?
21:00
因为你只把自出,你没退出,不退出它下面继续取啊,因此刚才这个问题就在这出现的,所以你会快速的定位就可以了。好,我们再来写一下爱的一。汤姆list,爱的。二。好,Jack。好爱的,我们123对不对?史密斯好,我们爱的。22345,好吧,叫做米兰,米兰好历史的。同学们现在呢,我们,呃,大致是这样的一个情况啊,一个2345,它掉到第一条去了啊这个无所谓,那现在呢,我们翻了一下。办了一下,我输入一个ID,比如说我输入一个不存在的九,显然这个应该提示找不到。在哈希表中没有找到该雇员。没有找到该雇员,那么没有找到该雇员过后呢?我们看看此时时刻。他是怎么处理的。当我们在这里。
22:02
大家看这里,我们在这写完一个find过后,你有没有发现我们并没有去加入break,如果你没把break它会怎么样?它会直接退出,因此这个break呢,我们丢掉了,就不能再去继续去玩了,明白这意思吧,所以说刚才这个地方呢,我们如果不没有break,就只能玩一次。好,我们再来一次爱的一号对不对?汤姆,好的,爱的二号什么呢?Jack,好,爱的,我们再来一个。123号好,史密斯。好类一下,当然爱的一个。三这个人啊,不知道是多少了。叫米兰。回车,好,我们历一下。那同学们可以看到现在信息是这样子,我们再来办一下,这次就可以多次查找,首先我们查找一个八号,八号不存在。你看没找到继续,那这个时候你可以再犯的判断呢,我们这次找找存在,找到一个存在的啊一号。
23:06
一号来走,一号有一车,他说在第二条链表找到雇员ID的,是不是第二条呢?第二的确是第二条,我们再来找一个半,这次呢,我们输入一个3456。啊,3456 3456在第几第第几条上,第六条是不是第六,第六条的确是第六条,好,同学们关于这一个链表的添加形式查找就做完了。那么我给同学们留一个课后题,就是关于删除过源,请同学们自己参考老师的写法,把它加进去就完事了。很简单,提示一下思路,你在删除的时候也是先要到哪里去写代码呢?写在这个employ link link list里面去写,找到过把它从列表里面踢掉,踢掉以后呢,在哈希table里面。调用一个呃,写一个delete,根据他的ID确定它是第几条链表就可以了,明白好,那关于。
24:09
哈希列表的最核心的代码我就给大家写完了,我们把讲解的内容进行一个板书。那刚才我们讲的是什么内容呢?捋捋思路,刚才我们讲的是哈希表,也是一种新的数据结构,对不对?好,给各位同学板书一把。睡吧。诶,这个地方不要吸气啊。诶,这怎么回事儿啊?我把这。我把这个稍微的改进一下啊。好,这个地方他老写这个应该是我的正文哈,我的正文哈希表,那哈希表我们先讲的是什么呢?我们先给同学们提出了一个题,引起大家思考,就是什么呢?谷歌的一个商机体。对吧,谷歌上集体,那么谷歌上集体的要求呢,其实说白了就是要求我们用哈希表来完成,相当于说让你让我们自己来写一个哈希表。
25:06
是不是我们自己?完成的这个哈希表的一个结构。并且呢,可以工作把哈希表上级题说完了以后呢,我们给同学们说一下哈希表的基本介绍,也就说哈希表的概念是什么,是这样说的吧,哈希表的概念是什么,那我在这里呢,我们说到哈希表的概念大致是这样一个情况。是吧?OK,当然,那么我们把这个哈希表的一个分析就是,呃,哈希表的价值是有什么作用呢?其实哈希表在一定程度上就是一个缓存层。呃,只是呢,这个缓存层没有像red或者没开功能那么强大,但它的确可以做缓存,也就是说,我们可以把经常使用的数据放在这个缓存层,这样减少对数据库的操作,这就是他的一个由来。包括其他集合的价值也主要是体现在这里。
26:01
好,这是它的,呃,一个111个最,就是为什么有这个哈希表的一个解释,那紧接着呢,我们给大家画了一个哈希表的一个内存的布局图,也就是这个图,大家看一下。是不是这个图啊,这是哈希表的一个内存布局图,我挪到上面去。有了这个内存布局图以后呢,我们就给大家说,我们来写一段代码,也就是这段代码是不是谷歌的商机起要求什么什么什么什么什么对吧,我们把这个呢,就拿过来给大家写个字。好,这是我们的谷歌一个上机提的完成。二骨骼商机体完成。那嗯,怎么做的呢?我们把这个思路先给同学们分析了一把,首先我们这有要求。是不是这是我们的一个具体要求?那有哪些要求呢?第一点,不使用数据库。第二点添加的时候呢,我们认为总是从低到高的插入,那我在给大家出一个题,如果ID不是从低到高的输入的话呢,请同学们。
27:10
把这个功能加进去,也就是说把这个爱着呢,考虑假设他先输了一个五号,接着再输了一个四号也要保证。呃,比如说输了个五号,输了一个四号,然后呢,我们要保证它在每条链表也是一个从低到高的,这样大家把它完成一下啊,好,然后呢,我们这里面用的这个链表,同学们看到我们使用的是一个不带表头的,什么不带表头呢?就是说我这个我这个链表的头直接指向的是一个有效的employee,而不是一个纯粹用来做节点的一个投节点,明白我的意思吧。好,然后呢,我们就画出了这一个示意图,就是把我们这个哈希表。也就是说,我们用哈希表来完成这个题的思路,以图解的方式给同学们画出来了及这张图。是不是同学们,我把这个图呢,给大家伙放在我们的笔记中,降低于大家的复习和理解,有了这张图过后呢,我们就开始完成代码,是不是,所以说我们再去做一件事情的时候呢,一定是先有思路再有代码,代码实现,这个代码实现其实就是在就是在原先这个分析的基础上来实现的,是这样子吧。
28:25
好,各位同学,我把代码呢给各位朋友板书到我们的笔记中,整个代码拷贝一下。操作到。我们这个还行,插入到我们这个笔。
我来说两句