380_尚硅谷_Go核心编程_数据结构和算法-哈希表(散列)1.avi原创

好，同学们，那么我们接着呢，呃，继续为大家讲解这个数据结构里边的哈希哈希表，哈希呢，呃，也可以叫做散列，就是把它散开，就是到时间呢，根据一个咱们的哈希的一个函数或叫散列函数，把我们的这个查询呢或者是添加。把它分散到不同的这个链表里边去啊，我们可以用它来做，那么大家先来看一个实际的需求啊，这是谷歌公司的一个上机题。啊，这个题呢，它主要是考察，考察就是程序员他的。他的这个，呃，他的知识结构里面有没有这个哈希的这么一个思想在里边。他的题呢，是这样出的，说有一个公司当有新的员工来报道的时候，就将该员工的信息加入啊，有什么信息呢？有ID，有性别，有年龄，有住址。

到时间呢，我们在演示的时候呢，我只添加ID和。名字啊，其他我就不加了，然后呢，输入该员工ID时，要求查询到员工的所有信息，他的要求是这样子的，不允许使用数据库，这是第一个前提，要不让用数据库。让大家想一想，如果不要用数据库的话。那你怎么做呢？你可能用数组对不对，但是人家这地方是有要求的，要。节省内存，而且速度要越快越好，这是一个要求，就是他要求咱们自己设计一个东西，但他这个原先原原题是要自己设计。啊，不能用现有的，比如说你用的麦啊，这些他不能用。啊，他不让你用这个东西，他让你自己设计。OK，那么这个时候呢，其实他考察点就是看你会不会哈希表的这个原理啊，这个是他的一个需求，我们先放到这啊，需求先放这好，这是一个实际需求，就是说。

怎么去存储我们的数据啊，然后呢。把它。把它这个做的速度更快，这是我们的哈希它的一个实际需求。哎，看一下实际的一个需求，对。那么这个需求。诶，现在撤回来他需求是什么呢。就是一个这样的一个商机体，把它先放过来啊。翻过来。好，这是他一个实际需求。那么有这个需求过后呢，我们就直接来看一下哈希表的一个基本介绍。呃，哈希表它的一个基本的原理是什么呢？大家看这张图，你看大致也就明白了，它这样子的啊，散列表。它有时候呢，也叫这个哈希表，就散列哈希table嘛，叫哈希表，它也叫闪力，那么是根据关键码值，就根据一个关键的码值而直接进行访问的数据结构。

就是我根据你的一个码，我可以直接进行访问，也就是说它通过关键的码值映射到表中的一个位置来访问记录。以加快查找的速度。那么这个映射函数呢，也叫闪离函数，就是它通过一个闪离函数能够把我们的这个数据分散到不同的这个数据存储的这个位置，当然有可能是链表，也可能是数组，但这个是根据实际情况，我们这呢就用链表来做。啊，那么也就是说相当于说，如果我们把这个哈希表存存放起来，那么相当于说你自己就可以做一个内存的数据库了。啊，而且呢，根据你的需求可以定制。如果说你不会这个的话呢，你肯定只能依赖于现有的一些数，呃，一些这个数据，比如像map呀，或者是像这个这个切片怎么来用的，对吧，但是有些时候呢，需要你自己去做，所以说哈希表的一个结构呢，大体长得就这样子的，你看它怎么做的呢，每一个地方是一个链表，大体可以看到是个链表。

是链表，而且大家看到它的链表呢，是这样做的，它的ID值你看啊，它一共有15根，16根链表。它有16个链表。对，16个链表的话呢，同学们可以看到它的不同的这个码值就是这个，比如这个ID吧，它分散到不同的链表里面去了。而且大家可以观察到，它在往里面添加这个数据的时候呢，是按照从小到大的顺序往里面添加的。你看这个零号链表。它的第一个是496，第二个是896，是从小到大。那么一号链表存了三个元素，1337和3353也是从小到大，那就说我们呢，要通过自己的一个方式，我们也来用这个这个哈希表来存放我们的一个雇员系统。

那完成它的增删改查，就是要做这个东西，好，那么明白这个东西呢，过后呢，大家对哈希表的底层它的实现我们就比较清楚了，好，这是哈希表的一个介绍啊，哈希表一个介绍，我也把它放到这里啊，同学们，这是哈希表的一个介绍，板书一下。OK，介绍是什么呢？他的一个说明。啊，它的一个说明。第二个呢，我们这儿有一个简单的示意图。这一个简单示意图，待会儿呢，我们要自己来构建这么一个哈希表，我们要自己写一个哈希表。好，这是哈希表的一个基本介绍，那下边呢，我们就来具体的实现啊，那代码也不算太多啊，不用太多，我们直接就做这个案例了，这是我的要求。

我先把这个要求放到笔记里面，我们就开始写。啊，应用实力哈希表的就是说实用哈希。哈希表来实现，来实现一个雇员的雇员的管理啊，管理系管理这个系统啊，但是比较小啊，就增删改查吧，就完成了增删改查。增删改查好，我们来一起玩一把。把它先放到这里来啊，同学们。好，那么具体的要求呢，就是这样子的，我我先把它整理一下，这是一个应用实例啊，这是一个应用实例，谷歌的一个上机体。先放这儿，那具体的描述，这是对题的一个描述，刚才呢，大家已经已已经也看过了，我再看一下它要求。这是他的一个题的说明，要求是这样子的。哎，要求是这样子。好，第一点，不使用数据库。啊，然后呢，速度越快越好啊，速度越快越好的话呢，就需要我们把闪离到不同的列表里面去，第二个呢，他要求添加的时候要保证雇员按照雇员的ID，我这写一下啊，叫做雇员的ID。

雇员的ID从低到高插入。好，那么这是要求我的一个简单的思路。思路分析，我整理一下。我的思路是这样子的啊，同学们。第一个呢，我肯定会用链表来实现哈希表，而且这个链表呢不带表头。这是第一个。啊，第二个呢，我要画出这个示意图了。然后呢，我要实现的功能是增删改查。啊，这层改查呢，我主要完成一个增加。还有查询删除和修改呢，我可能会留给同学们啊，因为我把核心的搭起来了。好，那待会查询呢，我要完成两种查询，第一种是显示所有的员工，而且要知道这个员工是在哪一个链表里面，因为这个图有很多链表，我们到时间呢先用七个链表，我们不用16个，16个太多了啊，我们用七个链表，然后呢，还要提供一个IID查询。

好，这是我的要求，现在呢，我必须给大家画一个图，如果不画图，大家可能会听的比较蒙圈。就你你也不知道我写到哪个地方了，好，我先把这个图画一下，我要怎么去实现它啊，来分析一下我们的思路。待会儿呢，我们要完成的这个雇员基于哈希表的雇员管理系统的示意图是这样子的。基于我先把思路讲清楚啊，然后再写代码，然后再写代码好。好，基于基于什么呢哈。哈希。Table的雇员。雇员管理系统的一个思路分析。好，先把这个说清楚，然后呢，我们再写代码啊同学们。

好12，嗯，我怎么来做这个事情呢？我怎么在做这个事情呢。首先。首先，我会先建一个结构体。好，我先说一下，这会出现一个数组。这边会有一个数组。这个这个这个数组里面呢，一共到实验会有七个。会有七个这个，呃。链表啊，我先把这个画像。好，这是第一根，第一个链表，待会长什么样子我都会画出来的。诶。好，这第一个。怎么复制不了呢？好，这是一个啊，一共有七个。好，这是第二个啊，第第三个啊。好，再来一个。

七个，待会儿我画的时候呢，重点分析三个就行了。这有一个。好，这是第六一个。第一个好，然后我往下面再挪一下啊挪一下。好，再来一个。好写好了，写好过后呢，这个这个是个数组，这是个什么数组呢？它是一个链表数组啊，它是一个链表数，它长什么样子啊，我先说一下。往稍微的排一下。A拍一下。然后呢，这个呢，就相当于是我们的一个哈希表。好，这个是我们的哈希表，待会呢，我取个名字就叫哈希table。哈希。哈希table，那么这个哈希table呢？它指向这个数组。好，它执行这个数组，当然了，呃，这个数组里面呢，我们里面有七个七个元素，那么这七个元素分别是什么呢？告诉大家第一个元素。

啊，到时我们整，我们整理一个这样的东西，叫它是这样一个东西叫link。Link。十个链表数组里面呢，第一个下标为他。好，这个就是我们的第一个元素。好，这是第一个，然后呢，紧接着有第二个，我就我就写两个啊，下面的意思类推。倒时间它指向谁呢？它指向的是这个里面的元素。好，我把它画一下。好，这个是一个蓝色的线，它指向第二个。对他执行第二个。好，也只一个南线吧。那么问题来了，那有些同学老师，那你这个哈希table长什么样子呢？它是一个结构体，注意听这样子，这这样一下子大家就明白了啊，我把这个结构体一写出来，长什么样子大家就清楚了，它是一个结构体。

它结构体里面呢，呃，实际上就有这么一个东西。它这个结构体里面定义了一个这样的东西什么呢？他定义了这样一个东西是link。二里面呢，是一个七七个元素，它这个七个元素里面是什么东西呢？是固原的。链表。那也就是说这里面存放的东西。就是大家看到它不是有七个元素吗？那么这里面的这个值是什么呢？就是它它这个元素里面具体是放的什么东西呢？它放的就是这个东西放的是link。Income。放的是这个东西，就是它是一个固原链表。那有些同学说了，老师固源链表里面是什么东西呢？好，我现在把这个固原链表的结构体给大家拿出来讲一讲。好，我把它扯出来啊。把它扯出来。我说一下e p link，它又又是一个结构体，因为它里面又包含很多方法，所以说它是个结构体，它这个结构体是个什么样子的呢？

啊，哈希表的世纪，伊兰斯项世纪，它是一个这样的结构体，是structure。它里边也只有一个元素。什么元素呢？就是指向这个链表的雇员的图纸人。也就是说，它只有一个东西叫had。新赝品。OK，那就说它它实际上呢，是指向一个图层，那么它它这里面其实就存放了一个指针而已，就是它这里面只存放了一个指针。同样的道理，下面的呢，下面这个元素也是一样的。OK，好，我把这个往后面下面挪一下啊。好，这个呢，我们也把它扩扩扩大一下。好，大家应该看清楚了，那也就是说他将来这边会指向什么呢？它会指向很多的雇员，那么雇员有有哪些呢？我四个亿，比如说我们将来这有五个啊，有三个雇员吧。

有三个雇员。好，我画一个这这画一个别的颜色啊，画个别的颜色，好，它这个是一个头指针，它是头指针，那么它就先指向了第一个固原。对，直间第一个有柜员，那第一个固员完了过后呢，这个雇员下面还有雇员。就他这面下面还有雇员。紧接着他还有固源，就它会形成一个链表。而且呢，顾远的ID是从小到大进行这个设计的，就说他指向他。我要把我的思路说清楚才能写代码啊，不然的话大家听的就很蒙圈，连接起来，那打个比方。打个比方，你这个是零。你这个是零，那么到时间我这个ID会怎么存放呢？我会用一个哈希函数，我取模来决定哪一个固源放在哪一个链表里面，比如说你是林的话，假设我一共有七根链表。

你你你的编号如果是七的话，我就放到这里面去，打个比方，这1ID等于七的一个用户。为什么ID等于七的用户放在第一跟列表里面去呢？因为七模七刚好等于零。这样的话，大家想一想，如果我在按照ID查的时候，我一下先取模，我一下就把它分成了指定到这个列表里去了，你看。这样查询速度相当于说在七个列表里面先指定一个，而不是在整个大列表里面找，这一下就把我们时间的速度节省了。接上了这个六倍，好，当然如果下一个再来存的话呢，他也应该是取模过后等于零的ID，比如说14。但如果如果不是14的话，比如说是个21也是有可能的，那么下一个呢，我再试一个一，比如说下一个呢，按照从这再下，呃，那么比如说四再加一个，比如说28。也可以。

那同样的道理，你这个地方有一个链表，那么下面呢，我们也有可能有链表。哎，那四个一。你比如说下面又来一个链表。对，那这个列表里面存的是这个列表，它显然是它的这个下标应该是一了。那什么样的雇员会放在第二根链表里面去呢？就是它的ID取模，取模期过后刚好是在一好，比如说这个是八号。A8毛七等于一，这个假设我们是。好了，这个地方上哪去了？飘了啊飘了好这个呢是28。好，这个地方呢，是。啊，假设这一定是。这个地方有有写错啊，这个地方是二，诶不对呀。刚才这个是22。22。22啊，22磨七的话呢，刚好等于一嘛，啊，这边是29。

好，以此类推。但是它这个也可能是不是连续的啊，同学们不一定是连续的，比如说你这个地方没有29，而是直接在这个基础中再加了个七，比如是这个36啊，这也也是有可能的，也是可能就是说它不一定是连续的，是但是他要保证从小到大就行了，好以此类推，那就相当于说我们一共有七根链表。那么问题来了，说老师，那你这个节点是什么东西呢？它也是一个结构体，就是一个具体的固源，我把它拉出来。好，它是什么呢？它就是一个一个具体的固原呢，它也是个结构体。好，那么这个地方呢，它也是个结构体structure。它这个结构体里面放的置是什么呢？好，这个就是一个一个一个的，雇员呢，比如说雇员应聘，那么它里面的信息就应该是比如说有ID in，有名字。就是具体的共源信息了，节点是不是？当然它应该还含有个特别重要的一个，呃元素，就是指向下一个节点的一个指针。

吉他。好，同学们可以可以看到啊，我们一个哈希表的示意图，咱们就分析完了，也就是说我们我们要完成的这么一个东西，就是首先有一个哈希表，这个哈希表呢，里面存了七根。或者叫七个链表，它是一个链表数组，当然每一个链表里面呢，它每一个，每一个链表里面，它指向了一个自己的，呃，雇员链表，而且呢，不含投资人。啊，然后呢，这个这个链表里边，它有一个指向图纸，就就是指向指指向这个雇员的一个指针。好，那么通过它呢，我们就来完成它的增删改查。首先我们看一下这样有什么好处啊，同学们。如果我们这种方式。他为什么速度会变快呢？打个比方。

我们做一个简单的比较啊，比如说现在我有。一个链表就一个链表，这一个链表里面呢，我们串了有。1000个雇员，假设只有一个链表，你没有，你没有闪开，没有散裂，那么比如说你只有一个链表，我要查询ID，等于。998的。998的，那你只能是。按照这个默认方法，单列表的话，就是一个一个的去查，对吧，一个个去查好，那你就应该查998次才能找到这个ID，但是呢，如果我是用这个散列，那原先我在存的时候，我会怎么存呢？我在存这个ID等于998的时候，我首先用998。我先用998磨一个七，同学们998模七会等于一个具体的值。它会等于一，那么我在插入的时候就已经确定这个九九八一定是在某一根。

某一个列表里面，就它的编号是谁我都是知道的，那么这样插的时候呢。插进去，插进去过后呢，我在查的时候，大家看在查的时候，你你把9998也给我了，那么998我仍然是取了一个膜。我取模A，我同样也能得到这根这个998是存在哪一个链表里面的，那我直接就到这个指定的链表里面去查，这这一下子我们时间就减少了很多。对吧，你原先是呃，是到一根电表，现在我一下分散出去了，所以说这个查询速度呢，肯定是原先的，从这个逻辑上来说，应该是原先的这个六六倍嘛，至少。啊，这样子的速度快吗？速度快减少了，比如说你原先是呃。原原先花七秒，现在我可能只花一秒。就找到了。如果你的闪裂是七根。你节省了七倍，那假设你的散裂，你将来这个列这个哈希表是100个或者是1000个，那显然这个就更更舒服了，那它它的价值就在于我们可以提高这个速度，而且大家想一想。

将来你在做开发的时候，遇到这样一个情景，你用这个来做的话，效率就会大大提升。比如说。你将来做了一个维护用户在线的这么一个功能。你用传统的方式会怎么做呢？你会把一个用户的在线信息，把他的ID和状态直接存到数据库里面去，当然如果这个用户的状态发生变化了，你就会去操作数据库。显然这个速度会很慢。假设我们，我们假设有。假设同时在线有10001000万个人。假设有1000万。各位，如果你按照。传统的方法就是操作数据库。如果你按传统方法操作数据库，会有什么后果呢？就是有一个人的状态发生了变化，或者有一个人要来读取。

一个ID的状态，那你只能操作数据库，这个量是很大的，对数据库的冲击很大。但是如果我们把我们做一个优化，因为你的瓶颈就在取取用户状态嘛，就是维护。就是维护用户的状态，我举个例子啊，状态，那假设如果你都去操作数据库，这个数据库压力太大了，那我换一个思路。我换一个什么思路呢，我这样做。因为我很我很清楚的知道，用户的状态不是一个特别重要的数据。为什么我这么分析呢？因为你的用户状态要么是离线、在线或者繁忙，他第一次如果没有更新上，他第二次来了更新上就行了，他不是一个特别重要的数据，丢了就丢了，丢了一次也无所谓，他下一次再补过来也可以的，他不跟我们一个余存款的余额那么重要，所以说像这种经常操作的，又不是特别重要，必须入库的数据。

我们就可以采取这种方式，怎么办呢？我做一个结构体。我做一个，比如说我就叫user status。OK，那么这个结构体呢，我就设计两个特别简单的。简单的字段，注意听。啊，最近就是说这个使用价值在什么地方，比如说它有个ID我存进去，对的，然后呢，我再用，我再用一个BAT。我再用个bit来存放它的不同状态，比如说零表示什么，一表什么，二表什么，我可以用这个东西，比如说它一个状态。State。OK stay这个状态呢，我也用一个bit来表示好，那现在大家可以可以看到，可以看到，如果我把一个用户就直接存放到哈希表里面去，而且我散列给他来上多少个呢？不是不多了，咱们直接来上2000个。也是用2000个这个链表把它串起来，那这样的效果会有什么好处呢？大家想一想，我可能会浪费一点内存。

但是我在操作一个用户的状态的时候，不管是修改还是查询，我的速度就是以前从理论上说就比以前快。2000倍。但这是理论值。实际上呢，还会涉及到一点并发的问题。啊，因为你如果是读的话，并发问题都不用考虑了，因为这个列表在这个地方，你读的话，你1万个人来读，1000万个读都无所谓。我速度大大提升。我至少不用倒。数据库就完了，那么内存的开销又有多大呢？我算了一下，其实并不大。你比如说我们这个假设int就算64吧，最大的了64我们可以表示一个很大的用户了，那么假设我们存放1000万个用户，我们。会浪费，会需要多少内存呢？大家看一下啊，如果要我们存1000万个用户。我们只需要乘以九个字节，因为一个用户的这个ID占八个字节，BY占一个字节，那一共是九个字节，那么算算它占用的内存有多大，可以计算一下，简单计算一下1000万个，十百千万，10万，百万，千万一千个同时在线，然后呢，乘以九个字节。

这是九个字节，九个字节我们除以1024是K。这么多K。再除以1024就是兆了，那么一共需要多兆，多少兆呢？85兆其实根本不算什么。你85兆C那点内存你还在乎啊。我我我很珍惜内存，那是以前的事情，那如果你再存一个十，就可以存一个在线用户了，一个G的内存都不到。所以说这种优化它是很有价值的。而且这种问题它是不仅仅是这种问题，用到只要类似的问题咱们都可以玩。所以说我们说这个算法在什么时候用到呢？就说你不经意的时候就用到了，如果你不会用自己写哈希，你全靠迈普，你做不到这一点。

你做不到这一点，而且里面有很多特别的东西，比如说用ID，我还可以用名字，名字呢，我先给它算一个固定的值对不对，然后呢，把它转成一个整数，这种先算算算法很多的，你用这个名字把它生成一个唯一的一个32位的一个整数，再模，连名字都可以查。对，这个就很有价值了，同学们明白我的意思吧，所以咱们咱们学东西呢，你一定要理解它的价值在什么地方，你学起来才带劲，对吧，如果说你不明白这个东西有什么价值，第一个你不想学，第二个呢，你也觉得没啥用嘛，这个东西但是呢，在你用的时候，你突然发现，哦，诶，原先韩老师讲了一个这个东西。哦，给我一点思路，我可以通过这个方式去优化，哎，这就叫。代码的优化，好这个分析呢，老师就先讲到这里。