00:02
来,那么接下来呢?接下看什么下把这个。我们最主要掌握什么呢?我在这里强调一下啊,最主要掌握我们map集合往里边存和取的时候,它的原理是什么。我现在这写一下吧。就最主要掌握的是。像什么呀?或者叫map.put kv以及map.get k返回一个V以上这两个方法的实现原理。啊是必须掌握的,就是他存的时候是怎么存的,他取的时候是怎么取的。啊,我们最主要把这看一下各位啊,是必须要掌握的,来看一下这个这个图啊,嗯,是这样。
01:06
哈希表呢,这个数据结构呢,它是一个,首先这是个一位数组。这个一位数组啊。那这个一位数组呢,我们这样吧,这样画一下。用黑色比较好啊,喜欢黑色。啊,然后呢,这个呢,我们就给它分开吧。分开啊。来这给它分开。分开一下啊。画图是比较耗费时间的,咱们随便画一下吧,好吧。就是那个叫做什么呀,叫做no数组吧。是不是哎,No数组啊,然后这个里边存的每个元素是一个no。明白吗?哎,这是个对象。
02:01
对吧,这个节点里边有啥呀,各位。是。是吧,哎,这字体太大了啊,字然小一点。UK。还有啥呀?有哈希值。还有什么value?是不是有key有value啊,还有什么呀?下个节点内存地址吧,哎哟,我的天呐,这图画的next。哎呀,我的个天呀。这是个节点啊。往上一点。这个节点呢,它有内存地址。保存内存地址去指向什么呀,下一个节点啊。
03:01
是吧,这个里边也有什么,也有这些数据。啊,它呢,去指向谁呢,指向他。是这样一个情况啊。具体的我就不再画了。在这儿呢,还有一还有一个。是不是啊?就这一个东西啊。这是链表。对吧,包括你这块也是。有。单列表。来。画一下啊,咱别嫌费劲。对吧,哎。再来一个。嗯。是不是指向?这个意思,注意。
04:01
来这个下标是几啊,是零。那这个下边它大点,哎,太大了。下标零啊。这个标呢,是。对吧,这个下边呢是二。看到吗?这个下标呢,就是300数组嘛,它得有它得有下标。这是四。啊,这是五类似的啊类似的。来。那么现在是这样的,各位啊,它是首先啊,我们先去研究一个方法,这个方法叫什么?叫做map.put逗号value。这个方法的一个实现原理。他怎么实现?我把这个字变小一点吧,这样我能写的更多一点啊,它的实验原理是是什么?
05:01
首先呢,我跟大家说一下是这样的啊。首先map这个调的方法,K和value。他底层会怎么着呢?先把你K和Y6干什么?封装成一个节点对象。节点对象啊,它的实验原理,第一步先将什么呀,就K这个V啊封装到哪呀,No的对象当中。这是第一步,第二步呢。第二步是干什么?封装之后呢,它会调用什么呀?K哈西扣的方法,注意啊,会调用就是这个底层啊,底层会调用什么呀。K的哈希扣的方法得出什么呢?哈希值。得含义值啊,然后。嗯。通过哈希函数,或者叫哈希算法。
06:05
将什么呀,我们这个哈希值转换成什么呀,数组的下标。各位啊,会转化成数组的下标。那么下标位置上。下标这个位置上,如果怎么着啊,如果没有任何元素。啊,如果没有任何元素就是空白的,比如这个位置对吧?底层啊会先调用K的哈希扣的方法得出哈希值,然后通过哈希算法或者哈希函数将哈希值转换成数组下标,下标位置上如果没有任何元素,就把元素加进去了。啊,就把node添加到这个位置上了。啊,这是第二步。那如果说呢,如果说注意啊,如果说。
07:05
下标对应的位置上,注意啊,下标对应的位置上。有。No。或者有数据或者有链表对吧?如果下边对应的位置上是有链表的,就这样叫这个有这个你要如果说你上来调K的哈构的方法得出哈值,通过哈值通过哈算法转换成数字下标,通过下标找到了我们这个位置是空的,那这个时候二话不说八就加进去了,明白吧?但如果说你算出下边是二二,上面它有有这个链表,有链表的时候怎么办呢?如果说下边对应的位置上有链表,此时。会。拿着谁呢?拿着这个K啊,就这个K。啊,拿着K和什么呀,和链表上每一个节点。
08:00
中的K进行什么equals?如果所有的。Equals方法返回都是false。那么这个新节点。将会被添加到什么表的末尾啊,将会被添加到链表的末尾。如果其中有一个equals返回了处。记住啊,如果其中有一个equals方法返回了true,那么那么放那么啊是这样的,是这样的,各位啊。假如说啊,听我说啊,这个地方有点稍微有点复杂,各位啊,稍微有点复杂。
09:01
这样,别动了。天哪。行吧,这么着吧啊。第一步啊,就是先将K和Y6封装到我们的node对象里边。封装进去之后,第二步呢,底层会调用K的哈希扣的方法得出哈希值。有一个类呢,叫object,这是老祖宗object,老祖宗这个类当中啊,有一个方法叫哈扣的方法,对不对?哎,哈扣的方法默认情况下,如果你不重写这个哈扣的方法,是不是返回的是对象内存地址还记得吗?你60个对象是不是十个哈扣的值?你有100个对象,是不是就100个内存地址,100个内存地址得出的这个哈值是不是就不一样啊。对吧,100个哈值吧,是不是?哎,首先要知道这个哈构的方法是老祖宗自带的。那么调用我们K的哈扣的方法得出哈值,然后通过哈算法转换成数组下标,下标位置上如果没有东西,直接就加到这了,如果有东西的话,那这个时候会拿着我们这个参数K。
10:10
会拿着这个K,各位啊,这个K和谁呢?和我们这个链表上的,和这个链表上的这个每一个K进行equals。如果说所有的equals方法都是返回false的。那么这个时候它会在这个位置上,它会加到这个位置上,各位。你明白吗?他会加到这个位置上,它会把这个元素加到这,注意啊。Object key object value,这个就是那个节点嘛,In,哈希,然后接下来这是node next。它会被加到这个位置上,然后你这个节点指向我们这个节点,这样的话,这个元素就完成了添加。当然还有一种情况,假如说我们发现这个地方已经有了两个元素,拿着我们这个K和这个K进行什么呀,Equals,然后呢和这个K进行equals,发现我们这个K的equals方法返回了true。
11:10
如果其中一个equals返回了处。怎么办呢?哎,会把会把怎么做呀,会把新的这个节点它的value。啊,把这个Y轴给它替换掉。拿那个新的节点,就是刚才那个加的新的节点嘛,KV装no节点嘛,对吧,原先这个如果这个K和这个链表上其中这个K如S方法返回了处。那么这个时候他会把这个改成什么?的外流。啊,不知道这么说大家理解不?那么这个节点将添加到链表的末尾,如果其中有一个E方号返回处。那么这个节点的value将会被。
12:01
覆盖。啊,这是一个纯的原理,各位啊,这个字跑偏了,行吧,就就这么着吧啊。存的一个原理。那么大家思考一下,我们这种哈希表这种数据结构,它的优点是什么?它的优点是什么,各位?我们如果使用单向链表,会有会有什么样的缺点呀?单向链表就是它的查询效率比较低,大家思考一下,必须得从第一个节点挨着往后找吧。是不是,那么我问大家一个问题啊,如果说有一本字典。大家都用过对吧,小学的时候我们有用这个字典,那字典这个东西啊。来慢慢聊啊,不着急字典我要从什么呢?从字典当中干什么呀?找找什么呢?找中这个字。找这个字。
13:01
你有几种方式?嗯。你有几种方式啊?两种方式对不对?第一种方式是干什么?是从第一页开始,往后一页一页找。直到找到为止。你想想。对吧,哎,直到找到为止。对不对,哎,你拼音笔画咱们先不用这种方式啊,假如第一种方式就是你要找这个中国的中字,你有一种方式是什么呢?是一页页的往后翻,对吧,愚公移山的精神你拿出来对不对,哎,终于翻翻翻翻翻了大概第365页啊,诶终于什么呀,诶找到了。这个效率怎么着啊,比较低。啊,效率比较低,但是他能不能找到呢?各位它是可以找到的,就像这个链表一样。
14:00
对不对,你去第一个节点挨着往后找,能不能找到能,但是就是效率稍微低一些。那么第二种方式是什么呢?第二种啊。实际上是怎么做呢?是从什么呀,从。目录中找什么呢?找这个知翁中。这个汉语拼音对应的页码。啊,假设这个页码是360页。那么一上来对吧,一开始我们就可以翻到哪儿啊,诶翻到360页。对不对,从360页挨着一页一页找对吧,最终找了五页。对吧,在365页找到。
15:01
这种方式显然效率怎么着啊高。为什么?因为缩小了扫描的什么。范围。啊,就是这种方式显然是效率高,为什么呢?因为缩小了扫描的范围,扫的那个范围只需要扫那五页就行了。对吧?哎,那么现在我们这个哈希表的这个数据结构,它有这样的一个优点吗。他有没有这样的优点,各位。那现在这个呢,我是给大家讲的是map的一个铺的方法实现原理是不是,那么大家思考一下map它的get方法的实现原理是什么。返回给Y对吧,Map掉get方法括号里传个K。那么这个方法的实现原理是什么呢?当你调map集合的get方法K,那么这个时候第一步啊是干啥呀?是先干什么,先执行或者先调用啊,先调用什么K的哈希扣的方法,得出哈希值。
16:16
通过哈希算法转换成数组下标。通过数组下标,通过数组下标定位,快速定位是吧,快速定位到哪啊啊到。某个位置上。它因为你调盖的方法,这传个K嘛,它会先调用K的哈希扣的方法得出哈希值,哈希值通过哈希算法转换成数组下标,通过数组下标又快速定位到某个位置上。如果这个位置上什么也没有返回,那。明白吧,就是如果你这个位置上,你看什么也没有,它就会返回一个那。
17:00
明白什么意思吧,哎,如果这个位置上。有单向链表,那么会拿着谁呀,会拿着。K这个参数K各位啊,会拿着参数K和谁啊和单项链表上的。明白吗?和单项链表上的。每个节点中的K进行equals。只要。其中。或者说如果把所有equals方法返回,那呃,Equals方法返回false,那么。Get方法。返回那。
18:02
只要其中有一个节点的。K和参数k equals的时候。返回处。那么此时这个节点的就是我们要找的。Get方法,最终返回这个要找的什么Y。别第一步了,我直接就写全了,各位啊。就是你的get方法的一个实现原理是什么呢?就相当于是说你不是卖这个调get方法传个K吗?那么这个时候呢,他会去先调K的哈西扣的这个方法各位,然后转换成一个哈希值,哈希值又转换成数组的下标,有了下标之后,我们是不是就可以数组嘛,有下标我们是不是直接就直接就通过算法就找到这个位置了。
19:05
对吧,但如果说你找的这个位置上,就是这个位置上没有东西。那它会返回一个那个呗。啊,那如果说这个位置上有单向链表,假如说就长这个德行对吧,那么这个时候怎么办呢?你不是有个参数K吗?你这个K呢会和这个k equals,你呢会和这个k equals,你呢会和这个k equals,发现所有的equals方法都是返回一个false。各位啊,都是返回false,那就代表。没有找到这个方法会返回一个none,各位还是返回none啊,那如果说你这个K在和这个单向链表上的每一个节点进行equals的时候,发现这个K和这个K进行ES的时候反馈的处,那么这个value就是我们要找的value。明白什么意思啊,它的目的实际上其实就是为了什么呀,哎,缩小我们的一个扫描范围。
20:03
他不需要从单项列表的第一个位置开始往后找了。对吧,哎,不需要一个一个去找了,他只需要找其中某一个单项列表就可以了。啊,大家注意注意,它的存是怎么存的,取是怎么取的?来我再说一下它存各位啊,它存实际上是说K和value呢,传进去之后先转换成一个no的对象,有了这个对象之后呢,它呢,接下来它会调这个K,这个哈希扣的这个方法得出哈希值,通过哈值转换成什么呀,数组的下标,那当你数组下标位置上如果没东西的话,它吧就加进去了,明白吗?那么接下来假如说它数组这个下标为二二,上面有这个单向链表的话,它的加还是不加,那取决于我们这个参数K和这个放上面每个K进行equals,如果所有的equals方法都是返回false,那就加到列表的末尾。它加进去了,如果其中这个拿这个参数K和我们这个K和这个KES的时候,发现其中这个k equals返回true,那么这说明什么呀?这说明这个元素已存在,那么这个时候这个value就会被覆盖,就这个节点当中这个就会被覆盖掉。
21:11
这样加进去的。啊,所以说这里有两个重点,各位啊,一个重点是往里边放是一个重点,一个是往外取是一个重点。啊,放的时候它其实。也也效率很快,各位大家看它放的时候怎么放的,各位。他放是不是往链表上放。链表上放增加一个元素需不需要涉及到位移的位移的问题?需不需要位移的问题。各位。不需要吧?大家思考一下。这个一会再说啊。嗯。为什么哈希表的增删效率都高?
22:00
为什么哈希表的随机增删以及查询效率都很高?为什么哈希表的随机增删以及查询效率都很高?中山是在链表上完成。你吧。啊,查询也不需要干什么呀。也不需要都扫描。只需要扫描其中一个。只需要部分扫描啊,部分扫描。那么这个哈希表实际上它并没有把增删发挥到极致,也没有把查询发挥到极致,对吧?它是一个中间体。对吧,它是个中间体,它就是说它有纯数组查询效率高吗,各位。它有纯数组的查询效率高吗?有纯数组的产品效率高吗?没有。
23:07
啊,它有这个纯链表的,纯链表的增删效率高吗?没有。明白吧,它都没有,但是呢,它在这个随机增删以及咱们的查询方面,它都不弱,它的性能都是可以的,因为它是一个诶结合体,各位它是个结合体啊结合体,那么通过杜老师的讲解,你应该知道知道一件什么事呢,就是说这个map集合呀。他这个K呢,会先后掉两个方法。重点啊,重点通过这个讲解,通过讲解可以得出什么呢?可以得出哈希map集合的K。会先后调用什么呀,两个方法。一个方法是什么呀?是哈希code,一个方法是什么呀?是ES。
24:08
那么这两个方法都需要什么重写?都需要重写,各位,那么现在我问大家,为什么我们需要重写?思考一下。为什么放在哈希map k部分元素需要重写E方法?思考思考,各位。为什么放在哈希map集合K部分的元素需要重写equals方法呢?因为equals。默认比较的是两个对象的什么内存地址。我们应该比较什么内容?所以equals是不是得重写一下equals如果不重写,你调用的是object这个类当中的equals方法,这个equals方法比较是内存地址。
25:04
我们比较两个对象应该比较内容,所以equals需要去重写,那雨桐老师光重写equals行不行?这个code如果不重写会不会有问题?那当然会有问题,会有问题啊,一会儿可以给大家演示一下,演示一下啊。就现在你先去理解哈希code和ES都要重写,然后其中ES是必须要重写的,现在哈希code为什么要重写,可能不知道。对吧,扣为什么要重,不知道啊。重写方法吗?大家还记不记得这个哈希map集合,它的K存储元素的特点是什么?还记得吗?哈希map集合的K。部分特点是什么?无序怎么着?不可重复,为什么无序呀?
26:03
不可重复是怎么保证的?来,大家思考一下,为什么是无序?因为你加元素的时候,有可能这个元素是加到这儿的。明白吗?也有可能这个元素是加到这儿呢,也有可能下一个元素啊,是加到这个位置上了,听懂了吗?所以将来在输出的时候,它的顺序怎么着和你加入的顺序不一样。我不知道这么说大家理解不理解。因为它添加元素的时候,有可能是挂到这儿了,有可能是挂到这了,有可能是挂到这儿了,也有可能在这儿,有可能加到这。你输出的时候可能先输出再再他再他再他再他再他再他对吧,你加入的顺序和输出的顺序怎么着。不一样。不是。可以理解吧。为什么无序?因为不一定挂到哪个单项链表上。明白吗?那不可重复是怎么保证呢?Equals方法来保证什么?哎,保证哈希map集合的K不可重复。
27:11
对吧,如果K重复Y的覆盖啊,对吧,如果K重复了Y6会覆盖。明白什么意思吧,Value会覆盖掉哈希map集合,K部分的特点是无序不可重复。无序是因为不一定挂到哪个列单元列表上了。不可重复是因为什么呀,它底层掉了E的方法来保证它不可重,重的话,对吧,它就不放,把value给它覆盖掉。把value给覆盖掉,就。啊。无序,不可重复,可重复Y流覆盖。那么记住哈西。放在哈希map集合K部分的元素其实就是放到哪儿了,哈希set集合中了。明白吧?哎,所以哈西S集合中的元素也需要同时重写,什么哈希code加equals方法。
28:12
方法。啊,这是个什么。不用管它来,那刚才呢,就是我们说到这个叫做它的一个存的一个原理,还有它的取的一个原理,先后都经历两个方法,一个方法是哈一扣的方法来得出哈值转换成数字下标一个方法是什么呢?哎,是它的这个E的方法比较是否相等啊,如果相等怎么办对吧,如果不等怎么办,它是怎么加的,它是怎么取的啊,这两个原理要知道,那么现在大家思考一下啊。我们这个。同一个单项列表上的哈希值一样不一样。这个。这个值。
29:00
这个值。还有这个值一样不一样。是一样的吧。注意啊。注意,同一个单向链表上。同一个单向链表上啊。同一个单项列表上所有节点的哈希相同。啊,因为他们的数组下标是一样的。他们的数组下边是零。啊,所以这个哈希值和这个哈希值和这个哈希值是一样的。啊,但是同一个单项列表上,它K和K的equals方法肯定是false。但同一个链表上。对吧,K和K的equals方法肯定返回的。
30:04
是false都不相等。无序不可重复吗?是不是不可重复,各位啊,不可重复。无序是你存,你不知道存到哪儿了,取的时候是另外一个取的方式。对吧,不可重复,就是靠equals方法,好,那现在大家思考一个问题。我哈扣的方法,在重启的时候给他返回一个固定值行不行?哈西扣的方法需要重写对吧?在重写时。返回一个固定值可以吗?会出现什么问题?
31:00
各位。就假如说我现在这个哈希扣的方法。扣的方法啊。重写的时候返回了一个固定不变的值。全部哈希脂都一样。对吧,如果哈方法在重启的时候返回一个固定值,那么这个时候就会导致什么呀,就会导致它都会放到同一个单向链表上。啊,那这样的话就变成单向链表了,各位就变成单向链表无法发挥什么呀。无法发挥。我们的这个这个这个哈希表的这个性能,各位啊,无法哈希表的性能。如就是哈希表你用不好,就是发挥发挥不了它的性能,各位啊,在这里再说一下哈希表数据结构,哈希表哈希map使用不当时。无法发挥什么呀,发挥性能啊,无法发挥性能,假设将所有的哈西扣的方法返回值固定为某个值。
32:15
啊,固定某个值。那么会导致什么?会导致底层哈希表变成了什么?单项链表,纯单向链表。会导致底层哈希表变成纯单项链表。明白吧,哎,这种情况我们称为什么呀,散裂分布不均匀,散裂啊,散裂分布不均匀。明白吧,就是说你扒一下这个列表特别大,结果这个列表里边就有两三个元素,这里边叭有两个特别大的大列表,是不是,你应该是说,假如说你有100个元素,你有十个链表,每个链表上十个元素,这是一种最极致的状态,各位啊,什么是散分布均匀呢?
33:15
就假设有100个元素,十个单向链表,那么。啊,那么每个单项链表上有十个节点,这是最好的啊,是散列分布均匀的,各位啊,那我们再问大家,假设将所有的哈西扣的方法返回值。都设定为不一样的值。可以吗?有什么问题?就是哈扣的方法,在重启的时候,返回值都设定为不一样的值,就是说你有1万个对象,我这1万个对象,哈扣的方法返回的值都不一样。
34:04
行不行,那这样的话就会导致它底层变成什么,因为你哈希值不像速度下标就不一样,那这个时候放的时候,它就放一个放一个放一个放一个放一个,它永远都不会往单向列表上挂,对不对。对吧,哎,所以说这块呢,就会变成一位数组变成数组了。明白吗?假设将所有的哈希扣的方法反馈值都设定为不一样的值可以吗?有什么问题不行啊,因为这样的话导致底层哈希表就成为什么一维数组了啊,没有链表的概念了。啊,也是散裂分布不均匀啊,也是散裂分布不均匀,各位。就是你要让它散裂分布均匀,你的哈扣方法得重启的时候有技巧明白吗?哎。
35:03
散裂,分布均匀。需要你,呃,你重写哈西扣的方法时。有一定的技巧。啊散分布均匀,需要你重方式有一定的技巧才可啊,有一定技巧可以。
我来说两句