00:00
各位老铁晚上好啊,那咱们今天的话呢,谈一下第14道题,那如果感觉对你有帮助的话呢,欢迎大家点个赞啊,那好,那咱们接下来的话谈一道面试题是这样子的,就是说如何高效率的去判断啊我们集合元素是否为一,什么意思呢?就是说我们现在呢有一个集合,这个集合的话呢,里面可以放很多的元素,但是呢,我们希望的话呢,存在这里面的元素呢,是唯一性的,也就是说假设我存了一个A,那再存个A呢,就存不进来了,A小布拉这么一个效果,那怎么办呢?好,那这个时候的话呢,我们需要去怎么判断它的唯一性的问题,诶OK,当然我们可能想要第一个非常简单的方式是什么?就是便利,对吧,我才用变利的方式来做比较,那这个时候比如说我里面存了ABC3个了,我用再存一个D,那怎么办?很简单,我挨个的去跟他比较,是不是就可以完事了,我挨个跟他比较,挨个跟他比较对吧?诶都比较一遍啊,都比较一遍,那么只要发现了没有一个跟我相同的,意味着我就是唯一的,所以我就可以干。
01:00
吧,就可以把它放进来,是不是这样,哎,但是呢,这种方式好不好呢?问题它能解决问题,但是它的效率高吗?诶可想而知啊,我们需要跟每一个比较,所以很明显这种玩法的话呢,它的时间复杂度呢,是OE啊,不是on啊on OK on那个这里面的话很简单,就是说我们的这个时间时间呢,消耗的时间会随着我们这个数据量的增加而增加,当这个N为三,那么意味着比较三次啊,最多比较三次啊,那也可能啊,不是,就是需要比较三次,OK,就需要比较三次啊,然后的话呢,如果说我们这个数据量达到300呢,就需要比较300次,达到3万呢,就需要比较3万次,所以这个很明显这是有问题的,这个这个玩法呢,它很明显它的效率肯定是不高的,所以这个方式不应该成立,对不对,那好,那接下来怎么让这个东西变得高效率呢?所以我们希望呢,能不能有机会把这个时间复杂度呢,给它变低一些,叭如说变成O1的方式。
02:00
诶,那OE效率就很低了,效率就很高了,是不是啊,效率就很高了,那怎么做到的?那在这里面的话呢,我们可以借鉴一些像我们看到的一些东西,比如说举个例子,你会看到啊,像JDK里面关键的类叫set啊,而这high set的话呢,它很明显它除里面的元素呢,它就是唯一性的啊,那怎么做到的呢?那当我们去观察它内内部源码的时候,你会发现什么呢?你会发现实质上啊,在这里面它用的依然是什么,依然是一个集合立面,底层依然是一个数组。依然是个数组好,但是它跟我们的玩法并不太一样,我们来稍微稍微说一下,大家可以都来听一下啊,它怎么做到这个效果更效率更高的,很简单,这个时候假设一样在这里边存了好几个元素,有ABC3个元素,OK,大家可以注意看啊,我来画一下,比如说有A。啊,然后呢,有B。然后有C,好假设呢,我要存一个D进来,那怎么办呢?好注意这个时候的话,数组大家有下标是不是,所以这里面的话呢,我们先写一下这个C是01234对不对?好,那注意看这个时候我要去存的话,我并不是去挨个比较,而是干嘛,而是经过这个元素会调用它的哈希扣的方法啊,叫哈西扣的。
03:25
哈西扣的方法,调这个方法,然后他要得到一个数值,好,而这个得到这个数值之后要知道啊,基本上来说的话呢,这个是有个数之后呢,我会经过什么一系列的算法啊,就是一个你可以认为是有一个比较规则化的啊,一个规则的算法,那么就会得到一个什么,得到一个再得到一个数值,而这个数值实际上来说是我们要这作为什么,作为我们在这个数组里面的一个什么,一个下标啊,一个下标好,那大家会发现什么呢?这个时候实际上来说啊,唯一的变化什么,就是关于这个对象对应的哈扣的这个东西有可能是变化的,就是不同的对象调查的哈扣的方法,可能得到的数值是不一样的,但是后续的这个规则就算法是一样的套路啊,所以唯一的变化的点是在这里啊,变化的点在这里。
04:11
OK,好,所以这个时候的话呢,我们就可以发现呢,正常来说,常规来说啊,基本上来说,很多的对象,他们的哈code的不同对象它的哈code的方法绝大绝大部分情况下是不一样的啊,但也有可能会出现一样的情况啊,这就是我们后期要在谈的哈希冲突,但是此刻呢,我们先暂时认为是不一样的,那么就会得到什么,就会得到得到一个东西,就是在这里面绝大部分概率是不一样的啊,那这个时候的话呢,那可能到什么,就是说,比如说它得到数值假设啊,假设它数值是四啊,诶,那这个时候意味什么,意味着他要存到的价标,就是在我们这个第四个位置去存放,结果他一看什么呢?这个位置没放东西。好了,完事,这就完事了,没放东西意味着什么?此刻没有人,这地方是没有人跟我一样的,所以他直接就可以干嘛,直接就可以放进来,所以大家会发现什么呢?这个时候我只需要经过一次运算,一次运算就可以确定我能不能放进来,所以大家可以看到在这个最佳的效果来说的话呢,它是可以得到一个什么一个OE的效果的,因为它只需要计算一次,哪怕这边存了好存了什么300个,但是我只要算一次,发现这个地方没有人放,我就可以直接放进来,所以这个时候你看我并不会随着数据量的增加,而我的这个什么,我的这个消耗的时间会增加。
05:25
对吧,OK,大家发现呢,这个时候就是这就是一个高效率的方式,明白这意思吧,OK,那么再举个例子,比如说这个时候的话呢,我们存的另外一个元素,再存一个B,那很明显呢,这个B的话呢,它它放那什么它发是一样的,那就不行对吧?OK就不行啊好。好了,当然如果你有经验的同学会肯定会知道啊,这里面可能没有像想象中么美好,因为随着这个元素越来越多,因为毕竟这个格子有限,但是呢,假设我们现在往里面真的扔300元素,就可能会出现所谓的哈希冲突,那么出现哈希冲突之后又怎么办呢?所以的哈希冲突就是可能啊,我现在又在存一个元素,是这样子的啊,我现在存一个元素叫什么叫E啊,叫E,但是它可能算出来结果它就是要放到这个第二个位置啊,第三个位置啊,就是零一啊第三个位置,那么很明显它跟B是不一样的,但是他们算出来的位置是一样的,这个时候我们说的哈希冲突,那这个问题怎么办呢?诶,我们下个面试题再聊啊,这个面试就聊到这里。
06:21
OK,那先掌握我们用哈希算法是能够提高判断微星的效率的,效率非常的高哈,就是什么从OE啊,原来是什么O,就是一个什么质的变化啊,质的变化好,如果感觉对你有帮助的话呢,麻烦老铁们点个赞啊。
我来说两句