8.2.1 简单的哈希算法在线视频

那在前面的那一小节当中我们使用

链表来代替静态数组解决了这个

用户的人数难以提前预知的这样的一个问题

细心的同学可能已经发现前面的事例

当中的每个链表 它的这个节点其实代表的

是日志文件的一条记录 并不是用户

那我们上一章要求统计不同用户的在线时间

为此呢 需要对每次读入的这个新纪录

去查找这个新纪录它对应的用户

是不是已经出现过

那么当使用数组来做这个事情的时候

其实可以通过它的下标的变化

可以非常方便的通过线性查找这样的一个算法

就能够确认这个记录到底有没有在

以前的里头出现过呢

现在这条记录是不是代表了一个新的用户呢

但是对于链表来讲这个问题就变得复杂了

因为这个链表当中的每一个元素

它在内存当中并不是紧密相连的

不能够像数组那样的通过一个整数下标

去访问指定的节点 那这样的话

我们就问一个问题 就是怎么能够提高

链表节点的访问的效率呢

假如你都是每次操作那个next

然后通过指针一个一个去访问那效率就比较低了

那能不能把数组和链表它们两个

肯定有各自的优点 把他们结合起来呢

我们知道这个数组的元素和整数的下标

它是有一个对应关系的

正是因为如此呢它去访问起来就比较快

那为了提高链表的访问也让它快起来

我们是不是也能够去把链表的元素也跟

一个整数对应起来呢 那怎么才能把一个

链表的节点跟一个整数去对应呢

那我们今天要说的一个内容就是

把用户的编号 去对应着一个整数

通过一个专门的函数去完成这样的一个映射过程

那么这个函数的算法该如何实现呢

这个已经有经典的这种思路

就是用哈希算法来完成这样的事情

那个哈希算法实际上就是

把一个类型的数据去映射成为另外的一个类型

那么一般来讲呢 是映射成一个整数

而这样的一个映射过程它是通过计算来完成的

你事先规定的只是规定了它的计算方法

并没有把它每一个数据编成什么码规定出来

这话什么意思呢 我们大家都知道在

这个C++语言里头 有一个称之为ASCIIII码表

的这样的一个内容 那么这个表格里头

人为的事先的规定了每一个字符英文字母啊

数字啊标点符号等等 对应的二进制值是什么

给它一个编码 这是事先规定好的

永远如此固定如此 而我们现在想要的

是说一个我有可能在写程序的时候不知道

它是什么内容 但是我需要你给出一种办法

能够找到它对应的一个固定的值

这个值你每次算都是它 我们需要有这样一个过程

那么这个我们把它称为哈希的这种算法

要完成的这种任务 那么凡是能完成这个事情的

我们都把它称之为是做了一个哈希

那你也可以理解为是把每一个不同的对象

在我们这里头是每一个不同内容的链表节点

为每一个这样的节点去打上一个整数的标签

这个打整数的标签 打什么 怎么打

就是哈希算法要回答的

下面我们看这样的一个这个示例的代码

那这是一个把字符串映射成为整数的一个

简单的哈希算法 那顾名思义还有其他

可能复杂的一些算法对吧 这个我们由于

时间有限就不给大家去详细的介绍

这个地方呢讲一个差不多够用的一种办法

这里头我们定义是一个函数

这个函数它完成的把字符串映射成整数的功能

所以它的参数和返回值类型很简单

参数是一个字符串类型返回值是一个整数

这个是由你的功能来决定的

所以我们在编一个函数的时候啊

是根据需求去设定它的参数和它的返回类型

至于名称这当然是由你自己的爱好去决定

我们这里头用的是哈希这样的一个单词

那怎么才能把一个字符串这种类型

变成一个整数呢 或者说我应该怎么去

算出一个值去代表这个字符串呢

这里头我们给的方法是

把字符串里头的每一个字符

我们知道它是跟ASCII码是有对应的

每一个字符都有它的ASCII码值

我们呢把这个值拿出来 去相互之间进行一个

异或的操作 大家知道异或是一个

二进制的按位的操作对吧 那么根据一个

异或它的这个ASCII码的值

这个二进制值就会不断的发生变化

所以我们刚开始的时候给它一个

sum这样的一个初始值为0

定义这么一个变量初始值为0

然后呢把每一个字符的这个ASCII码值去

异或到这个sum上去 通过这样不断的累计起来

最终这个sum就会得到一个值 而这个值很显然

如果你字符串的内容是固定的

那它的这个值就会固定的

你什么时候去调用它都是恒定的一个值

但是呢如果说字符串内容不一样

那按照我们以前的这种设想

我们是希望它算出来的值也不一样

不过大家数学基础好的同学可能已经猜想到

像刚才的这样一个简单的哈希的算法

它其实是不能保证你任意给的一个字符串

得到的最后的一个映射的这种整数值

是不一样的 你不能 这没法保证这个

所以就有可能会发生两个不同的字符串

得到相同的整数值 那这不就麻烦了么

没关系 因为少量的或者说一定程度的

有这样的一个多个不同的内容的字符串

对应到同一个整数上去

并不妨碍大多数或者很多的字符串

它们各自有不同的整数 这就是我们要达到的目的

所以这样的一个通过上面的方法

我们就可以把用户的编号

就是那个字符串映射成一个整数

这样的话我们就可以把这个整数

就是你算出来的这个整数 去当作一个数组的下标

那这样的话呢就可以去拿这个对应的数组的这个元素

来关联去保存这个用户信息的链表的这个节点

就像我们现在看到的 我们定义一个指针

组成的这种数组数组的每个元素都是指针

每一个指针都是指向一个链表的头的

所以我们定义一个

Noda*hash_tab[256]

这样的一个数组元素 这么多的数组元素

那因为每一个字符呢它对的ASCII码值

在这个反复的异或或者运算的过程当中啊

这个整数值不会超过一个自己能表示的

整数范围 所以我们呢就用256个单元

这样的一个元素这个数组

就可以去完成不同的字符串的这个链表

这些片段的指向 那么前面我们说过

不同的用户的编号是有可能映射成为

同一个哈希值的 就是说Hash(id_1)==Hash(id_2)

那如果这个事情真的发生了

怎么办呢 那我们看这么一个示意图

假定在某一个元素数组的元素

它的下标是就像现在看到的id_1这个字符串

所对应的哈希值 也就是id_1的哈希值作为

数组元素的下标 而对应的这个元素呢

是一个指针 这个指针就指向id_1

就是现在这个图表示的内容

那现在id_2它的哈希值也等于这个

怎么办呢 没关系 我们把它串起来

所以刚才那个指针那个哈希值对应的

那个下标对应的那个元素指向的id_1

现在id_2也等于这个哈希值

它的下标 它的哈希值也等于它

也访问这个下标元素的下标的这种元素

我们把id_2用以前讲过的链表的操作方法

把它串接到这个id_1的前面去

那这样的话在同一个哈希值下面

有可能对应着多个节点

那它们相互之间组成的一个链表

那有同学说这还不是一个链表么

其实不然 我们以前啊 只用链表的时候

就像这个图上大家看到的 你是把所有的节点

串成的一个唯一的链表 一个长串所以这个里头

你要访问某一个很麻烦的 得从前面一个一个

挨家挨户往后找 对不对 所以效率就低啊

那现在是什么情形呢 现在我们用了一个数组

数组的下标就是这个节点的id值

它哈希运算之后得到的一个整数值

用它来做数组下标 也就是说相同的这种哈希值

会由同一个数组的元素做为头来指向形成一个链表

那这个链表我们会发现它其实是有多个的

每一个数组的元素都有可能指向这个链表

那很显然这个链表其实是原链表的一段

换言之一个很长很长很长的链表

通过这种办法通过你哈希的运算

通过把它对应到一个数组的下标上去

通过让数组的这个元素去指向这个链表的头

我们就把这个长链表拆分成了很多很多的小链表

像我们这个例子里头通过字符的

这个ASCII码值的这种运算 我们得到了256组小链表

那你想想看在我们以前是一个很长的链表

你去访问数据和你在256组里头去找一个组

然后在这一组所对应的小链表短链表里头

去找一个元素 那很显然是后面这个快

你可以设想一个最理想的情况对吧

把整个链表均匀的分成256份

那就意味着你原来在访问的时候一个一个找下去

碰到你需要的停下来

而现在呢你可以去根据它的下标

去访问那个256分之一这样的一个小链表

那么当然效率就高多了 我们以前在讲这个折半查找啊

分置法啊分置法的思想啊 其实是跟这个道理是一样的

把它拆成这些局部的小集合小链表那么通过这种办法

来提高这个链表的访问效率 同学呢可能已经想到

这256个不够啊 我这有4000多个记录呢

那可能将来还成千上万呢 那用户有600个呢

你这个256个不行啊 那是因为我们现在为了介绍

这个哈希的这个非常巧妙的思路

我们用的是一个很简单的哈希算法

如果我们去查一些参考书找一个复杂一些的

比如说你能够把他映射成一万个不同的值

这个数组有一万个元素那你区区600个用户算什么啊

对不对 它不就散开了么 到最后有可能理想情况下

一个数组元素指向一个节点 独门独户

那不就跟数组有什么区别呢 那也可以快速访问了

所以这个比方关键是我们要选择巧妙的哈希算法

让我们想去算出来的整数值 能够实现满足某种条件

满足下面的条件就是说 如果你对象不同 内容不同

我就能得到不同的整数值 没有这种重叠

没有这种我们称之为碰撞 这种哈希算法就是很好的

当然这个有难度了 我们专门有人去研究这个内容

我们这里头举一个简单的例子

但是你要想到这是可能的 只要你把它算法弄好了

它是有可能把这个链表啊 它这些元素啊打的更散

通过这种办法 我们就提高了链表的访问的效率