00:00
各位老铁早上好,欢迎来听朝哥聊面试,今天呢,我们来谈第15道面试题,当我们出现哈希冲突之后该怎么办呢?啊,那我们来看一眼啊,首先啊,我们得清晰什么是哈希冲突,那么我们知道在上节课啊,我们谈了一个东西,就是在这里面的话呢,我们可以通过啊哈希算法,然后去快速的定位当前存进去的这个元素,它是不是唯一的对不对?好,但是呢,知道了这个底层啊,它这个数组的容量是有限的,比如说就五个格子对吧?但是当你往里面放100个元素的时候呢,那难免会出现什么问题呢?难免会出现啊某些元素它们虽然长得不一样,比如举个例子啊,比如说这个第一个人是A。OK,稍等一会啊,第二个元素呢,叫AA,有可能它俩是不一样的,但是他俩算出来的那个哈希值啊,这个哈希值它是一样的,然后呢,经过运算之后呢,它俩都会同样放在某一个位置上,比如说放在第一个位置上,OK,就比如说位置是零啊,那好,那这个时候就有什么问题呢?这时候意味着是这样子的,假设呢,A先来,A就在这个位置里面,已经有了,结果呢,A过来之后呢,发现什么呢?发现这个位置又有人占了,这就是我们说的哈希冲突,那好了,那这个时候怎么办呢?
01:14
OK,那这个时候的话呢,在JDK里面的话,他是这么玩的,他首先第一个玩法就是通过哈扣这个方法确定了位置,第二个如果这个位置已经有人站着了,那这个时候得判断一下,怎么判断呢?所以这个时候调一调equals方法。Equals方法。好,通过这个equal或的方法来判断说我俩是不是一样的,只果一比较,发现什么呢?AAAA跟A是不同的东西,那好,那就能放进来,但如果说发现那什么,比如再来一个AA啊,再来一个A,再来个A啊,再来一个A,这个A的话呢,他发现什么,他跟这个原来的A呢,肯定是一样的嘛,所以他就放不进来。OK,所以这个时候的话呢,就会就是不能进来了,所以很简单两步骤,第一步骤的话呢,是哈code确定位置,第二个步骤的话是通过ES来比较这个东西是不是相同的啊,如果是相同那么就不能放进来,如果不同就可以放进来,所以呢,这个equals的判断规则就需要你自己重新去写了,你怎么定就是你说了算啊。
02:15
OK,比如说像字符串啊,他那么它重写这个方法,它比较就是内容啊,OK好了,如果是你自定义类型,那你就要重写这个equals,比如说你根据什么,根据里面特定的属性的值哎去做比较,OK好,那最终的话呢,这里面就会形成什么,形成一个链表,也说其实在最后的话呢,这个每一个数组元素里面,它底下都是一个什么,都是一个链表,所以呢,放着一个又一个的元素啊,在这个位置,实际上第一个,然后呢,最后再这样,第二个,第三个就是形成一个链表,所以所谓的哈希表,实际上来说,它本质的结构是什么,就是这个呢,是一个数组,大的来说是一个数组,数组的每一个元素呢,是一个链表。OK,就这么一个情况啊,这就是我们说的哈希表的结构啊,哈希表的结构,但是在我们JDK1.8之后呢,做了一点的改进,什么意思呢?因为啊,它考虑到一点是什么,随着这个元素越来越多,大家本身它会做扩容,第二个的话是什么?就是说这个链表啊,它也不能太长,因为太长的话呢,你想看这个时候是不是类似于回到我们最初的那个起点的问题啊,依然需要遍历这个链表去做比较,所以链表太长,我要便利太长的元素,那么效率也会随之下降,所以的话呢,在JDK1.8之后呢,它有设置一些临界值。
03:33
当达到某些临界值之后,它就会将这个链表呢作为一个升级做一个改变,变换成什么?变换成一个红黑数啊,红黑数的结构好,那么说到这你可能会问了啊,那到底是这个临界值是多少呢?OK,这给大家留下一个小小的题目啊,大家可以看一下相关的源码,把这个答案呢答到公幕上啊OK,那么看看答案能不能答对啊好,那么今天的话呢,关于这个哈希冲突的解决,我们稍微总结一下两个点,第一个的话呢,我们通过哈希code的确定位置,当我们发现这个位置呢出现了从有元素的有元素存在时,此刻发生high冲突怎么办?我们通过equals做比较,如果相等抛弃,如果不相等,加进来形成一个链表,当这个列表太长,我们发现效率也会下降,所以这个时候的话呢,我们会把它转成恒黑竖OK好,那么这样的话呢,树我们知道树的查找效率肯定是比链表草效率要高,所以呢,这样这方面的话呢,就是性能有了提升,OK就是整个的。
04:33
一个结构的变化啊,另外一个要注意个点是什么呢?这个哈扣的方法的写法呀,他肯定是要什么要写写写好就是分散的,我问的一个问题,留下一个思考题,如果说我们将哈扣的方法每次都返回一个固定的值,这样可以吗?啊,一个思考题哈希扣啊,每次返回固定的值,这个OK吗?这个做法有会不会造成什么样的问题呢?好了,大家可以把你的答案啊留在屏幕上,好,今天的话呢,我们就分享到这。
我来说两句