00:00
各位,我们接着来讲数据结构和算法的下一个内容叫哈希表,那么首先给大家说哈希表呢,它是属于数据结构,它是属于一种数据结构,不是属于一种算法,这点大家请注意一下哈。那哈希比是个什么呢?我们仍然是从一个实际的需求来看,这是我以前刚刚参加工作的时候呢,去,就是我刚刚大学毕业,大学毕业呢,我们去面试的时候呢,遇到遇到的一个题,大家一起来看一下。这个提示什么呢?他说有一个公司,当有新的员工来报道的时候,要求将员工的信息加入,就是把员工的信息加到我们这个管理系统里面去,那么要求有ID、有性别、有年龄、有住址等。也就是雇员的信息,那么当输入该员工的ID号的时候,就是把这个员工号的信息的ID找到时候,要求查到该员工的所有信息。
01:05
那么他有一个要求是说不允许使使用数据库,尽量节省内存,速度越快越好。啊,当然肯定是,都是要求越快越好,那这个时候呢,其实点名了,就是希望我们使用哈希表,或者说叫闪电来实现,就是这么一个题,那同学们呢,在学Java的时候应该学过哈table。哈希table啊,对对不对,像哈希table,哈哈map呃,吹赛等等这样的一些东西,那么同学们有没有想过,像Java提供的这些歌集合里边,它的底层是怎么实现的?它的底层是怎么实现的?那这个时候呢,其实这道题就要求我们自己来写一份哈希表。那么哈希。通过我们自己写哈希表呢,能够更深刻的理解这个哈希表它的一个含义,好了,那现在呢,我们来看哈希表它是怎么来的呢?我们来看一下它这有个需求。
02:08
哈希表的基本介绍哈希表呢,也叫散列表。它是根据关键码值,这个关键码值就是一个,就是你在进行这个数据操作的时候,它会有一个关键的一个属性,比如说我们前面讲的,呃,就是员工的ID号,这个就是它的一个关键码值。那么通过这个关键码可以么?可以干什么呢?可以直接进行访问的一种数据结构。所以说我们可以看到哈希表,它是一种数据结构,那么也就是说它通过把关键码值映射到表中的一个位置来访问,从而加快查找的速度,那么这个映射函数呢?我们叫做闪离函数。哦,我们叫做闪电,就说什么意思呢?就是说我们给他一个关键码值,通过一个方法或者叫函数能够迅速的定位它在表中的一个位置,我们把这个呢叫做散列函数,存放记录的数组呢,我们称之为散列表,也叫哈希表,就这个意思,那哈希表它这个,呃,为什么会存在,它的意义又是什么呢?来我们画一个图。
03:13
那么我们来看一下,嗯,最早的时候呢,比如比如说我们现在呢,各位同学。这样子啊,我画一个表格。比如说这次呢。我们的。一一段代码,一段代码,比如说现在呢,我们写了一段Java程序。学了一段Java程序,那这个Java程序我们要去操作数据,最普通的方式是不是这样做的,就是这有Java程序,那么Java程序呢,我们要操操作数据库,一般来讲我们可以这样直接操作。对吧,我去操作数据库。是这样子的吧,然后数据库呢,经过一番操作,把这个结果又返回给我们Java程序,Java程序拿到这个数据过后呢,进行显示。
04:02
是这样的一个流程吧,因为我们数据。数据呢,一般来讲都是放在数据库的,但是这种结构呢,它有一个问题什么呢?它会对我们的。对于我们这个数据库的操作可能非常频繁,有一些数据呢,没有必要每次都去查数据库,在某些情况下。不需要,那这个时候呢,一般在公司里面你会怎么做呢?一般你会这么处理。你会加一个缓存层。对不对,你会加一个缓存层,比如说。我们在这个地方加一个什么呢?加加一个缓存。缓存层。那么一般来讲,我们提高提高这个检索的速度,一般就是把我们常用的数据加载到缓存层,然后呢,我们能够在缓存层里面取数据,我们就不到数据库取数据,那么缓存层呢,一般我们可以使用缓存产品,对不对?通常情况下我们使用相关的缓存产品就可以了,那比如说我们常见的缓存产品有哪些呢?比如说同学们可能接触到的像这个red。
05:16
或者是同学们接触到像这个memory。等。是不是这是现有的缓存产品,但是在韩老师这个时代,就是我们那个刚刚参加工作的时候呢,其实没有red,也没有没catch,我们会怎么办呢?我们会自己写一个缓存,就说我我们也可以自己写,自己写,写出这个缓存缓存层,那这个时候我们就可以用一种数据结构来说,比如我们所说的哈希表就可以,哈希表呢,其实从某个程度来说,它就是可以把我们的数据先加载到内存。加载内存,把它放入到我们的哈希表中,诶这样子呢,我们在取数据的时候就无需到数据库取,什么时候才到数据库取呢?大家可以看到。
06:04
现在老师在给大家讲什么呢?讲这个缓存层的意义,也就是说哈希表它在实际应用场景会怎么样,对不对?那干什么呢?如果你不在某些情况下用缓存产品可能太重量级了,你就可以自己写个哈希表,那这个时候我们可以事先把我们的数据先放到这个哈希表中。我们放到哈希哈希表中,然后我们取数据的时候,先在哈希表里面取就完了,这我们提高我们效率,就这意思。那么哈希表的结构有哪些呢?比如说我们常见的是可以用数组。数组加上什么呢?加上链表。这是一种结构,还有一种结构呢,是什么呢?数组我们加上什么呢?二叉树也可以。因为二叉数呢,如果我们用的是二叉,呃,二叉排序数,那这个性能呢,就会有所提升。
07:00
那不管是你用数组配合链表,还是用数数组,这写错了啊数组。还是用数组配合二叉树呢?其主要的目的其实就是干什么呢?就是去提升我们这个数据的查找速度,因为为什么要这样做呢?因为如果我们每次都是直接查数据库,速度太慢了,而且对数据库压力太大,所以说我们经常会干什么呢?把数据先放在哈希表,然后呢,我这个程序先到这哈希表去取,取不到我再到数据库去。然后呢,我可以把这个经常用的呢,再加载到哈希表里面就可以了,这样就提升我们的速度,明白我意思吧,那如果一级缓存不够,一级缓存不够,甚至有人可以做二级缓存,也就是说如果一级不够,我们可以再加一个缓存层,这样就形成我们的二级缓存,这个我就不去说了,其实原理就是一样的啊,二级缓存呢,我们可以通过再哈希可以得到。
08:00
好,这就是老师给大家讲的这个哈希表的一个由来,哈希表的一个由来,它是这样子的,那么哈希表它到底是我们以数组加列表的形式来讲,它到底在。这个内存布局里面,它是长什么样子的呢?各位同学请看这张图。这张图呢,就比较清晰的啊,就比较清晰的把这一个。把这一个呃,哈希表的一个结构给同学们说出来了。哎,你看这里是一张表,看到没有。这是一张表么?每一个表呢?它放的不这呃,这是一个表,但是也可以理解成这是一个数组了,那么这个数组它放的是什么呢?它不再放的是普通数据,而是一根链表。看到没有,它是一个念表。那么你们你们注意观察,它是一个链表,也就是说我们这个数组变成什么数组呢?变成链表数组。
09:00
变成链表数组,那么当我们要去查找一个ID的时候,当我们要查找根据一个ID查找的时候,我可以先用散列函数。来得到我们这一个信息,会在这个表里面的哪一条列表。这样呢,就直接在这条列表里面去查,从而提高速度。你打个比方,比如说现在我们有15条链表。我们有15条列表就针对这个,那如果我来一个,比如说我来一个值,对不对,是这个111,我魔上15。我就知道我这个111ID号应该是在哪一条列表,我就直接到这条列表去取。这样呢,相当于说我们速度就提升了多少倍呢?提升了15倍。这样比我们单独用一条链表就快,那整个数组加链表就形成了一个所谓的散列表,也叫哈希表,好,这就是我们哈希表的一个最基本的工作原理,也是它的一个内存布局图,大家明白。
10:04
好,下面呢,我们准备给大家来完成前面提出的这一个上机体,谷歌公司的上体,从而让大家更加深刻的理解哈希,那当我们自己写出一个哈希表过后呢,我们就。再去看。一些源码,或者说理解底层的东西会更清晰。好。关于哈希表的一个基本介绍,我们就先说到这里。
我来说两句