数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?

王争 2018-11-07
还记得 2011 年 CSDN 的“脱库”事件吗?当时,CSDN 网站被黑客攻击,超过 600 万用户的注册邮箱和密码明文被泄露,很多网友对 CSDN 明文保存用户密码行为产生了不满。如果你是 CSDN 的一名工程师,你会如何存储用户密码这么重要的数据吗?仅仅 MD5 加密一下存储就够了吗? 要想搞清楚这个问题,就要先弄明白哈希算法。
哈希算法历史悠久,业界著名的哈希算法也有很多,比如 MD5、SHA 等。在我们平时的开发中,基本上都是拿现成的直接用。所以,我今天不会重点剖析哈希算法的原理,也不会教你如何设计一个哈希算法,而是从实战的角度告诉你,在实际的开发中,我们该如何用哈希算法解决问题

什么是哈希算法?

我们前面几节讲到“散列表”“散列函数”,这里又讲到“哈希算法”,你是不是有点一头雾水?实际上,不管是“散列”还是“哈希”,这都是中文翻译的差别,英文其实就是“Hash”。所以,我们常听到有人把“散列表”叫作“哈希表”“Hash 表”,把“哈希算法”叫作“Hash 算法”或者“散列算法”。那到底什么是哈希算法呢?
哈希算法的定义和原理非常简单,基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。但是,要想设计一个优秀的哈希算法并不容易,根据我的经验,我总结了需要满足的几点要求:
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(82)

  • Smallfly
    课后思考:

    区块链是一块块区块组成的,每个区块分为两部分:区块头和区块体。

    区块头保存着 自己区块体 和 上一个区块头 的哈希值。

    因为这种链式关系和哈希值的唯一性,只要区块链上任意一个区块被修改过,后面所有区块保存的哈希值就不对了。

    区块链使用的是 SHA256 哈希算法,计算哈希值非常耗时,如果要篡改一个区块,就必须重新计算该区块后面所有的区块的哈希值,短时间内几乎不可能做到。

    作者回复: 👍

    2018-11-07
    7
    245
  • 雪无痕
    除了hash+salt,现在大多公司都采用无论密码长度多少,计算字符串hash时间都固定或者足够慢的算法如PBKDF2WithHmacSHA1,来降低硬件计算hash速度,减少不同长度字符串计算hash所需时间不一样而泄漏字符串长度信息,进一步减少风险。
    2018-11-07
    3
    89
  • oyt
    加salt,也可理解为为密码加点佐料后再进行hash运算。比如原密码是123456,不加盐的情况加密后假设是是xyz。 黑客拿到脱机的数据后,通过彩虹表匹配可以轻松破解常用密码。如果加盐,密码123456加盐后可能是12ng34qq56zz,再对加盐后的密码进行hash后值就与原密码hash后的值完全不同了。而且加盐的方式有很多种,可以是在头部加,可以在尾部加,还可在内容中间加,甚至加的盐还可以是随机的。这样即使用户使用的是最常用的密码,黑客拿到密文后破解的难度也很高。

    作者回复: 👍

    2018-11-13
    4
    63
  • Jerry银银
    原来“散列冲突”的数学原理是鸽巢原理,为啥大部分算法书上讲解散列表的时候,不提一下呢。搞得我平时向朋友解释为什么存在冲突的时候,用得都是“鸽巢原理的白话版”,而且在讲解的时候还不知道那就是鸽巢原理,很尬!

    离散数学的课必须得好好补完

    作者回复: 👍

    2018-11-07
    52
  • 小龙的城堡
    老师您好,我有一个疑问就是hash算法用于加密数据,但是我理解的加密是需要对应解密的,但是hash算法并不能解密,这用应用更像是数字签名,不知道我理解是不是有问题,感谢!

    作者回复: 没错 可以理解为数字签名

    2018-11-07
    2
    27
  • 王鸿运
    md5不应该称之为加密算法,所谓加密,肯定对应有解密,不管是简单的异或加密,还是对称加密算法(aes,des)或者是非对称加密(rsa,ecc),都有加密和解密方式
    而md5是不可逆的,因此不能称为加密算法,从名字来看,md5就算一个摘要算法,用于生成字符串的摘要信息以及签名校验信息
    2018-12-18
    24
  • 姜威
    带着问题来学习:
    1.如何防止数据库中的用户信息被脱库?
    2.你会如何存储用户密码这么重要的数据吗?仅仅 MD5 加密一下存储就够了吗?
    3.在实际开发中,我们应该如何用哈希算法解决问题?
    一、什么是哈希算法?
    1.定义
    将任意长度的二进制值串映射成固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。
    2.如何设计一个优秀的哈希算法?
    ①单向哈希:
    从哈希值不能反向推导出哈希值(所以哈希算法也叫单向哈希算法)。
    ②篡改无效:
    对输入敏感,哪怕原始数据只修改一个Bit,最后得到的哈希值也大不相同。
    ③散列冲突:
    散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小。
    ④执行效率:
    哈希算法的执行效率要尽量高效,针对较长的文本,也能快速计算哈希值。
    二、哈希算法的常见应用有哪些?
    7个常见应用:安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。
    1.安全加密
    ①常用于加密的哈希算法:
    MD5:MD5 Message-Digest Algorithm,MD5消息摘要算法
    SHA:Secure Hash Algorithm,安全散列算法
    DES:Data Encryption Standard,数据加密标准
    AES:Advanced Encryption Standard,高级加密标准
    ②对用于加密的哈希算法,有两点格外重要,第一点是很难根据哈希值反向推导出原始数据,第二点是散列冲突的概率要小。
    ③在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。
    2.唯一标识
    通过哈希算法计算出数据的唯一标识,从而用于高效检索数据。
    3.数据校验
    利用哈希算法对输入数据敏感的特点,可以对数据取哈希值,从而高效校验数据是否被篡改过。
    4.散列函数
    散列函数中用到的哈希算法更加关注散列后的值能不能平均分布,以及散列函数的执行快慢。
    三、思考
    1.如何防止数据库中的用户信息被脱库?你会如何存储用户密码这么重要的数据吗?
    ①使用MD5进行加密
    ②字典攻击:如果用户信息被“脱库”,黑客虽然拿到的是加密之后的密文,但可以通过“猜”的方式来破解密码,这是因为,有些用户的密码太简单。
    ③针对字典攻击,我们可以引入一个盐(salt),跟用户密码组合在一起,增加密码的复杂度。
    2.现在,区块链是一个很火的领域,它被很多人神秘化,不过其底层的实现原理并不复杂。其中,哈希算法就是它的一个非常重要的理论基础。你能讲一讲区块链使用的是哪种哈希算法吗?是为了解决什么问题而使用的呢?
    2018-11-16
    1
    24
  • FLYING
    越是复杂哈希算法越难破解,但同样计算时间也就越少。这句话应该是越多吧?

    作者回复: 谢谢指出 笔误 本来是想写“长”的 写成了“少”

    2018-11-07
    18
  • 🐱您的好友William🐱
    其实我感觉hash不可能做到无冲突的原理可以用机器学习里面的免费午餐理论解释,因为hash追求的其实就是机器学习中的best seperate,就是mapping之后,不只是把两个不一样的东西分开,还要保证两者足够远(最大margin),因为hash函数是要面对所有类型的数据分布,而免费午餐理论告诉我们:不存在一种完美的算法对所有类型的数据分布都能做到完美的分离,最好的算法一定是根据特定的数据分布特定设计出来的。所以像hash函数这种需要应对不特定数据分布的,需要广泛使用的,是一定不会将数据完美seperate的。

    作者回复: 👍

    2018-11-08
    17
  • 0.618
    所有的安全措施,只是增加攻击的成本而已!!!
    2018-11-08
    1
    9
  • 大张
    加盐之后,盐是随机的,但对一个用户来讲,盐是固定的,而且肯定是存储的,那同样找到盐之后可以轻易计算hash了
    2018-11-26
    1
    6
  • 伯安
    哈希算法的特点有一条:从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法)。

    可是JAVA中的MD5类不是有加密和解密方法吗?解密的过程,是不是代表哈希算法能够反向推导出原始数据呢?就这块比较困惑。。

    作者回复: 应该没有吧。有破解方法 但也是基于碰撞的。但它也只是最近才被破解的

    2018-11-07
    6
  • chengzise
    1. hash不可能做到无冲突的原理,可以用数学中的函数映射来理解。hash函数本质就是明文空间到密文空间的映射,以md5为例,它的密文空间是2^128,明文空间是无穷大的,所以存在多个明文映射到同一个密文,不存在无冲突的hash。
    2. 同时,为什么说可以设计出md5等碰撞概率小的hash函数:虽然刚才说的明文空间是无穷大的,但是实际人类使用的明文空间没有想象中的那么大,例如:大量的文章都是相对于有意义的,随机的乱码文章,人类根本不会使用到。因此还是可以设计出在人类使用的明文空间的hash函数的
    2019-05-25
    3
  • 落叶飞逝的恋
    老师有个问题:
    我们可以从图片的二进制码串开头取 100 个字节,从中间取 100 个字节,从最后再取 100 个字节,然后将这 300 个字节放到一块,通过哈希算法(比如 MD5),得到一个哈希字符串,用它作为图片的唯一标识。
    这里说的取图片的二进制码串头部、中部、尾部的100个字节,这样图片在第一次计算的时候,还是需要完全读取图片的流。第一次就很耗时呀?
    2018-12-20
    3
  • MrTin
    个人认为hash算法不能做加密用,因为解密不出来,文中说的不是准确

    作者回复: 我再去研究下 有没有要求说加密算法必须能解密才叫加密算法。这里你看以理解为数字签名

    2018-11-11
    1
    3
  • bro.
    java中是没有MD5的解密的,一个很简单的例子,一部电影可以加密成128为的MD5值存储,那么能将这128位的md5值还原成相对应的一部高清电影吗,如果可以的话,以后就不用拍电影了,直接写128位密码值还原一下就好了吗,网上的破解,只是维护一个密码表,暴力的一一对应,根据密码生成的MD5到表中查询是否存在,如果存在对应的密码值是?一般小公司要求不高的话会在密码前后加上特定的字符串在生成md5在上传保存的.有效避免常用密码被破解
    2018-11-07
    3
  • 张三
    7月最后一周了,继续加油,从6月10号开始的,希望能坚持下去!
    2019-07-29
    2
  • smarttime
    salt存到数据库中,如果脱库了,通过彩虹表还是可以破解的对吗?请老师讲一下密码加盐最佳实践,在网上找了很多文章要么人云亦云,要么自以为是的重复造轮子,希望老师可以拿着当前大厂的真实方案来解惑
    2018-12-13
    2
  • 学习爱好者
    王老师好,关于哈希加密,我查了一些资料,但是有几个点不太明白,希望老师能指点一下:
    1、网上说,固定盐值硬编码到程序里不安全,推荐把哈希值和随机盐一起存储到数据库里,这种做法是否可行?如果盐存在库里,脱库后也轻松拿到盐,用彩虹表也能比较容易破解吧?感觉这样做也不行啊
    2、这节里说到的哈希加密应该属于存储范畴,那web传输的账号密码怎么加密呢?直接在客户端求哈希值?还是把密码传到服务端再算哈希值?
    3、这节的举例子aes,des应该属于对称加密吧?感觉放到哈希加密好像不太合适。
    4、以MD5为例,有2^128个哈希值,但是我们可取的值有无数个,那按照鸽巢理论,碰撞的可能肯定大于1;相反,如果数据库里存原始密码,命中的可能只有1种,就是完全等于原始密码,从这个角度讲,如果不脱库,存储原始密码是不是更安全?
    2018-11-15
    2
    2
  • Hesher
    比特币是两重hash,先做hash160或sha256,然后RIPEMD160,得到160位的hash串。主要用于Pow工作量证明。使用这两种散列算法应该主要是考虑安全性,但至于为什么是这两种就不太清楚了。
    2018-11-07
    2
收起评论
82
返回
顶部