共计 6392 个字符，预计需要花费 16 分钟才能阅读完成。
前置问题
- MD5 算法会不会抵触？概率是多大？
- redis 的分布式缓存是如何做到的？
- nginx 的负载平衡有哪些实现形式？
蝉的哲学
蝉有好多种，有的 3 年期出土，有的 5 年期出土，本文更多探讨的是 13 年和 17 年出土的超长周期蝉。
周期蝉是蝉科周期蝉属（Magicicada）下 7 种蝉的统称，其中有 3 种是 17 年蝉，4 种是 13 年蝉。它们只生存在北美东部，其中 13 年蝉次要散布在美国东南部，17 年蝉次要散布在美国东北部及加拿大局部地区。
这 7 种蝉之所以被称为“周期蝉”，是因为 它们会遵循某个周期集中呈现。咱们以 2016 年为例，2016 年，有一种 17 年蝉将会在马里兰州呈现，而在 2016 年之后的 16 年里，马里兰州再也不会呈现这种周期蝉，直到 2033 年，马里兰州才会再次出现这批周期蝉的后辈。
乏味的事件发现了，咱们发现，不论蝉的生命周期长或者是短，它们都是质数。也就是说，它和任何一个数的最大公因数是 1
为什么？
依据《费马大定理》里提到的，有一种实践假如蝉有一种生命周期也较长的天敌，蝉要设法避开这种天敌。如果这种天敌的生命周期比方说是 2 年，那么蝉就要避开能被 2 整除的生命周期，否则天敌和蝉就会定期相遇。相似地，如果天敌的生命周期是 3 年，那么蝉要避开能被 3 整除的生命周期，否则天敌和蝉又会定期相遇。所以最终为了防止遇到它的天敌，蝉的最佳策略是使它的生命周期的年数缩短为一个质数。因为没有数能整除 17，十七年蝉将很难得遇上它的天敌。如果天敌的生命周期为 2 年，那么它们每隔 34 年才遇上一次；假使天敌的生命周期更长一些，比方说 16 年，那么它们每隔 272（16×17）年才遇上一次。
为了还击，天敌只有抉择两种生命周期能够减少相遇的频率——1 年期的生命周期以及与蝉同样的 17 年期的生命周期。然而，天敌不可能活着接连从新呈现达 17 年之久，因为在前 16 次呈现时没有蝉供它们寄生。另一方面，为了达到为期 17 年的生命周期，一代代的天敌在 16 年的生命周期中首先必须失去进化，这意味着在进化的某个阶段，天敌和蝉会有 272 年之久不相遇！无论哪一种情景，蝉的漫长的、年数为质数的生命周期都爱护了它。
这或者解释了为什么这种假如的天敌从未被发现！在为了跟上蝉而进行的赛跑中，天敌很可能一直缩短它的生命周期直至达到 16 年这个难关。而后它将有 272 年的工夫遇不到蝉，而在此之前，因为无奈与蝉相遇它已被赶上了死路。剩下的是生命周期为 17 年的蝉，其实它已不再须要这么长的生命周期了，因为它的天敌已不复存在。
那么这个蝉，和咱们明天要说的哈希有啥关系呢？
哈希(hashing)
哈希这个概念，对于前端来说，其实不是很容易了解，为什么，因为咱们时时刻刻都在用这个货色，这个对咱们来说，就是天经地义的。
那么抛开这些，假如咱们不是一个前端，咱们来看。
假如咱们要给一个公司的工号做一个工号本，能够依据工号找到这个工号是谁。
思考到这个公司不大，不可能呈现十万人。假如工号的格局是 xXXXX，99999 是最大工号。因为公司的流动性，尽管只有 100 人，然而工号也曾经上万了。
那么咱们能够间接把对应的人的信息，存到数组里。这样拜访这个号码的时候，就是 O(1)的工夫复杂度。
var arr = new Array(99999);
arr[num] = info;空间 = O(9999)
利用的效率 = 100/99999 = 千分之一。
那利用率是不是太低了？
那咱们就须要设计一种货色，能够进步它的利用率，那这个就是哈希表
哈希表
哈希表，又称散列表，英文名为 Hash Table。本质上是一种对 数组进行了扩大的数据结构 ，能够说哈希表是在数组反对下标间接索引数据(value) 的根底上进行优化并尽可能在常数工夫内对数据进行增、删、改、查等操作。
也就是说，人数 100 人，假如我提供一个容量为 199 的哈希表，我只须要把工号，通过某个形式，转换为 200 以内的数字，最终同样把所有人的信息，存储进来，那么是不是这样的效率会更高呢？效率就是 100/199 ~= 1/2，远远大于千分之一。这也是装载因子的定义
而这个形式，也就是所设计进去的函数，就叫 哈希函数
哈希函数
比方 MD5 算法，就是一个比拟常见的哈希函数，它的原理都是公开的，有趣味能够去查查。
它就是把任意长度的字符串，转化为一个 128 位的 2 进制数，也就是 32 位的 16 进制数。
而像上述的这个工号转换的哈希函数，很简略。
function hashNumber(num) {return num % 199;}假如我须要存储工号 1999 的员工的信息
const key = hashNumber(1999);
arr[key] = {name: '张三', phone: 18888 ,sex: '男'};那么假如有个共事的工号是 2198，后果发现通过这个算法生成的 key 也是 9，这就造成了抵触。
而要想设计一个优良的哈希算法并不容易，个别状况下，它须要满足的几点要求：
- 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
- 对输出数据十分敏感，哪怕原始数据只批改了一个 Bit，最初失去的哈希值也大不相同；
- 哈希抵触的概率要很小，对于不同的原始数据，哈希值雷同的概率十分小；
- 哈希算法的执行效率要尽量高效，针对较长的文本，也能疾速地计算出哈希值。
这些定义和要求都比拟实践，可能还是不好了解，我拿 MD5 这种哈希算法来具体阐明一下。
咱们别离对“优良的哈希算法不是我能写进去的”和“aklgod”这两个文本，计算 MD5 哈希值，失去两串看起来毫无法则的字符串。能够看进去，无论要哈希的文本有多长、多短，通过 MD5 哈希之后，失去的哈希值的长度都是雷同的，而且失去的哈希值看起来像一堆随机数，齐全没有法则。
MD5("优良的哈希算法不是我能写进去的") = 15215cac3a04b7735eadd30b2c384420
MD5("aklgod") = 0135ae01cc770c5b6c46c788a46106ca咱们再来看两个十分类似的文本，“每天都想一夜暴富”和“每天都想一夜暴富！”。这两个文本只有一个感叹号的区别。如果用 MD5 哈希算法别离计算它们的哈希值，你会发现，只管只有一字之差，失去的哈希值也是齐全不同的。
MD5("每天都想一夜暴富") = fc63ff05adebc9f02a5fdf101c571db5
MD5("每天都想一夜暴富！") = 2b9647855f3879e0cff8d4ea2dd8c92b后面也说了，通过哈希算法失去的哈希值，很难反向推导出原始数据。比方下面的例子中，咱们就很难通过哈希值 “2b9647855f3879e0cff8d4ea2dd8c92b” 反推出对应的文本“每天都想一夜暴富！”。
哈希算法要解决的文本可能是各种各样的。比方，对于十分长的文本，如果哈希算法的计算工夫很长，那就只能停留在实践钻研的层面，很难利用到理论的软件开发中。比方，咱们把明天这篇文章，用 MD5 计算哈希值，用不了 1ms 的工夫。
哈希抵触
有些论断看似没有情理，比方“一个班级里必定有两个人生日在同一个月份”、“世界上必定有两个人头发数一样多”等等，然而认真一想还真是对的。
人类的头发依据种族和发色的不同，数量略有不同，最多在 12 万根左右；目前世界上的总人口超过了 74 亿；
再举一个例子，当初有十只鸽子但只有九个笼子，那么必然有一个笼子里至多有两只鸽子。因为九个鸽子先各占一个笼子，那么第十只就只能和其余鸽子挤挤了。
而上述看似显然的一个论断就是“鸽笼原理”(The Pigeonhole Principle)，也叫“抽屉原理”。
那么我刚刚设计的一个工号，它的抵触的概率就是 199 分之 1。概率还是很高的，而 MD5 算法呢，它是 128 位的 2 进制数，也就说抵触的概率在 2^128 分之 1，这是一个难以想象的概率，那么对于一个才百分级的图库，大可不必放心应用 MD5 算法，而比特币这样的，就用了更厉害的 SHA256 算法。
抵触的解决方案
目前来说，哈希抵触的解决办法有两大类 ` 链表寻址法(Linking Addressing)` 和 ` 凋谢寻址法（Opening Addressing）`。- 凋谢寻址法
凋谢寻址法思维比较简单：如果呈现一个 key2 进行 hash(key)后映射的地位与 key1 进行 hash(key)后映射的地位统一（即产生了哈希抵触），那么从该地位往下寻找到第一个空位时将 key2 的数据放入。而从该地位往下寻找闲暇地位的过程又称为探测。
疏忽，不是很重要。 - 链表寻址法
啥意思呢？就是我存储数据的时候，应用链表的形式。当抵触数据进来的时候，采纳头插或尾插的形式，把抵触数据插入到对应的地位即可。
举个例子
```
1999 这个工号的人，地位是 arr[9] = {xxx}
后果我插入 2198 的时候，发现还是 9，抵触了，采纳头插法就是
let temp = arr[9].next;
arr[9].next = 2198 的 info。2198info.next = temp;
采纳尾插法，就是
let head = arr[9];
let next = head.next
// 假如尾插的时候曾经有 2 个以上了，我不判断了。while(next.next) {next = next.next;}
next.next = 2198info。``` 在 java8 以前应用的是头插法，java8 之后改为了尾部插入，有趣味的能够去查查为什么
疑难
上述说了半天，其实能够发现，我最开始为啥不必对象呢？
间接
var obj = {};
obj[工号] = info这样不就完结了吗？
是的
js 中的对象，实质上来说，就是服务端后盾外挂版本的 HashMap
而 js 中的对象或数组，其实就曾经是一个优质的散列表了。
这是成品的利用，而哈希函数的思维，还是十分值得去思考的。
利用
- 平安加密
相似 MD5,SHA 都是属于平安加密的利用。它们都没有独自的说去解决这个抵触。
如果咱们拿到一个 MD5 哈希值，心愿通过毫无法则的穷举的办法，找到跟这个 MD5 值雷同的另一个数据，那消耗的工夫应该是个天文数字。所以，即使哈希算法存在抵触，然而在无限的工夫和资源下，哈希算法还是被很难破解的。
比方
d131dd02c5e6eec4693d9a0698aff95c
2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a
085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6
dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e
c69821bcb6a8839396f9652b6ff72a70
d131dd02c5e6eec4693d9a0698aff95c
2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a
085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6
dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1e
c69821bcb6a8839396f965ab6ff72a70
这两段进去的是一个 MD5 79054025255fb1a26e4bc422aef54eb4
然而，能够通过蛮力的形式，比方罕用的生日，罕用的 123456，12345678。这样的明码的 MD5 值，存起来，那就晓得它是谁了。
所以须要有加盐的这样的操作。
就是 123456 这样的明码，比方你固定在第三位开始，加一个 niubi。这样的。他人就很难破解了。
- 惟一标识
比方咱们的图片，它最初进去的 tfskey，那就是一个 hash 算法后的 key，保障了图片的唯一性。能够间接通过这个 key，拜访到对应的图片
比如说咱们在发送接口申请的时候，会带一个_sg，就是 sign，给服务端，服务端通过验证这个签，就能够判断咱们是不是那个对的人。
以上，都通过了各种算法，把宏大的图片信息，用户信息，变成了简短的一个 key，来达到目标。
- 数据校验
利用哈希算法对输出数据敏感的特点，能够对数据取哈希值，从而高效校验数据是否被篡改过。比方你再下载文件的时候，文件很大，须要分成很多个数据块，而后都下载完了后，再组装起来，然而一旦两头下载出错了，怎么办呢？能够对分块的文件取 hash 值，这样下载完一块后，和种子文件里的根本信息做比照，如果不同，就阐明出错了，须要从新下载。
- 负载平衡
咱们晓得，负载平衡算法有很多，比方轮询、随机、加权轮询等。那如何能力实现一个会话粘滞 （session sticky） 的负载平衡算法呢？也就是说，咱们须要在同一个客户端上，在一次会话中的所有申请都路由到同一个服务器上。
最间接的办法就是，保护一张映射关系表，这张表的内容是客户端 IP 地址或者会话 ID 与服务器编号的映射关系。客户端收回的每次申请，都要先在映射表中查找应该路由到的服务器编号，而后再申请编号对应的服务器。这种办法简略直观，但也有几个弊病：
如果客户端很多，映射表可能会很大，比拟节约内存空间；
客户端下线、上线，服务器扩容、缩容都会导致映射生效，这样保护映射表的老本就会很大；
如果借助哈希算法，这些问题都能够十分完满地解决。咱们能够通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将获得的哈希值与服务器列表的大小进行取模运算，最终失去的值就是应该被路由到的服务器编号。这样，咱们就能够把同一个 IP 过去的所有申请，都路由到同一个后端服务器上。
这其实也是 nginx 负载平衡中的一个算法。
- 分布式存储
就以分布式缓存为例吧，咱们每天承受海量的数据，须要缓存，并不想让他们去频繁的拜访数据库，因为到了我的数据库，就须要 I / O 了，而缓存是在我的内存中的，谁更快大家都懂把。
然而一个缓存机器必定是不够的。于是，咱们就须要将数据分布在多台机器上。
该如何决定将哪个数据放到哪个机器上呢？咱们能够通过哈希算法对数据取哈希值，而后对机器个数取模，这个最终值就是应该存储的缓存机器编号。
然而，如果数据增多，原来的 10 个机器曾经无奈接受了，咱们就须要扩容了，比方扩到 11 个机器，这时候麻烦就来了。因为，这里并不是简略地加个机器就能够了。
原来的数据是通过与 10 来取模的。比方 13 这个数据，存储在编号为 3 这台机器上。然而新加了一台机器中，咱们对数据依照 11 取模，原来 13 这个数据就被调配到 2 号这台机器上了。
因而，所有的数据都要从新计算哈希值，而后从新搬移到正确的机器上。这样就相当于，缓存中的数据一下子就都生效了。所有的数据申请都会穿透缓存，间接去申请数据库。这样就可能产生 雪崩效应，压垮数据库。
这里，就会说到一致性哈希了。
一致性哈希
统一哈希 是一种非凡的哈希算法。在应用统一哈希算法后，哈希表槽位数（大小）的扭转均匀只须要对 K/n 个关键字从新映射，其中 K 是关键字的数量，n 是槽位数量。然而在传统的哈希表中，增加或删除一个槽位的简直须要对所有关键字进行从新映射。
Redis Cluster 就是相似于一致性哈希的原理。
例子
1. 两数之和
2. 购物车，咱们晓得，购物车里的数据，是服务端吐的数组汇合，然而购物车须要频繁的去勾选，去反选，去删除，去加减数量。
那么找到这个数据，就须要 find，频繁的去 find 到对应的 sku，而咱们的 sku，通常又会藏在 store 的上面，spu 的上面。这样对于查找的工夫，就会偏长。
那么如果通过本节所学，创立一个前端 hash 表，把 sku 的 id 作为 key，是不是空间换工夫的完满策略，这样我再找到选中的那个人的时候，O(1)的工夫就能够找到了。
后续
后续可能要讲讲均衡二叉树系列，更好的去了解链表这样的数据结构，对前端自身也是一种进步。
