哈希算法
将任意长度的二进制串映射为固定长度的二进制串,这个映射规则就是哈希算法,而通过原始数据映射之后得到的二进制串就是哈希值.设计一个哈希算法需要满足几点要求:
- 从哈希值不能反像推导出原始数据.(所以哈希算法也叫单向哈希算法)
- 对输入数据非常敏感,哪怕原始数据只修改了一个Bit,最后得到的哈希值也大不相同.
- 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率要非常小;
- 哈希算法的执行效率要尽量高效,针对较长的文本,也能快速的计算出哈希值.
哈希算法的应用
安全加密
最常用于加密的哈希算法是MD5和SHA.还有很多其他加密算法比如DES,AES.
为什么哈希算法无法做到零冲突?
哈希算法产生的哈希值的长度固定且有限.比如上面提到的MD5例子,哈希值固定是128位二进制串,能表示的数据是有限的,最多能表示2^128个数据,而我们要哈希的数据是无穷的.
没有绝对安全的加密.越复杂越安全的加密算法,需要计算的时间就越长
唯一标识
例如要在海量图库中,搜索一张图片是否存在,我们不能单纯的图片元信息(比如图片名称)来对比,因为图片名称和图片往往是不相符的.那该如何搜索呢?
比较笨的方法是,用二进制串码一一对比,但是这样比对起来非常耗时.
我们可以给每一张图片取一个唯一标识或者说信息摘要.比如,可以从图片的二进制码串开头曲100个字节,中间取100个字节,从最后再取100个字节,然后将这300个字节放在一起通过哈希算法,得到一个哈希字符串,用它做图片的唯一标识.通过这个唯一标识来判定图片是否存在.
数据校验
BT下载的原理是基于P2P协议的.我们从多个机器上并行下载一个2G电影,这个电影会被分成很多文件块.等所有文件块下载完成后再组装成一个完整的电影.
但是在下载中,文件块可能下载不全或者被恶意修改.这个时候就需要数据验证.
我们通过哈希算法,对多个文件块分别取哈希值,并保存在种子文件中.当下载完成后,再通过相同的哈希算法,对下载好的文件逐一求哈希值,然后再跟种子文件中的哈希值比较.
散列函数
散列函数实际上也是哈希算法的一种.散列函数是设计一个散列表的关键,它直接决定了散列冲突的概率和散列表的性能.不过,相对哈希算法的其他的应用,散列函数对散列冲突的要求要低很多.即便出现散列冲突,只要不是严重,也可以用开放寻址法活链表法解决.
不仅如此,散列函数对于散列算法计算得到的值,是否能反向解密也并不关心.散列函数中的散列算法,更加关注散列后的值是否平均分布.散列函数的执行快慢,也会影响到散列函数的性能.所以散列函数的散列算法一般都比较简单,比较追求效率.
负载均衡
负载均衡的算法有很多,比如轮训,随机,加权轮询等.
假如实现一个会话粘滞的负载均衡算法.最直接的方式就是维护一张映射表,这张表的内容是客户端IP地址与服务器编号的映射关系.但是存在如下几个弊端.
- 如果客户端很多,映射表可能会很大,比较浪费内存空间
- 客户端下线,上线,服务器扩容,缩容都会导致映射失效,这样维护映射表的成本就会很大.
借助哈希算法可以解决这个问题.通过哈希算法,对客户端ip地址计算哈希值,将取的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器.
数据分片
如何统计关键词出现的次数
假如有1T的日志文件,记录了用户搜索的关键词,如何快速统计出每个关键词的个数?
我们可以先对数据分片,然后采用多台机器处理的方法,来提高处理速度.我们从搜索记录的日志文件中依次读出每个搜索关键词,并通过哈希函数计算哈希值,然后再跟n取模,得到应该被分配的机器编号.
如何快速判断图片是否在图库中
假设现在有1亿图片,此时在单台机器上构建散列表示行不通的.我们同样可以对数据进行分片,然后采用多机处理.准备n台机器,让每台机器维护某一部分图片对应的散列表.每次从图库中读取一个图片,计算唯一标识,然后与机器数n求余取模,得到的值就是对应的机器编号,然后将这个图片的唯一标示和路径发往对应的机器构建散列表.
当判断是否存在的时候,我们用同样的哈希算法,计算图片的唯一标识,然后与机器个数n求余取模.假设得到的值是k,那就去编号为k的机器中查找.
估算这1亿图片构建散列表需要多少台机器.
散列表中每个数据单元包含两个基本信息,哈希值和图片路径.假设通过MD5来计算哈希值,那长度是128bit也就是16字节.文件路径长度上线是256接,假设平均是128字节.如果用链表发来解决冲突,那还需要存储指针指针占用8字节,所以散列表中每个数据单元占用152字节.
假设一台机器2G内存,散列表装载因子0.75,那一台机器可以给大约1000万(2GB * 0.75 / 152)张图片构建散列表,所以1亿张大概需要十几台机器.
分布式存储
面对海量数据.为了提高读写,写入能力一般都采用分布式方式存储数据,比如分布式缓存.我们利用分片思想,通过哈希算法取哈希值,然后对机器个数取模,找到对应的机器编号.
但是,随着数据增多,原来的10个机器已经无法承受,需要扩容.这时候就变麻烦了.因为并不是增加一台机器这么简单.
假如原来的数据是对10取模的,比如13这个数据原先取模后存在3号服务器上.现在增加了一台机器,对11取模,这个数据就被分配到了2号服务器.因此所有数据都需要重新计算哈希值,然后重新搬移到对应的机器上.此时所有的缓存都失效了.
我们需要一种方法,加新机器后并不需要大量数据搬移.这时候就需要一致性哈希算法.
假设有k个机器,数据的哈希值范围是[0,max].我们将整个范围划分成m个小区间(m远大于k),每个机器复杂