1）哈希算法：

    将任意长度的二进制串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。要设计一个哈希算法要满足几点要求：

1. 从哈希值不能反向推导出原始数据（所以哈细算法也叫单向哈希算法）；

2. 对输入数据敏感，稍作改变得到的哈希值也大不相同；

3. 散列冲突的概率要小，对不同的原始数据，哈希值相同的概率很小；

4. 效率要尽量高效，针对很长的文本也能快速的计算出哈希值。

2）哈希算法的应用

    1.安全加密：

    最常用的安全加密算法是MD5（消息摘要算法）和SHA（安全散列算法），除了这两个以外还有其他加密算法，比如DES、AES。前面讲的哈希算法的四点要求其实有两点对于安全加密来书尤为重要，不能反向推导和散列冲突概率小，理论上哈希算法无法做到零冲突，比如MD5算法，他的哈希值固定式128个二进制串，也就是最多能表示2^128个数据。所以一旦数据量达到2^128+1，那么就一定会有重复的。但是尽管散列冲突是无法避免的，但是如果拿到一个MD5的哈希值，找到跟这个值相同的另一个数据，那耗费的时间也会是一个天文数字，所以有限时间资源情况下，哈希算法还是很难破解的。

    2.唯一标识：

    如果想要在海量的图库中，搜索一张图是否存在，不能单纯的根据图片的元信息（比如说图片的名称）来进行搜索，因为可能存在名称相同但是图片内容不同的。任何文件在计算中都可以表示成二进制码串，所以比较笨的方法就是拿图片的二进制码串和数据库中的作比较，但是每个图片转换成二进制是一个非常长的串，比对起来非常耗时。

    可以给每一个图片取一个唯一标识，或者说信息摘要，比如说可以取图片的二进制字码串前100，中间100，后100，将这300个字节放在一块通过哈希算法得到一个哈希字符串，作为唯一标识。

    如果想继续提高效率，可以把每个图片的唯一标识和图片的路径都存储在一个散列表中，当要查询某一个图片是否在图库中的时候，可以对这个图片进行哈希算法获得唯一标识，然后在散列表中查找是否存在这个唯一标识。如果不存在，则说明不在图库中，如果存在，则查到这个图片，然后把两张图片进行全量对比，如果相同，则说明存在，如果不相同，则说明两张图片尽管标识相同，但是图片其实是不一样的。

3.数据校验

    要下载一个电影，可能会被分割成很多的文件块，（比如下载一个2GB的电影，被分割成100块，每块大约20MB），等所有的片段都下载完，在组装成一个片段就可以了。网络下载是不安全的，下载后的文件可能会被宿主恶意修改过的，又或者下载过程中出现了错误，导致下载不完整，这样最后合并可能无法观看甚至导致电脑中毒。那么如何校验文件块的安全、正确、完整。

    BT协议很复杂，校验方法也有很多，通过哈希算法校验是其中一种，对100个文件块分别取哈希值，并且保存在种子文件中。从前面来看，哈希算法十分敏感，只要文件块的内容有一丁点改变，最终计算得到的哈希值就会完全不同。当文件块下载完后，对其一一求哈希值然后和种子文件中的哈希值作对比。如果不同，则说明这个文件不完整或者被恶意篡改了。

4.散列函数

    散列函数其实也是哈希算法的一种应用，相对于其他哈希算法的运用，散列函数对于散列冲突的要求其实低得多，只要不是过分严重，都可以通过链表法和开放寻址法来进行解决，而且对于是否能反向推导也不太关切，更加关注的是散列后的值能否平均分布，除此以外，散列函数的执行快慢也会影响散列表的效率，散列函数用的散列算法设计一般比较简单，比较追求效率。

3）区块链的底层实现

    区块链是由一块块区块组成的，每个区块分为两部分，区块头和区块体，区块头上保存着自己的区块体的和上一个区块头的哈希值，这种链式的关系和哈希值的唯一性，只要区块链上任意一个区块被修改过，后面所有区块保存的哈希值就不对了。如果要篡改一个区块，就必须重新计算该区块后面所有的区块的哈希值，短时间内几乎不可能做到。

5.负载均衡

    负载均衡的方法有很多，比如轮询、随机、加权轮询等，如何实现一个会话粘滞的负载均衡算法，也就是在同一个客户端上，在一次会话中所有的请求都路由到同一个服务器上。

    最直接的方法就是维护一张映射关系表，这张表的内容是客户端IP地址或者会话ID与服务器编号的映射关系，客户端每次发出请求，都要先在映射表中查找应该路由到的服务器编号，然后在请求编号对应的服务器。优点：简单直观。缺点：如果客户端很多，映射表可能会很大，比较浪费内存空间；客户端下线，上线，服务器扩容、缩容都会导致映射失效，这样维护映射表的成本就会很大。

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

6.数据分片

举例来说明：

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

    假设有1T的日志文件，记录了用户的搜索关键词，要快速统计出每个关键词被搜索的次数，该怎么做?

    两个难点：一是搜索日志很大，没办法放到一台机器内存，二是如果只用一台机器来处理那么大的数据处理时间会很长。

    针对这两个难点，可以先对数据进行分片，然后采用多台机器处理的方式，来提高处理速度，具体思路是采用n台机器进行并行处理，我们从搜索记录的日志文件中，依次读出每个搜索关键词，并且通过哈希算法对关键词进行计算得到哈希值，然后跟n取模，最终得到的值就是应该被分配到的机器编号，这样相同的关键词就会被分配到同一台机器，每个机器分别计算关键词出现的次数，最后合并起来就是最终的结果。这也是MapReduce的基本设计思想。

2）如何快速判断图片是否在图库中

    现在有1亿张图片，很显然，在单台机器上构建散列表是行不通的，因为单台机器的内存有限，所以前面提到的方法就失效了。

    同样对数据进行分片，然后采用多机处理，准备n台机器，让每台机器只维护一部分图片对应的散列表。每次从图库中读取一个图片，对图片进行唯一标识计算，然后与机器个数n求余取模，假设得到的值为k，那就去编号k的机器构建的散列表中查找。

    估算一下需要多少台机器，散列表每个数据单元包括两个信息，哈希值和图片文件的路径，假设通过MD5来计算哈希值，那长度就是128bit，也就是16字节，文件路径上限是256字节，假设平均长度128字节。如果用链表法来解决散列冲突，每个指针8字节，所以散列表中每个数据单元大概是152字节。假设一台机器内存2GB，散列表因子0.75，那一台机器可以给大约1000万张照片构建散列表，所以需要大概十几台机器。

7.分布式存储

    互联网面对着海量的数据、海量的用户，为了提高数据的读取、写入能力一般采用分布式来存储数据，比如说分布式缓存，需要将海量的缓存存储到多台机器上，那么如何决定将哪个数据放到哪台服务器上，可以根据数据分片思想，即对于数据进行哈希计算取哈希值，然后对机器数量取模，得到的值就是缓存机器编号。

但是！

    如果数据增多，由10台机器扩容到11台机器，这时候麻烦就来了，原来的数据是对10区模的，现在11台机器，所有的数据都需要重新计算哈希值，然后搬移到正确的机器上，这样就相当于，缓存的数据一下子全部失效了，所有的数据请求会穿透缓存，直接访问数据库，这样就是可能会发生雪崩效应，压垮数据库。

    所以，需要一种在加入一个新的机器，并不需要进行大量数据搬移的算法一致性哈希算法，假设有k个机器，数据哈希值范围[0,MAX]。我们将整个范围划分为m个小区间(m远大于k)，每个机器负责m/k个小区间，当有新机器加入时，就把某几个小区间的数据从原来的机器中搬移到新机器。这样既不用全部重新计算哈希、搬移数据，也保持了各个机器上数据量的均衡。（一致性哈希算法可以参考https://www.jianshu.com/p/570dc8913c20）

（本文是个人听课笔记，不少东西摘取于王争老师的原文，原文链接http://gk.link/a/10aMZ）