哈希算法
# 哈希算法基础
定义
将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。
算法要求
- 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）
- 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同
- 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小
- 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值
# 应用
安全加密
MD5,SHA,DES,AES
前面哈希算法四点要求，对用于加密的哈希算法来说，有两点格外重要。第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要很小。
第一点
第一点很好理解，加密的目的就是防止原始数据泄露，所以很难通过哈希值反向推导原始数据，这是一个最基本的要求。
第二点
**不管是什么哈希算法，我们只能尽量减少碰撞冲突的概率，理论上是没办法做到完全不冲突的。**为什么这么说呢。
这里就基于组合数学中一个非常基础的理论，鸽巢原理（也叫抽屉原理）。这个原理本身很简单，它是说，如果有 10 个鸽巢，有 11 只鸽子，那肯定有 1 个鸽巢中的鸽子数量多于 1 个，换句话说就是，肯定有 2 只鸽子在 1 个鸽巢内。
比如前面举的 MD5 的例子，哈希值是固定的 128 位二进制串，能表示的数据是有限的，最多能表示 2^128 个数据，而我们要哈希的数据是无穷的。如果我们对 2^128+1 个数据求哈希值，就必然会存在哈希值相同的情况。
一般情况下，哈希值越长的哈希算法，散列冲突的概率越低。
唯一标识
如果要在海量的图库中，怎样搜索一张图是否存在？
我们不能单纯地用图片的元信息（比如图片名称）来比对，因为有可能存在名称相同但图片内容不同，或者名称不同图片内容相同的情况。
我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。
我们可以把每个图片的唯一标识，和相应的图片文件在图库中的路径信息，都存储在散列表中。当要查看某个图片是不是在图库中的时候，我们先通过哈希算法对这个图片取唯一标识，然后在散列表中查找是否存在这个唯一标识。
如果不存在，那就说明这个图片不在图库中；如果存在，我们再通过散列表中存储的文件路径，获取到这个已经存在的图片，跟现在要插入的图片做全量的比对，看是否完全一样。如果一样，就说明已经存在；如果不一样，说明两张图片尽管唯一标识相同，但是并不是相同的图片。
数据校验
并行下载
我们从多个机器上并行下载一个 2GB 的电影，这个电影文件可能会被分割成很多文件块（比如可以分成 100 块，每块大约 20MB）。等所有的文件块都下载完成之后，再组装成一个完整的电影文件就行了。
校验
我们通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中。我们在前面讲过，哈希算法有一个特点，对数据很敏感。只要文件块的内容有一丁点儿的改变，最后计算出的哈希值就会完全不同。
所以，当文件块下载完成之后，我们可以通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。
散列函数
散列函数中用到的散列算法，对于散列算法冲突的要求要低很多,是否能反向解密也并不关心,更加关注散列后的值是否能平均分布，也就是，一组数据是否能均匀地散列在各个槽中。除此之外，散列函数执行的快慢，也会影响散列表的性能，所以，散列函数用的散列算法一般都比较简单，比较追求效率。
负载均衡
如何才能实现一个会话粘滞（session sticky）的负载均衡算法呢？
也就是说，我们需要在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。
方法
我们可以通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。 这样，我们就可以把同一个 IP 过来的所有请求，都路由到同一个后端服务器上。
数据分片
==针对这种海量数据的处理问题，我们都可以采用多机分布式处理。借助这种分片的思路，可以突破单机内存、CPU 等资源的限制。==
如何统计“搜索关键词”出现的次数？
假如我们有 1T 的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？
我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。
每个机器负责一片数据，所有机器并行处理。
从日志文件中，取出一个关键词，然后通过哈希函数计算哈希值，然后跟n取模，最终得到的值就是该关键词被分配到的机器编号。
然后将该关键词分配到对应机器编号上。相当于每个机器同时做两件事，一个是遍历分片的数据，将关键词分配到不同的机器上；另外同时接收从其他机器上传来的关键词。
当遍历完所有数据后，哈希值相同的搜索关键词就被分配到了同一个机器上。在没有冲突的情况下，也就是说，同一个搜索关键词会被分配到同一个机器上。
每个机器会分别计算它拥有的关键词出现的次数，最后合并起来就是最终的结果。
这里的处理过程也是 MapReduce 的基本设计思想。
如何快速判断图片是否在图库中？
假设现在我们的图库中有 1 亿张图片，很显然，在单台机器上构建散列表是行不通的,因为单台机器的内存有限，而 1 亿张图片构建散列表显然远远超过了单台机器的内存上限。
构建散列表
我们同样可以对数据进行分片，然后采用多机处理。我们准备 n 台机器，让每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片，计算唯一标识，然后与机器个数 n 求余取模，得到的值就对应要分配的机器编号，然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。
查询是否存在
当我们要判断一个图片是否在图库中的时候，我们通过同样的哈希算法，计算这个图片的唯一标识，然后与机器个数 n 求余取模。假设得到的值是 k，那就去编号 k 的机器构建的散列表中查找。
分布式存储
我们为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据，比如分布式缓存。
一般哈希
我们可以借用前面数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。
当需要扩容时，所有的数据都要重新计算缓存机器编号。
这样就相当于，缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存，直接去请求数据库。这样就可能发生雪崩效应，压垮数据库。
-
我们需要一种方法，使得在新加入一个机器后，并不需要做大量的数据搬移——一致性哈希
一致性哈希映射
不同于普通哈希，是通过求余的方式来映射的。
一致性哈希映射是==环形、顺时针、就近==映射
整个环，相当于全部的缓存空间，环形空间总被被分为**2^32^**个缓存区。（这里的32是哈希值的二进制位数）
key值通过某种hash算法转换为一个32位的二进制数
每一个缓存结点node(相当于之前提到的缓存机器编号)，用同样的算法，映射到环形空间。
==归属原则==
每一个key顺时针方向最近的node就是key所归属的存储结点
增加结点
当缓存集群的节点有所增加的时候，整个环形空间的映射仍然会保持一致性哈希的顺时针规则，所以有一小部分key的归属会受到影响。
原先只有结点1,2,3----现在增加结点4
影响
原本归属node2的key2，现在需要归属node4
受影响的键只有key2，其他键不受影响
删除结点
当缓存集群的节点需要删除的时候（比如节点挂掉），整个环形空间的映射同样会保持一致性哈希的顺时针规则，同样有一小部分key的归属会受到影响。
现在假设，结点3挂掉了
影响
只有key4受到影响，现在要归属于node1
虚拟结点
当缓存在环形空间中分布不均匀时，可以引入虚拟结点。
设 原来 只有node1，和node2，分布相当不均匀。现引入，node1-1，node1-2；和node2-1，node2-2.
由于虚拟结点数量较多，缓存key与虚拟结点之间的映射关系也变得相对平衡了。
# 问题思考
你会如何存储用户密码这么重要的数据吗？（MD5+salt）
字典攻击
如果用户信息被“脱库”，黑客虽然拿到是加密之后的密文，但可以通过“猜”的方式来破解密码，这是因为，有些用户的密码太简单。比如很多人习惯用 00000、123456 这样的简单数字组合做密码，很容易就被猜中。
那我们就需要维护一个常用密码的字典表，把字典中的每个密码用哈希算法计算哈希值，然后拿哈希值跟脱库后的密文比对。如果相同，基本上就可以认为，这个加密之后的密码对应的明文就是字典中的这个密码。
加盐(salt)
针对字典攻击，我们可以引入一个盐（salt），跟用户的密码组合在一起，增加密码的复杂度。我们拿组合之后的字符串来做哈希算法加密，将它存储到数据库中，进一步增加破解的难度。
不过我这里想多说一句，我认为安全和攻击是一种博弈关系，不存在绝对的安全。所有的安全措施，只是增加攻击的成本而已。
比如原密码是123456，不加盐的情况加密后假设是是xyz。 黑客拿到脱机的数据后，通过彩虹表匹配可以轻松破解常用密码。**如果加盐，密码123456加盐后可能是12ng34qq56zz，再对加盐后的密码进行hash后值就与原密码hash后的值完全不同了。**而且加盐的方式有很多种，可以是在头部加，可以在尾部加，还可在内容中间加，甚至加的盐还可以是随机的。这样即使用户使用的是最常用的密码，黑客拿到密文后破解的难度也很高。
更优秀做法
除了hash+salt，现在大多公司都采用无论密码长度多少，计算字符串hash时间都固定或者足够慢的算法如PBKDF2WithHmacSHA1，来降低硬件计算hash速度，减少不同长度字符串计算hash所需时间不一样而泄漏字符串长度信息，进一步减少风险。
区块链
区块链是一块块区块组成的，每个区块分为两部分：区块头和区块体。
区块头保存着 自己区块体 和 上一个区块头 的哈希值。
因为这种链式关系和哈希值的唯一性，只要区块链上任意一个区块被修改过，后面所有区块保存的哈希值就不对了。
区块链使用的是 SHA256 哈希算法，计算哈希值非常耗时，如果要篡改一个区块，就必须重新计算该区块后面所有的区块的哈希值，短时间内几乎不可能做到。
