哈希算法

哈希算法：
将任意长度的二进制串，映射为固定长度的二进制值串，这个映射的规则就是哈希算法。

哈希算法作用：
1、唯一标识，哈希算法可以对大数据做信息摘要，通过一个较短的二进制编码来表示很大的数据
2、应用是用于校验数据的完整性和正确性
3、应用安全加密。
4、应用散列函数。

5、负载均衡
实现一个会话粘滞的负载均衡算法？
最直接的算法就是维护一张映射关系表，这张表的内容是客户端IP地址或者会话IS与
服务器编号的映射关系。客户端发出的每次请求，都要先在映射表中查找应该路由
到的服务器编号，然后再请求编号对应的服务器。这种方法简单，直观。但
如果客户端很多，映射表可能会很大，比较浪费内存空间。
客户端下线、上线，服务器扩容、缩荣都会导致映射表失效，这样维护映射表的成本就很大

我们可以通过哈希算法，对客户端的IP地址或者会话ID 计算哈希值，将取得的哈希值与服务器
列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。

6、数据分片
假如我们有 1T 的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？
我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。具体的思路是这样的：为了提高处理的速度，我们用 n 台机器并行处理。我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希函数计算哈希值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。这样，哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说，同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数，最后合并起来就是最终的结果。
7、分布式存储
现在互联网面对的都是海量的数据、海量的用户。我们为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据，比如分布式缓存。我们有海量的数据需要缓存，所以一个缓存机器肯定是不够的。于是，我们就需要将数据分布在多台机器上。该如何决定将哪个数据放到哪个机器上呢？我们可以借用前面数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。
但是，如果数据增多，原来的 10 个机器已经无法承受了，我们就需要扩容了，比如扩到 11 个机器，这时候麻烦就来了。因为，这里并不是简单地加个机器就可以了。原来的数据是通过与 10 来取模的。比如 13 这个数据，存储在编号为 3 这台机器上。但是新加了一台机器中，我们对数据按照 11 取模，原来 13 这个数据就被分配到 2 号这台机器上了。
因此，所有的数据都要重新计算哈希值，然后重新搬移到正确的机器上。这样就相当于，缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存，直接去请求数据库。这样就可能发生雪崩效应，压垮数据库。所以，我们需要一种方法，使得在新加入一个机器后，并不需要做大量的数据搬移。这时候，一致性哈希算法就要登场了。
假设我们有 k 个机器，数据的哈希值的范围是 [0, MAX]。我们将整个范围划分成 m 个小区间（m 远大于 k），每个机器负责 m/k 个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。一致性哈希算法的基本思想就是这么简单。除此之外，它还会借助一个虚拟的环和虚拟结点，更加优美地实现出来。这里我就不展开讲了，如果感兴趣，你可以看下这个

对称加密算法（AES，DES）或者是非对称加密（RSA，ECC）