vlambda博客
学习文章列表

说到哈希算法的应用，最先想到的应该就是安全加密。最常用于加密的哈希算法是MD5(MD5 Message-Digest Algorithm，MD5消息摘要算法)和SHA(Secure Hash Algorithm，安全散列算法)。除了这两个之外，当然还有很多其他加密算法，比如DES(Data Encryption Standard，数据加密标准)、AES(Advanced Encryption Standard，高级加密标准)。

前面我讲到的哈希算法四点要求，对用于加密的哈希算法来说，有两点格外重要。第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要很小。第一点很好理解，加密的目的就是防止原始数据泄露，所以很难通过哈希值反向推导原始数据，这是一个最基本的要求。所以我着重讲一下第二点。实际上，不管是什么哈希算法，我们只能尽量减少碰撞冲突的概率，理论上是没办法做到完全不冲突的。为什么这么说呢?

这里就基于组合数学中一个非常基础的理论，鸽巢原理(也叫抽屉原理)。这个原理本身很简单，它是说，如果有10个鸽巢，有11只鸽子，那肯定有1个鸽巢 中的鸽子数量多于1个，换句话说就是，肯定有2只鸽子在1个鸽巢内。有了鸽巢原理的铺垫之后，我们再来看，为什么哈希算法无法做到零冲突?我们知道，哈希算法产生的哈希值的长度是固定且有限的。比如前面举的MD5的例子，哈希值是固定的128位二进制串，能表示的数据是有限的，最多能表 示2^128个数据，而我们要哈希的数据是无穷的。基于鸽巢原理，如果我们对2^128+1个数据求哈希值，就必然会存在哈希值相同的情况。这里你应该能想 到，一般情况下，哈希值越长的哈希算法，散列冲突的概率越低。

我先来举一个例子。如果要在海量的图库中，搜索一张图是否存在，我们不能单纯地用图片的元信息(比如图片名称)来比对，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的情况。那我们该如何搜索呢?我们知道，任何文件在计算中都可以表示成二进制码串，所以，比较笨的办法就是，拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对。如果相同，则说明图片在图库中存在。但是，每个图片小则几十KB、大则几MB，转化成二进制是一个非常长的串，比对起来非常耗时。有没有比较快
的方法呢?

我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取100个字节，从中间取100个字节，从最后再取100个字 节，然后将这300个字节放到一块，通过哈希算法(比如MD5)，得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库 中，这样就可以减少很多工作量。如果还想继续提高效率，我们可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。当要查看某个图片是不是在图库中的时候，我们先通过哈希算法对这个图片取唯一标识，然后在散列表中查找是否存在这个唯一标识。如果不存在，那就说明这个图片不在图库中;如果存在，我们再通过散列表中存储的文件路径，获取到这个已经存在的图片，跟现在要插入的图片做全量的比对，看是否完全一样。如果一样，就说明已经存在;如果不一样，说明两张图片尽管唯一标识相同，但是并不是相同的图片。

电驴这样的BT下载软件你肯定用过吧?我们知道，BT下载的原理是基于P2P协议的。我们从多个机器上并行下载一个2GB的电影，这个电影文件可能会被分割成很多文件块(比如可以分成100块，每块大约20MB)。等所有的文件块都下载完成之后，再组装成一个完整的电影文件就行了。我们知道，网络传输是不安全的，下载的文件块有可能是被宿主机器恶意修改过的，又或者下载过程中出现了错误，所以下载的文件块可能不是完整的。如果我们没有能力检测这种恶意修改或者文件下载出错，就会导致最终合并后的电影无法观看，甚至导致电脑中毒。现在的问题是，如何来校验文件块的安全、正确、完整呢?具体的BT协议很复杂，校验方法也有很多，我来说其中的一种思路。我们通过哈希算法，对100个文件块分别取哈希值，并且保存在种子文件中。我们在前面讲过，哈希算法有一个特点，对数据很敏感。只要文件块的内容有一 丁点儿的改变，最后计算出的哈希值就会完全不同。所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后 跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块

HashTable中用到的散列函数，在某种情况下可以使用哈希算法代替散列函数。

前面讲了很多哈希算法的应用，实际上，散列函数也是哈希算法的一种应用。我们前两节讲到，散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过，相对哈希算法的其他应用，散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突，只要不是过于严重，我们都可以通过开放寻址法或者链表法解决。不仅如此，散列函数对于散列算法计算得到的值，是否能反向解密也并不关心。散列函数中用到的散列算法，更加关注散列后的值是否能平均分布，也就是，一组数据是否能均匀地散列在各个槽中。除此之外，散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。

1、如果客户端很多，映射表可能会很大，比较浪费内存空间;

2、客户端下线、上线，服务器扩容、缩容都会导致映射失效，这样维护映射表的成本就会很大; 

1.如何统计“搜索关键词”出现的次数?

假如我们有1T的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢? 我们来分析一下。这个问题有两个难点，第一个是搜索日志很大，没办法放到一台机器的内存中。第二个难点是，如果只用一台机器来处理这么巨大的数据，处理时间会很长。针对这两个难点，我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。具体的思路是这样的:为了提高处理的速度，我们用n台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟n取模，最终得到的值，就是应该被分配到的机器编 号。这样，哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。

实际上，这里的处理过程也是MapReduce的基本设计思想。

现在互联网面对的都是海量的数据、海量的用户。我们为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据，比如分布式缓存。我们有海量的数据需要缓存，所以一个缓存机器肯定是不够的。于是，我们就需要将数据分布在多台机器上。

该如何决定将哪个数据放到哪个机器上呢?我们可以借用前面数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。但是，如果数据增多，原来的10个机器已经无法承受了，我们就需要扩容了，比如扩到11个机器，这时候麻烦就来了。因为，这里并不是简单地加个机器就可以 了。原来的数据是通过与10来取模的。比如13这个数据，存储在编号为3这台机器上。但是新加了一台机器中，我们对数据按照11取模，原来13这个数据就被分配 到2号这台机器上了。