day24_集合/01-尚硅谷-Java语言高级-每天一考

来看一下咱们出的这几道问题来，这个之前的话呢，咱们讲的都是关于这个集合啊，集合呢，这一章涉及到这个API呢也不少，同时呢，我们除了会用呃，会使用这里边相关API之外呢，还关注一下这个底层的源码，包括这一张呢，在面试当中来问的其实也比较多，就是如果在整个技术阶段说问的稍微深入一点，就是比这个相应的这个笔试面试题的话啊，那么集合一定是其中的，呃，这个非常好的一个选择啊，就是可以探一探你对底层的这个结构的一个熟悉程度，是不是看过源码，包括呢，顺便呢，可以再问一问你的数据结构啊，就是单纯的问数据结构呢，这个事儿其实比较少啊，说让你写一个二叉树啊，什么树啊等等这种情况比较少，但是呢，他可以通过集合的方式去间接的考察大家一下关于底层树结构的一个了解程度，哎，咱们讲完集合以后呢，也带大家呢，带着大家呢稍微的串一下这个数结构的这个内容啊。啊，那我们看一下今天这几道问题，第一个说集合collection当中存储的，如果是自定义类的对象需要呢，自定义类的对象呢，重写哪个方法，为什么哪个呀？对这个大家应该都知道啊，叫重写E口的方法，这个呢得能够写出来啊，没写出来的这个不应该了。

那其实这块呢，咱们只是先泛泛的一说啊，为啥呢，因为collection呢，它没有提供直接的实现类，呃实际上咱们呃主要讲的是list的事现类和set的实现类。啊，那咱们顺便呢，就多说几句哈，这个list来讲呢，List来讲它也需要咱们往里边放这个数据呢，去重写这个对EQ的方法，上面这个少写一个S也需要呢，重写这个E测方法，虽然说咱们这个list呢，说可以放入重复的数据，就是在放的时候呢，哎，往里边去艾特，它没有去校验，说我现在放的这个数据和以前的这个数据呢，是相等还是不相等，它倒是没有校验过这块呢艾，它倒不会去调这个equals，但是呢，你会有其他的，比如说你想做一个remove啊是吧，做一个contents啊，做个这样的判断的时候呢，它就需要用到这个方法了，所以这个呢，哎是需要这个重写这个叫equals的，好，然后呢，咱们说一下这个set set的话呢，它比较特别一些，咱们呢，先仅仅呢是说。

说它的叫哈希set，或者呢是它的这个子类啊link的哈希set，先以他们两个这个为例去说明啊，以它们两个为例说的话呢，咱们也讲过它的添加过程啊，需要重写几个方法，两个方法对一个呢叫equals，同时还必须要去重写一个哈希code，否则的话呢，你会发现添加可重复数据这个事呢，你发现它这个这个按照equals呢，是处的两个数据呢，也能够添加进去，让这个set呢，就不能够满足说不允许添加重复数据了啊，所以这个high code呢也必须要重写啊。哎，咱们先仅仅是从这个角度来说一下，那么你会发现list色set呢，他们公共的部分就都有这个ecos了，所以咱们往上一提升说呢，诶，只要是这个collection网里边去添加数据，咱们呢，就要求去重写equals，诶其实具体来说呢，是因为它呢是有这个呢也有所以呢，呃，这块泛泛的说了一下。

这两个都有，那么collection呢，就意味着诶就有它，嗯，那么这块呢，其实要再详细的来说，Set的话呢，我们主要用的话呢，大家也主要用的就是哈希set和对link的哈希set了啊，那么其中还有另外的一个实现类，对，就是咱们最后讲的叫tree set，这个tree set的话呢，它稍微特别一点吧。他其实不用去写equals和这个higho了是吧？哎，他主要呢，我们必须要关心他排序的时候用到的这两个方法了，对，那就看你到底是怎么排序方法了，这个咱们讲过两种，那在前面涉及到这个肠类的时候呢，已经说过了啊，一个呢是我们这个叫compable，对，这叫自然排序，这个里边这个方法叫compar，对，To里边参数是一个吧，对啊，呃，是这个方法，哎，另外的话呢，涉一到compar是吧，这个接口，呃，这块呢，我们需要关心的叫can higher，对啊，Object类型O1啊，Object类型O2，对就是对于这个吹塞来讲，首先呢，人家也是一个set，所以他存的数据呢，也一定是不可重复的，那他判断重复不重复的标准变了，哎，它呢是拿。

Compare to和compare来比的啊，这个吹塞呢，我们说了一下，底层呢是红黑树，哎红黑树呢，它首先是一个，呃，这个涉及到数结构，它叫排序二尔叉树啊，就是首先它这个二叉树，就是这个数上它会分两叉，然后呢，能保证的就是说这个数呢，它目前是一个呃，有序的，什么叫有序呢？就是把比它小放左边，比它大的放右边，这时候呢，不存在跟它相等的。

就是要么小要么大，没有相等的这质数，所以呢，相同的元素呢，我们就不让它进来了。哎，这个呢，本身set呢也是这样的特征啊，吹set的话呢，就是小的往左放，大的往右放啊，就这样往下展开就完了，行，这个标准呢变了啊，包括呢，这个transet，咱们往里边放了数据以后，后续呢，咱们也可能去调用说叫contents啊，Remove啊，哎等等这样的操作，这些操作呢，也是以这个方法或者是这个方法为准的，说你怎么叫conds啊，呃，怎么叫这个remove是吧，我想删某个元素，它也是拿这个去判断的，也不会是考虑这个ES了，哎，这个大家额外的去关心一下这个吹菜的就行啊，额外的去关心一下跟我们说的这个呃有区别啊好，这呢是咱们说的这个事儿，呃，这个大家其实要答的话呢，暂时只需要说这样一个方法就行啊，你要说为什么？呃，这就是因为我们后边呢，你会涉及到这个collection中的一些方法的调用啊，就咱们刚才提到了，你判断一下是否包含。

Contains包含某个元素啊，还我去remove是吧，删某个元素啊，还有咱们还有这个叫return。啊，Return return all是吧，哎，是不是就是跟另外一个这个集合呢，求一些他们这个交集对等等，哎这样的一些方法啊，我们都需要考虑呃，调用我们添加这个对象的所在类的一口方法了啊。可以了是吧？嗯，然后呢，下边说a list link list vector3者的相同点和不同点，这呢是一道非常高频的题目，这个所有的同学呢，都应该要会答这个题目啊，嗯，这个题目答的话呢，先找同学来说一说吧，看看是怎么写的啊。

张艳婷，嗯，你说说这个。合他们的相同点的话就是都是集合，然后不同点的话就是相同点都是集合，这个说的有点太宽了啊，集合里边的哪哪一种集合对，都实现了list接口是吧？而list存储数据的特点呢，是。有序可重复的吧，是吧？哎，所以他们三个呢，都作为这个我们说叫容器了啊，它们三个存的数据呢，相同点就也都是有序可重复的对吧？嗯，然后不同点的第一个就是它是线程安全，VE安全，嗯，然后另外两个是有一些问题。

有一些什么问题啊，对线上不安全嘛，是吧，核心的那俩字别省啊。是，嗯，它是拿数组存储，它是拿链表存储，这个呢，Be底层用什么存呢，不清楚，咱们看过源码啊，也是数组，他也是数组啊，查找起来效率比较查找效率快，嗯呃，增加或删除这个增加呢，其实准确的说应该是插入是吧，就增加呢，咱们其实可以，呃，如果只是泛泛的说增加，其实分成好几种情况啊，比如我现有的有些数据了，不管你是链表还是说这个数组增加呢，从头上这种要增加，从中间呢也要增加，从尾部呢也要增加，那对于我们说从尾部增加这个事儿，其实呢，嗯，其实这个release你要非要说的话呢，能稍微好那么一点点，因为它直接呢就放到书组里就完了，而对于这个link list来讲，除了往里放，它是。

它的这个用这种指针来回指一下是吧，操作呢，稍微多那么一点点啊，一两步，当然这个也不是说大问题啊，就是说在尾部添加这种事儿呢，其实A还稍微好一点点啊，但关键呢，就是说在中间或者是头部添加啊，这个呢，对于俄release来讲，这个就非常的崩溃了啊，这个你涉及到往后移啊，或者你要头部添加，那就所有的都得往后移，哎，效率呢，叫我们link list呢就要差一些是吧？嗯。那这个VE这个效率怎么看呀，包括呢，我们开发中你你到底用不用，到底怎么用这几个类啊呃，建议的话就不要用VE，哎，就是建议使用这两个，这个呢就不用了是吧？哎，这是一个作为古老实现类出现的，所以就很少用了，哎行，那基本上就把这几个点都提到了啊好，请坐啊嗯，再稍微的都说一下啊，就是呢，这三个实验类，哎首先呢，相同点，那都是list接口的实现类了啊，所以说咱们在开发当中啊，首先明确一点，开发的时候呢，咱们用谁用的多呀，整个这一章来看啊啊啊对俄list之前先说一下这个这几个接口，这几个接口当中，咱们用的比较多的一个是set，一个是map啊呃，一个是list，一个是map，这个set呢用的比较少一些。

哎，比较少一些，而这个list的话呢，其实就相当于咱们原来用数组，咱们去存了很多数据啊，用数组存的，那后边呢，咱们基本上都用list去替换了，那数组呢，大家也看到有很多的使用场景，所以这呢，我们都用list去替换啊，诶你想装很多的什么数据啊是吧，包括像之前咱们举例的时候说到大家看到这个页面当中的这些数据啊，像这些数据呢，诶这个我们都是用这个集合去装，那这个集合呢，很显然就用list去装了。

啊，用list去装就是言外呢，就只接大家只要涉及到多个数据，通常这多个数据呢，也都是一个类型的了，那这多个数据的话呢，我们一般啊都是用list去装，用size呢比较少。啊赛代呢，主要体现的就是它这个不重复这个事儿啊，也会有啊比如说呢，呃，咱们举个例子，现在呢，我想把这个把什么呀，把咱们Java当中所有的关键字，我想拿一个容器去装。啊，这个用什么装啊，实际上呢，你要用list跟用set好像都可以是吧？啊都可以啊，都没问题啊，这个是都OK的啊，当然呢，你要有额外的一些诉求啊，额外的什么诉求呢？比如说哎，我们呢，就是呃，这个有很多这个单词，这个单词的话呢，我们这个想往里边去装，只要是它关，只要它是关键字呢，我们就让它往里边去装啊，这是一个需求，或者说就是我们现在已经有个容器把这个关键字都装好了，我现在呢，又想拿一些单词去校验，看它是不是这个关键字。

啊，这个时候呢，用谁比较好啊，哎，用set呢就要好一些啊，这里边呢，我把这个所有的关键词都放到这样的一个集合当中，用set装的，我来了一个，我判断它是不是关键字，你要是用list去装。假设啊，这个咱们有几好几十个哈，假设我这就先写个，比如说40个吧，那你用你要用list去装，那就意味着你拿着这个单词是不是得一个一个的去ES。那这个效率其实稍微偏差啊，那我们要是用set去装呢。准确的说应该是哈希set啊，当然你要用吹set也OK啊，我们用一个set去装的话呢，你首先呢，是不是去考虑用哈希库的，呃，这个方法先获取它的哈希值是吧，我直接定位到那那个位置上看看呢，有没有这个呃数据啊，如果有的话呢，在ec比发现诶还真都是一样的，那说明呢，你填的这个在这里边已经存在过，那就意味着你填呃你判断的这个单词，它就是一个关键词了。

就是用sad呢去比这个单词是不是一个关键字，其实这个效率要高一些。对吧。哎，这呢，就需要大家你对我们讲的这个源码，还有它这个添加过程呢，比较熟啊，你后续做这个呃，操作的时候呢，你知道哪个效率高了啊，这是这样，就是它呢，也有一些这个具体的使用的一些场景啊啊再比如说提到像这个机场啊，这个机场呢，咱都知道它有一些这个叫什么禁飞名单啊，基本上每个国家都有啊，就是限制一些人员出境啊，算是这个黑名单一样啊，就是一旦呢，发现你在这个禁飞名单当中，然后呢，我就不让你出境了啊，那这个呢，禁飞的这个名单我们用什么去存啊赛了吧啊，你要是用吝色去存啊，这个倒不是说关心他这个呃非得有续啊或怎么样了哈，就是主要你还是这个问题，你要用例子去存，现在来了一个人，这个人呢，到底在不在这个经费名单当中，是不是又得一个一个的去比，效率比较差，那我们要用set呢，线上哈移值是吧，直接呢去那个哈移值那个位置，你看看对应数组上，呃。

它它这个底层不也是个数组嘛哈赛啊先找一下看看有没有值啊，有的话呢，你再ES一下，直接呢很快的就就比完了，就啊就比完了啊这个所以说我们用S呢更合适，同时呢，你这个经费名单本来呢，它里边呢大家也是不相同的嘛，同时的话呢，你这个名单里边先填的谁后添的谁，其实也无所谓，主要关系呢，就是这里边呢是不能重复的，诶我们就用这个set去装就比较合理是吧？诶就这个情况啊，就是它呢也有些具体的使用场景，但是综合来讲的话呢，诶使用的是偏少的啊，综合来讲偏少的，而我们这个list和map呢是比较多的啊map呢，咱们这个今天呢就讲这个，讲到这儿的时候，我们再举一些这个具体的场景啊，成这儿呢，就是说的这三个结构，然后这三个结构里边呢，像list既然用的比较多啊，那这呢就提到了这三个具体实现类，首先呢，需要明确出来，就是也是自然而然，自然而然的一个事儿啊，你得先能提到你。

开发中用哪个用的多是吧，那很显然诶这个用的要多一些，对它呢，其实是我们的一个默认选择了啊，那这里边呢，其实比较他们三个关键呢，大家呢，就是这样去说哈，先把这个和这个we他俩之间说清楚。啊，一个呢是主要的，一个是以前古老的是吧？啊这个呢不安全，这个安全，这个效率高，这个效率低，呃当然也有个共同点，哎底层呢，哎都是出组啊还有一个区别，这个呢就涉及到源码了啊哎，你说哎我看过这源码，然后呢，俄list呢，哎扩容的时候是1.5倍是吧，这个we呢两倍对有这样一个小的区别啊这就完了，哎把它俩呢说清楚，接着呢，你再把这个a list和link list说清楚。

一般呢，这两个它俩不去直接比啊，一般就是拿着list跟这个比了，跟这个比，那list跟link list去比啊，关键点就是它们底层这个存储的结构不一样了，哎结构不一样了，那基于这个结构的不同导致呢，就是我们提到了它的一些操作上就有一些区别了啊，就我们说的这个一些插入啊，删除啊是吧啊这个效率高啊，这个效率偏差啊，如果呢，你要是呃只是呢在尾部添加，包括呢，我们经常呢，会去找某个位置上的元素，哎这种操作多，哎建议呢，对还是用a list。哎，它呢，因为直接呢，我就定位到那个缩引的那个位置了啊，这个它的复杂度呢，相当于是O1，比如说呢，我们我想找角标为五这个位置上的元素。

哎，我直接呢就定位到角标五这个位置了，所以它的复杂度是OE啊，但是呢，你要是link list，我想找它某个位置上的元素。这个复杂度是多少呢？对它是成on了，就对他得从前往后一个月去找啊，找第一个，然后呢，呃，第一个显然不是你想找第五个啊，我就用用一个变量，还得去记录一下，一个一个的next，每next一下呢，你这个加一下，然后呢，你要找第几个位置，哎，我就这个这个往后操作几下啊，所以它呢是一个on的一个复杂度，从查找的角度来讲，A release呢是要效率高一些的，哎，它呢效率差一些，但是呢，你要从这个删除的角度来讲。删除中间的某个或者插入某个元素，那你list啊，删一个后边的一个一个的往前走，它就成了O了是吧，那那人家这个link list呢，它就变成OE了啊从这方面呢，Link list要好，它呢就差一些，所以呢，他们有各自的使用场景啊，就这个意思，对于频繁的哎，这个这个插入删除就用它了啊哎，这就说的又又稍微给大家总结了一下啊呃，你要是再想说深一点，你看对方还没有停的意思是吧。

嗯，你再讲讲可以说什么呀。所以它这个底层的是不是这个源码啊。诶，咱们呢也讲过啊，像earli list link list咱们也看源码了，诶大家呢，可以把这个事儿说一说，比如说你用一个earli list，它底层干什么事儿了，然后我调it的方法里边涉及到扩容了，怎么扩的，哎，这个可以提一提，哎就可以了啊行，其实建议大家呢，你这个要说一说啊，哎，要说一说，不能把它就变成一道纯粹的是一道这个一道题目，然后我就死记硬背它的这个基本答案是吧，不能这样了，呃，在源码的方面呢，大家要能体现出来一些灵活的地方啊好，下一个。呃，这个类接口中的插用方法，这个咱们说过了，这个类呢，因为开发中比较常用了，那里边的方法呢，其实也很多，大家呢没有必要，所有的呢都记得特别熟，但是呢，有几个方法啊，要能拿起来就能写，哎，在例子当中，哎，我们添加艾这样是吧，删除remove这块注意有两个，对，这是一个，然后还有remove可以按照index删的，嗯，修改S吧，指定某个位置上的元素，我可以改成一个新的，诶，这是这个set，然后增删改查get，诶，In性的index啊，增删改查插入ADD index，哎，然后插入一个新的元素。

哎，这个增删改差差长度size啊，这个size的时候呢，要小心啊，这个size呢，返回的是底层数组的长度吗？不是，那是什么添了几个对元素的个数，嗯，这个这个一定要小心啊，所以很多同学这有个坑，就是我们用一个list，底层数组呢长度是16了，哎，然后呢问size size孟朗也写了个16啊这个就不对了啊，那得看你元素到底有几个增删改，查查长度电力几种方法对，准确的说呢，其实三种都行啊，第一个呢，是使用迭代器了啊，还可以用呃，For each，呃，For each for each，或者叫增加for循环也行啊，还可以用一个对普通的这个for也行。

诶，之所以能用普通的for呢，就是咱们有索引，就像你这个数组有索引一样啊，所以它可以用，但是你要collection就不行了，Collection是泛泛的说说我们有一个存储单个元素的这样的一个集合，这个呢，因为它呃也也相当于包含着set的情况啊，像set呢，主要它没有索引他的无序啊，无序呢就没有所谓的啊，你是第一个，你是第二个，你是第三个，没有无序嘛，谁先来的谁后来的无所谓。

哎，是这个意思啊，就像咱们刚才提到的，我想把这个所有的关键字放到这个集合当中，那这些关键字呢，彼此都不一样的啊，谁先进来的，谁后进来的无所谓啊，这个机场的这个禁飞名单啊，禁飞名单这些人肯定不一样啊，即使姓名一样的，他们身份证号也不一样，我们可以综合的去比，说他们是不一样的，但是呢，谁先添加进到这个这个这个黑名单里，谁后来的无所谓啊，所以它是一个set的，自然而然也就没有索引了啊。行在下面这个便利，这个呢是写代码的题，这个需要大家掌握，我就不在这写了，一会儿复习的时候再看一下，再往下。

Set存储数据的特点，无需的，对，不可重复的，这个大家都要会，这个非常简单啊，这要说不出来，那不应该了，那常用的时间内这个几个呀，三个啊，有哈希赛塔，对，诶这个啊，哎，哈希set，哎，Link，哎，哈西set吹，诶set我们呢讲了这样的主要的三个，呃，彼此的特点就是咱们还是提到的啊，呃，一会复习的时候我们再说一下，就有点像说这三个一样，把它呢提一下就行啊，从这个重要性上来讲，面试的时候呢，不会去问说这三个实现类，他们彼此的特点是什么，这个面试的时候也不会问啊，那么这三个的话呢，这个大家主要就关心一下，我们从这个无序性，不可重复性出发，怎么去理解它的无序和不可重复性，咱们。

那以哈西赛的为例，说了一下它的添加过程，哎，这个事呢，大家熟悉一下，对于set它的一个添加过程，咱们写到这儿了，Sat。就是这个过程啊，这个过程呢，对大家要求不高，哎，我只是说一个叫理解。啊，这个理解，那么谁要求比较高呢？我们讲哈奇map，哈希map呢，其实跟他这个过程呢，基本上是一致的啊，就是因为呢，哈希set其实它的底层呢，对就是一个哈希map，咱们现在说哈希set呢，其实这里边说的这些事，其实都是涉及到的是哈希map了，为什么我讲set没有带大家看源码呢，因为看源码呢，就看到map里了啊，那还不如咱们直接呢就说map了，那就成这样了啊这也是为什么大家你会发现啊，这三个类下边呢，我们讲map的时候呢，你会发现有正好对应的几个结构。

这个呢，对应的一个叫哈希map，哎对，这个呢，对应的叫link的哎哈希map，哎这呢对应的叫吹哎map，原因就是我new一个哈西set底呢，他就帮我new一个哈希map，我new一个link哈set底层就帮我new一个link哈map。啊，同样它也是如此，所以说我们想关心他们三者的，说底层到底怎么实现这个添加啊扩容的，其实我们只需要关注这个结构就行了，那从重点性重点上来讲呢，面试的时候也只会问说哈希map的底层实现原理，不会去问哈希set的。如果恰好被人给问了，那你说这个哈希set的底层原理就是哈奇ma，哎，那我给你讲一下哈奇ma的底层时间，哎就可以了啊行，这呢是一个set本身呢，咱们开发中用的也相对相对来讲啊要少一些，从使用频率上来讲，所以呢，我们这块呢，基本熟悉这几个结构它的特点啊就行，好这呢咱们这几道问题。