关于前端:从蝉的哲学来看哈希

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 年的蝉，其实它已不再须要这么长的生命周期了，因为它的天敌已不复存在。

那么这个蝉，和咱们明天要说的哈希有啥关系呢？

哈希这个概念，对于前端来说，其实不是很容易了解，为什么，因为咱们时时刻刻都在用这个货色，这个对咱们来说，就是天经地义的。

那么抛开这些，假如咱们不是一个前端，咱们来看。

假如咱们要给一个公司的工号做一个工号本，能够依据工号找到这个工号是谁。
思考到这个公司不大，不可能呈现十万人。假如工号的格局是 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)的工夫就能够找到了。

后续可能要讲讲均衡二叉树系列，更好的去了解链表这样的数据结构，对前端自身也是一种进步。

关于前端:从蝉的哲学来看哈希

前置问题

蝉的哲学

为什么？

哈希(hashing)

哈希表

哈希函数

哈希抵触

抵触的解决方案

疑难

利用

一致性哈希

例子

后续