day23_集合/22-尚硅谷-Java语言高级-HashSet中元素的添加过程

好，那么刚才呢，咱们把这个set当中叫无序的不可重复的这个事儿呢，我们首先呢解释了一下，那么想把这个事儿呢更清楚的理解，那我们就得关心一下这个数据到底是怎么存的啊，到底是怎么存的，就像咱们呃前面呢讲这个a list一样，只不过呢，A list呢比较简单啊，里边呢就是个数组，而对于数组的操作，操作呢，咱们又比较熟悉了，就是一个位置一个位置往里边去放就完了，所以呢，我们那个讲release的时候呢，重心其实没有在呃放这个事儿上，那就按照这个index往往下放就完了，那么对于我们这个set来讲呢，咱们就有必要关心一下它这个数据到底是怎么存的，其实正是由于它这个存的过程啊，我们回过来呢，才能更好的去理解这个叫无序性和不可重复性啊，这呢我们就说一下这个第三个事情啊，或者这呢，我们看成是第一个第一个大的这个事儿啊，就是叫无序性不可重复性的一个解解释啊，第二个问题呢，就是我们关心一下这个set中这个爱的。

操作它的一个具体的执行过程啊，就是添加数据的过程，或者要添加这个元素的过程，这个过程呢，我们以啊叫哈西set为例说明，因为呢，你像这个吹set跟它呢还不一样，所以呢，咱们说这个叫哈西set啊看看它这呢，我就先把这个事儿呢先说清楚，然后呢，我们在这再去描述一下啊这个哈希set，我们呢以它为例进行一个解释说明，我们提到了set当中存的数据呢，都叫做不可重复性，就相当于呢，添加到这个set中的数据呢，不能重复，那么我们先想一下，如果咱自己做这个事儿该怎么做。啊，咱们自己做这个事儿，自己做这个事儿，咱们有一个容器了，可能一开始你也不知道赛特它到底底层是什么，只是咱们说了一下，说哈希赛呢是数组啊，假设呢，你现在还不知道啊，还不知道，那么如果想让你设计一个结构，说保证这个结构呢，无需不可重复，那首先呢，咱们先所看一下这个所谓的叫不可重复啊，这个不可重复呢，其实是更主要的一个事儿。

后边呢，咱们用set啊，用它呢来去过滤一些重复数据啊，那主要呢，用它就是用的这个功能啊，我们现在呢，假设要往一个容器当中放数据，先放了一个，然后呢，我要放第二个，我要放第二个保证呢，呃，它跟已经放的这个数据呢，都不能重复，呃大家说怎么保证啊，我们是不是要拿这个跟这个去equals一下，好，那S一下ES一下以后呢，是个forces，那就进来了。啊，进来了，那现在我又有第三个元素，第三个呢，保证跟已有的不重不重复，我就得需要拿第三个，是不是既得和第一个又得和第二个去尼cos一下，哎，那么都是false的时候，我们才能让第三个进来啊等等等等等等等。

那么如果我现在要填填什么呢？第1000个数据。我想保证第1000个这个数据呢，啊，也得是满足不可重复性，你是不是要拿它跟前边的999个去比，很显然像这种效率很很低是吧。这个效率就很低了啊，这个数越多，这个效率呢，你发现这个低的越多，这个呢，你这个要便利的这个次数呢就越多了，这个显然呢不太靠谱，所以说呢，我们这个赛的话呢，就没有像咱们刚才说的这样一种方式呢，去保证它的不可重复性，它呢就哎用了一种比较巧妙的一种方式来做的，他怎么做的呢？他呢先来考虑一下这个叫哈希值，那现在呢，我们就说一下这个哈希set，它底层呢实际上是一个数组，诶我们把这个数组的概念呢，就引进来了啊，它呢底层是个数组，那默认呢，我们通过这样的方式呢，这个去造一个对象，底层这个数组呢，我们知道数组一旦你创建长度就确定了。

这个我们就得多说一句，在GDK7当中呢，这个长度就指定了，八当中呢，一开始也没指定，A的时候呢，才指定了，跟a release呢一样，那么它这个长度是多少呢？长度是16。这个数度的长度16，然后它怎么做的，它是这样做的，你看它这种做法呢，是不是说效率要高很多啊，我呢先来第一个元素，第一个元素的话呢，嗯，肯定呢，涉及不到跟谁去比了，因为就他自己肯定呢是不重复的，那我首先呢，计算一下这个元素的一个哈希值。这个哈希值就是调用我这个元素所属类的哈希扣的方法算的。所以呢，你看我们那会儿填的时候呢，不是把哈希库呢重写了哈啊这个哈希值，这个哈希值的话呢，我们保证什么呢？就是你要是同一个属性，相同的属性啊，这个哈义值呢，我们让他都算出来是一样的啊，就是它是唯一的一个哈义值，就是拿我们这个对象的属性来计算的，那好我算一个哈义值，假设呢，我们算了这个哈异值，是啊13462，随便呢，我说了一个数，那么这个数我说呀，就决定了它在我们这个数组当中的存放位置。

但是你肯定不能说存到角标是13462这个位置，那显然也没有那么长，那这呢，我们就需要做一些操作了，这个操作呢，就类似的一些叫散列函数啊，或者你就说哎，通过某种算法是吧，哎，我们呢，就计算出来这个数它到底在这个数组当中存在哪个位置，那咱们举个简单的道理啊啊，哪怕我拿这个数，我就简单的跟16去取个模。你想想我们得到这个数是不是就零到15了，哎，那你取末以后，这个这个这个结果我呢，就作为你这个数存在这个数组当中的一个位置，只不过咱们这种呢比较low。啊，就是最简单直白的一种操作啊，那么我们这个呃，API里边呢，用的比这要复杂一些啊，啊就是说我们这个指定方式呢，其实有很多种啊，这个我们先不去重点说这个事儿，就是这个数呢，确实决定了存在哪，那你像我们要用这种方式去算的话呢，那显然这个数呢，算出来它可不一定是零啊，那如果你要是不零，不是零的话呢，它就可能在后边的某个位置，那比如说它就在这了，因为呢，你是第一个，所以呢，用不着去比别的了，直接呢第一个元素就放这儿了。

就写个一，那么类似的，我再接着去艾特第二个，第三个第四个，那后边呢，比如说它会有一些操作了啊，假设我们再去艾特，再艾特的话呢，我又得去算一下你这个添加的元素的哈希值，哈希值呢啊又是某一个数，这个值呢，就决定了在这个数组中的存放位置，假设我们一算啊，它应该在这儿，在这儿呢，这个位置你先看看它上面有没有元素，如果要是没有，还是直接就放到这。没有呢，我就直接放到这儿了，那么类似的道理，我们再哎放一个三，这个三的话呢，一算诶三的位置应该在这儿，这个位置这个位置，这不就数组的一个索引位置吗？这个位置呢也没有元素，我把三呢也就放这了，大家你想象一下，我现在添了三个数，这三个数呢，可是谁都没有彼此比过哈，这三个数呢，都没有e cos过啊，那我就可以大胆的说，你这三个数呢，它是不可重复的啊，这其实是对咱们这个哈希扣的这个方法呢，在重写的时候呢，是有要求的啊，就要求呢，这个哈西扣的方法和E扣的方法呢，要要一致啊啊要一致，一会呢，我们再细说那个事，那现在呢，我就放了三个数了，那那我接着要放第四个数，第四个数呢，我们诶诶算一个哈气值一算。

算完哈义值的话呢，我们又得需要哎去判断一下，在这个数组中存放第几个位置，好一判断发现诶跟这个三呢要放的位置一样。也就是说呢，我们四呢，要放的话呢，发现这个四的要放的位置上已经有元素了，已经有元素了怎么办呢？是不是咱俩就得比一下了，对吧。

因为咱俩都要放一块儿，那得比一下，到底这个这个是不是有可能咱俩就一样是吧，就得比了，但这时候呢，大家又注意这样一个细节，什么细节呢？这个三个四我都要放在这儿，它俩的哈希值一定一样吗？想你想想还一直一定一样吧，不一定吧，不一定吧，你就好比是咱们就以以咱们这种比较low的这种去判断在数字中哪个位置，我这个数呢，假设是17，假设哈一值是17，那我取模16的话呢，是不是一，那我要是一去取模16是不是也是一啊。就是它只是在我们数组中，数组中存放的位置一样，它俩的哈希值其实不一定一样是吧，对吧？嗯，哈希值不一定一样啊，只是说呢，你算出来以后呢，它俩正好都要放在这个位置，毕竟你哈希值呢，那那个数范围呢，很大的，那我们这个数组呢，就只有16个位置啊，所以呢很小，嗯，那如果三和四的哈希值不一样。

这个时候呢，其实我们就认为它俩呢，其实已经算是不一样的元素了啊，那么我们这个四呢，其实就可以添加成功。那四天龙四往哪放啊，三都已经放上去了，那么哎，这个时候呢，我们就要以链表的方式呢，去存它俩了，链表所以呢，我们这个sat呢，它复杂到哪呢？它里边既出现了数组啊，又出现了链表啊，属于数组和链表的一个结合体啊，那么这个列表到底是谁练谁七和八又有区别，咱们就简单说一下啊，我要是这样写的。相当于是这个三是原来的啊，这个七的是你这个四，我这样指的这个是八的写法，八的话呢，你看这个四在下边，那要是七的写法呢，七的写法这个四就在这了，是这个四呢，指向你这个呃，四相当于是写到这了啊，四想写这这个三呢，就写到下边了。

就是JDK7和JDK8，嗯，就是有这样的一个区别，JDK8的话呢，这个四是写在外边，呃，人家这个位置呢，放的是数组的这个原来的那个元素，然后七的话呢是呃，让这个新的元素放到这个位置上，然后呢三呢就往下就他俩颠倒一下。这个大家怎么去记呢？哎，恰好呢，咱们国家有一个成语是吧，叫七上八下啊，简直呢就是绝了是吧？啊七上就是七的时候呢，七的元素在上边啊，八的时候呢，新的元素在下边，哎，就就这样正好去匹配啊，可能是照着咱们国家这个成语来的是吧？嗯，哎，总之呢，你知道它这是一个链表结构了。那这个链表结构就这么着了，这呢是我刚才说的是他俩的哈希值不一样的时候。这个时候呢，都没有ES啊好接着讲，呃，我现在呢，呃，假设呢，这个这个就放这儿了啊，那这是相当于是你添加就成功了，嗯，那么我们这是你添加成功了，那还有可能是不成功，那我就换个位置来说吧，比如我现在才添加这个五个第五个元素哈，这个第五个元素呢，我们一计算这个哈一值，然后再去判断在哪个位置，发现根一是一样的啊，根一的位置一样，根一的位置一样，咱俩一看咱俩的哈希值呢，哈希值啊，人家这俩哈希值刚才是不一样哈，所以呢，直接就填成功了，那现在你俩孩义子一判断呀。

还一直一样。哈一一样的话呢，这时候呢，就不能简单的判断说这俩元素就一样了，哎我们呢就得e cos了，哎当你俩哈一值一样，然后呢，我就要e cos，那我e cos的话呢，就是咱俩呢得判断一下，我们呢是调的五这个元素所在类的e Co方法把这个一呢，哎，就是相当于我这儿掉了五的这个ES啊，然后把这个一呢作为参数放进去，放进去以后我们主要看返回值，那如果返回值是一个处。

处说明咱俩是不是就真一样真一样，那这时候我们这个五呢就没戏了。哎，一样嘛，哈希也一样，ES也一样，那就真一样啊，所以这个五就添加失败了，那么如果这个E的返回值是false呢？哎，Falsex的话就相当于说，呃，虽然咱俩还一直一样，那可能就是巧了是吧，恰好哈一直一样，但是ECO咱俩还真不一样，呃这时候呢，这个五也得填下成功，所以说本质上咱们判断呃这个重复这个事儿的话呢，还得掉下来ECO才行啊，ECO是true了，那才是真一样了啊，那返回要是false，那这时候呢，还得添加成功，还是按照咱们刚才说的这个啊八的话呢，就是哎五它新的元素就在下边了，哎就是这样个过程。那么真实的我们这个set存的话呢，就是我刚才说的两个事儿，那么这个事儿好处是什么？大家想，比如我们填了很多数据了啊，现在我要填第1000个数据。当然这个第1000个数据，显然这个长度它也会在我们填的过程当中不断的去扩容啊，不断的去扩容，它又不不是16了，嗯，那么具体是多少，这个咱们就得知道它那个扩容的那个规则是什么，你再去算了，这个咱们就不具体说那个事儿了，我现在要放第1000个，意味着前面已经放了999个了，我放的第一千克也是先算一下哈希值，哈希值算完以后呢，先去计算一下它在数度中的位置，好，我们假设是某个位置啊，这个元素呢，我们不妨呢，就是这是第1000个这个数据，那么第1000这个数据呢，我们看到是某一个位置的，那你先判一下要放在这个位置上有没有元素，如果没有元素直接呢就填成功了，你看这个效率比我们刚才自己想象的这个效率是不是要高不止一点。

一个也不用比直接那就填成功了。啊，那这个呢，效率很高，好，那如果说这个位置上有元素，有元素呢，我们就比有元素的话呢，这时候你又得注意一下，这个元素呢，可能不止一个啊。就好比是我们这块呢，假设这个第1000个数据要往这放，你往这放是不是有个三有个四啊，那还有可能是不是还有一个别的，是不是可能还有个别的，就是它这个列表呢，有可能很长。

那我不管你有几个，反正呢，就是你要有几个，我就给你便利几个啊，我要放这个位置，嗯，假设有五个，那你就便利这五个，总之呢，这个它不会特别长哈。呃，它再差，再差他也不会像我们刚才一样，你拿着这第1000个和前面999个去比，它不会特别长的。啊，不会特别长，那这块呢，我们就把这个几个一个一个去比一下，那如果说一个一个比完发现都不一样，都不一样，那你就存下来啊，你就接着呢，往尾部去存就完了，哎就是这个道理，那如果说在比的过程当中发现呢，跟某一个呢，E扣死了一样了，那这时候你就别别往下再比了，这个你就添加失败了啊这个效率的话呢，就大大的提升了。好通过我刚才描述的这个过程，大家回过来再去看我们的无序性和不可重复性，无序性你看第一个在这儿，第二在这儿，第三个在这儿，所以体现为是无序的啊，是你放在这个数组中的位置，不是按照顺序一个一个来的，这叫无序性，不可重复性呢，就是我们刚才描述的这个过程。

啊，这呢就是我们看源码以后啊，这个当然大家我没带着大家看啊，是是我这块看了，因为这个赛呢，咱们就不带着大家看了，没有必要啊哎，我看了原码以后呢，把这个过程呢给大家描述的，描述完以后，咱们把这个事儿呢写一下啊哎，我一边写大家一边去理解这个过程，这个理解完以后，也有助于咱们后边呢去理解哈希map啊，那添加过程以哈希赛的为例说呢，哎，我们。像。哎，像这个哈希set中，哎添加。添加这个元素啊，添加元素这个元素呢，我叫小A吧，啊添加元素小A，我们说首先首先呢去计算啊，就是调用啊，调用这个元素小A，它所在类的叫哈西。哎，这个扣的方法。

哎，去计算这个叫元素A它的一个哈希值，哎，那么接着说磁哈希值啊，接着啊，通过某种算法，哎，我们现在就把这个事呢，先给屏蔽了此哈希值，接着呢，通过某种算法，然后呢，计算出在。嗯，这个哈希set底层数组中的存放位置。啊，这个存亡位置呢，这个我加上小块啊，即为这个相应的这个索引啊，索引位置。啊，得到呢，我们哈希塞的，呃，就是我们这个元素小A啊，在底层数组当中的一个存放位置，啊得到这个存放位置了，那么我们接下来做什么事呢？那我们判断啊，这个数组此位置上啊，此位置这个存放位置，比如说我们啊就不用加个说index了，判断数组此位置上呢，是否已经有元素，就是你判断这个位置呢，是不是no就完了啊，是不是已经有元素，那么如果。

此位置没有元素。这个我这样说吧，如果此位置上没有其他元素，则咱们这个元素小A。小A是不是就直接成功了，诶添加成功这个没啥可说的了，就那个位置也空的，那我就直接放进去，那么对应的另外一种情况说，如果此位置上呢，有其他元素。有其他元素，回忆一下我们刚才接着怎么办，其他元素B吧。其实这个元素是不是也不止，可能不止一个吧，啊，有其他元素B我们这多写一下啊，或者呢，是已经存在以链表形式。

形式存在的这个多个元素了啊，这也是有可能的，那如果此位置上有其他元素B啊，首先呢，比较元素AA与元素B的哈希值，如果。这这这个比较哈希值这块又得往下分了，这个我们这么着一下啊，这么着一下，然后这个就再往它的下边比较呢，它俩的这个哈希值，那哈希值呢，说如果哈希值不相同，则我们这个元素A呢，就添加成功。哎，所以我们这个元素A呢，就添加成功了，具体的添加怎么放，咱们一会儿说，那么接着说，如果呢，这个哈希值呢，相同相同呢，还不能马上说人家这俩元素就一样，如果还有是相同呢，那么进而需要呢，调用元素A的啊，元素A所在类的E口的方法啊，E口的方法，那就将我们元素B或者说你这有好几个啊，就一个一个呢，通过一个循环的方式呢，往我们这个形态上去放啊调用这个ECO方法，那么我们接下来呢，就又得看这个方法的反回值说ECO方法。

哎，这个方法呢，说返回处。返回处那么表明呢，我们这个元素A呢，确实跟已经存在这个元素呢就一样了，那就要那就表明我们这个元素A呢，添加失败，哎，这就没啥可说的了，失败啊，哎不成功，那如果呢，我们这个ES方法返回false，那就意味着呢，这个跟现有的这元素呢，还是不一样的啊则。

元素A啊，又添加成功。诶添加成功，那么我们这呢，就提到说这是成功，这是成功，这是成功，这三个成功当中呢，第一个呢，比较简单，因为你这个位置上没有其他元素了，所以呢，直接就放到数组中的那个位置上了，那像这里边的我们这个情况，这个我在这写吧，这个呢叫这个添加成功的这个角情况一啊。诶，CTRLC啊，这个CTRLVCTRLV这个呢叫情况二，这个叫情况三，下边呢，我们来一个简单的一个小说明。哎说呢，对于添加成功，添加成功的这个叫，哎情况二。百合这个情况三而言。嗯，这里边呢，因为咱们本身这个位置上呢，已经有元素了，你现在呢，又加了一个新的元素，那么这个对它们这两种情况而言呢，我们说这个元素A啊，它呢与呃，已经存在啊，已经存在这个指定索引位置上的。

啊，所以位置上的这个数据呢，就以这个列表的方式呢进行存储，就相当于呢，他们就以列表方式呢，去个保存数据了啊那具体这个到底是谁练谁这呢，我们简单说一下，在JDK7当中呢，也是我们这个叫新的这个元素啊啊就相当于是一个叫元素A呗，元素A呢哎放到数组中。哎，放到这个数组中，然后呢，这个指向原来的元素。哎，这向原来元素，而我们这个JDK8当中，哎，那么我们这呢，就正好反过来，这个呢是哎原来的元素啊，这个在这个数组中啊，然后指向呃这个呃指向呃咱们这个元素A，哎这样子啊，那如果是这样的，比如说我们这个数组当中，这是第一个元素，这已经有了，现在我要新新添加一个，新加一个，我们就以八为例了啊以八为例的话呢，就是这个呢，指向这个，那现在又来了一个元素，这个元素呢，跟他们都比较一下，发现呢都呃不相同，那就它也能成功，那这个呢，我们就接着往下放啊又来了一个，那就接着往下放，是这个样子的，那要是七呢，七是这样子的，这呢是你第一个元素，现在是第二元素过来，发现呢跟它都不相同，不相同呢，这会我们的假，这是第一个元素，我现在要填第二个，这时候呢，第二个元素呢，它就要放在这儿了，这个一呢，你就放这儿，哎，这样值那来了第三个啊也要放这儿，跟它们俩都不一样，那就是三就放这，二就放这。

啊一呢，就放这儿。哎，是这样子的啊，就是每一个心的话呢，都在上面，所以我们把这个呢，呃七和八这个呢，就总结一句话，哎就是哎对七上八下啊。

好，这呢就是关于我们这个哈希塞的为例，它的这样的一个添加过程，在这里边我们看到了哈西塞呢，底层还挺复杂的，首先呢是数组，其次呢还有这个链表，哎这样的一个结构，那么整体上大家可以我这里边画了一个图呢，哎，去理解一下。哎，放了这样的一个图啊，这呢就是首先呢是一个数组结构，那其次的话呢，呃，有可能会有一些元素呢，呃，放的位置是一样的，但是人家确实不相同啊，那你们就以列表的方式呢去进行存储啊下边是一个扩容方式，这个大家先不用关注，我们讲哈希外的时候呢，再说这个扩容的事儿啊，哎，这就是这样一个方式，所以简单来说的话呢，我们这个哈希set，我们讲了它的添加，其实呢，也就把它的一个底层的一个结构说到了，就是哈希set。啊哈希赛它的这个底层啊，其实呢，是叫数组加列表的结构啊行这个呢，我们就到此为止，这呢就是我们这个添加的一个过程，通过这个过程呢，大家再去体会一下所谓的无序性和不可重复性。

嗯，好，停一下。