散列算法、哈希算法，分别为Hash的意译与直译。指的是一个东西。本文主要记录下围绕Hash算法的一些知识点

Hash算法要满足的要求

Hash算法的应用场景

说到哈希算法的应用，最先想到的应该就是安全加密。最常用于加密的哈希算法是

对用于加密的哈希算法来说，有两点格外重要。

除此之外，没有绝对安全的加密。越复杂、越难破解的加密算法，需要的计算时间也越长。比如SHA-256比SHA-1要更复杂、更安全，相应的计算时间就会比较长。密码学界也一直致力于找到一种快速并且很难被破解的哈希算法。我们在实际的开发过程中，也需要权衡破解难度和计算时间，来决定究竟使用哪种加密算法。

在计算机中任何文件都可以标示成二进制码串，当海量大文件进行存储的时候，就可以利用存储路径、文件内容截取部分位置，通过Hash算法获取一个近似唯一的标识来进行存储。

常见的BT下载中，由于是基于P2P协议进行的分块下载，而网络传输是不安全的，可能会出现文件块被恶意修改等问题，导致最终文件合并出错。

我们通过哈希算法，对100个文件块分别取哈希值，并且保存在种子文件中。哈希算法有一个特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。

所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。

散列函数也是Hash算法的一种。散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过，相对哈希算法的其他应用，散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突，只要不是过于严重，我们都可以通过开放寻址法或者链表法解决。

不仅如此，散列函数对于散列算法计算得到的值，是否能反向解密也并不关心。散列函数中用到的散列算法，更加关注散列后的值是否能平均分布，也就是，一组数据是否能均匀地散列在各个槽中。除此之外，散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。

在负载均衡应用中，利用哈希算法替代映射表，可以实现一个会话粘滞的负载均衡策略。

可以通过哈希算法，对客户端IP地址或者会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。这样就可以把同一个IP过来的所有请求，都路由到同一个后端服务器上。

可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。具体的思路是这样的:

提高处理的速度，我们用n台机器并行处理。

从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟n取模，最终得到的值，就是应该被分配到的机器编号。

哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。

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

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

该如何决定将哪个数据放到哪个机器上，我们可以借用前面数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。

分布式存储中提到的例子，数据增加后原来的机器数量已经无法承受，需要进行扩容，但是原本的哈希算法是基于原机器数量进行取模得到的，这时候可能会出现查找不到的情况。就需要进行rehash。但是如果是海量数据，效率会非常低。

所以这时候就需要一种方法，使得在新加入一个机器后，并不需要做大量的数据搬移。

实际上，一致性哈希算法的应用非常广泛，在很多分布式存储系统中，都可以见到一致性哈希算法的影子。

参考该文章，讲的非常全面。https://zhuanlan.zhihu.com/p/78285304

假设我们有k个机器，数据的哈希值的范围是[0, MAX]。将整个范围划分成m个小区间(m远大于k)，每个机器负责m/k个小区间。当有新机器加入的时候，就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。

通过环的方式进行表示会比较直观。在少量节点时，通过虚拟节点保证数据均衡性。