哈希:算法 / HashTable / Hash用途 / 非对称加密

更多
2021年04月09日 11点10分 作者:叶飞 修改

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


Hash

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

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

Hash算法(函数)通常要求:

  1. 同一散列算法:散列值不同,输入值肯定也不同;
  2. 但是,散列值相同,输入值可以相同。

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

常用hash算法包括:MD5SHA-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. 为什么需要非对称加密?



算法 数据结构 复杂度
赞: 0 踩: 0

打赏
已收到打赏的 帮帮币

你的 打赏 非常重要!
为了保证文章的质量,每一篇文章的发布,都已经消耗了作者 1 枚 帮帮币
没有“帮帮币”,作者无法发布新的文章。

全系列阅读
评论 / 0

编程基础


项目管理相关

需求发布、开发规划、部署、测试,源代码版本管理(git)等……

逸闻史话

认识计算机

编程语言

数据结构和算法

Web开发基础

全部
关键字



帮助

反馈