复习：JavaScript中的数组不是数组，底层是由HashTable和链表实现的……

Hash

一般翻译做散列、杂凑，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。

其实是一类算法的总称。只要能够满足任意长度变固定长度，都算是哈希。

Hash算法（函数）通常要求：

1. 同一散列算法：散列值不同，输入值肯定也不同；
2. 但是，散列值相同，输入值可以不相同。

如果出现上述第2种情况，我们称其为发生了“碰撞”，越好的散列函数，碰撞应该越少。

常用hash算法包括：MD5（后文详述：Java/C#实现）、SHA-2等，他们都说不可逆的，即无法从输出（散列值）逆推得到输入。

@想一想@：hash算法可以用来干嘛？

HashTable

哈希表，又称之为散列表。通常用于存放键值对数据（又被称之为字典Dictionary、映射Map等），比如：

学号是键（key），学生是值（value）：

学号	学生
23	阿泰
14	波仔
87	浪神

姓名是键，年龄是值：

姓名	年龄
阿泰	17
波仔	18
浪神	23

你可能会想象我们用一张专门的表来记录键和地址，然后每一次从上往下遍历这张表找到相应的键值……但等等，只能从上到下遍历么？太慢了，尤其如果键值对的数量比较大的话——干嘛不根据Hash算法通过键直接运算得到值地址呢？！

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

再见数组

实现上面的目标好像并不难：计算机中任何数据都是二进制，也就是一个数值，我们完全可以像存放数组那样，记录待存储键值对的起始位置，把键转换成数组下标，这样不就OK了么？但是，

1. 键值对的数量是不定的，
2. 键所对应的数值有可能是极大的（不要想着我知道最大学号多少呢，如果事先就知道，干嘛不直接用数组呢？）
   

为了便于演示，我们用一种最简单的hash算法：除10取余，^_^（@想一想@：这算不算一种Hash算法？）

通过这种哈希算法，我们：

• 首先确定了数组最大长度是10，所以可以放心的初始化一个长度为10的数组
• 然后，存放数据时，先对键进行散列（运算，比如23=>3，14=>4），
• 于是，将散列值作为数组下标，进行存储（比如比如Students[3]=阿泰，Students[4]=波仔）
• 根据键取值也一样，先将键哈希，然后将哈希值做下标从数组中取值，超快！
  

拉链

@想一想@：现又要存入一个学号为43的学生，应该如何存放？

43/10=4...3，所以散列值为3，和之前的23碰撞了！惨…… （复习，理解为什么：越好的散列函数，碰撞应该越少）

但如果确实发生了这种情况，只有在3的这个位置，再放一个链表，链表节点中存放上键值对数据……

PS：JavaScript中：

• 数组就简单把下标0/1/2……也当做键值对的键就OK了
• 数组就是对象，对象也是数组，对象中的属性也是键值对，属性也存储在hashtable中
  

其他用途

快速比对：Java和C#的对象都可以生成一个哈希值，以快速的比较两个对象的内容是否不同（注意：只能比不同，@想一想@：为什么？）

加密：比如用户注册时的填写的密码，不应该直接（以明文）的方式存储在系统（数据库）中，而是应该对其用MD5加密，这样：

1. 把用户输入的密码进行加密后，和存储在数据库中的已加密密码进行比较，仍然可以确定用户是否输入了正确的密码
2. 如果数据库信息被泄露，黑客仍然无法逆推得到用户的密码（干各种坏事，因为用户可以在多个系统使用相同的用户名和密码……）

PS：

• csdn密码泄露
• 为什么现在无法找回密码（只能重置）
• 所谓的MD5破解：标准的MD5的算法是公开的，
  

非对称加密

很多时候，我们还是希望加密了之后能够解密。

加密算法

比如你想给你的男/女朋友传递小纸条，“今晚8点小树林见”，但不想这纸条的内容被经手的同学知道，你肿么办？

你可以用拼音，拼音还要按某种方式调整顺序，故意加一些无关的混淆符号……

这就是算法，加密算法！

但是，保险不保险？安全不安全？

纯算法加密是有迹可循，可以被破解的，延伸阅读：福尔摩斯 跳舞的小人

秘钥

为了提高安全性，我们往往在算法的基础上再加一个秘钥：解开加密信息的钥匙。

比如，你收到了一段我发给你的加密信息，按我们约定的加密算法解密之后，发现原文信息是：

01302120070501112080785111066251107

打开飞哥的《折腾》第三卷《从包工头到老码农》这本书：

• 翻到第013页，找第02行的第12个字：飞
• 翻到第007页，找第05行的第01个字：哥
• 翻到第112页，找第08行的第07个字：我
• 翻到第851页，找第11行的第06个字：爱
• 翻到第625页，找第11行的第07个字：你
  

所以，《从包工头到老码农》这本书就是秘钥。

PS：老谍战片里面所谓的密码本，就这个东西。

公钥私钥

按上面的方式，加密解密，用同一把钥匙就可以啦：这就是对称加密。

但非对称加密需要两把钥匙。为了方便，我们称其中一把为公钥，另一把为私钥（只是个称呼，哪一把当公钥哪一把当私钥随便你）：

• 用公钥加密的信息，只有用私钥解密
• 用私钥加密的信息，只有用公钥解密

作业

@想一想@：

1. hash算法还能用于干嘛？
2. 为什么需要非对称加密？（后文详述：HTTPS实现）
   

源栈学历

在当前系列 数据结构和算法 中继续学习：

多快好省！前端后端，线上线下，名师精讲

• 先学习，后付费；
• 不满意，不要钱。
• 编程培训班，我就选源栈

更多了解 加：