密码学 | 蓄势待发!说说什么是散列算法?

密码学 | 蓄势待发!说说什么是散列算法?

Android小彩虹2021-08-25 17:32:50220A+A-

前言

  • 在计算机科学中,散列算法 的应用场景有很多,例如:散列表的散列函数、消息完整性验证的消息摘要算法,除此之外你还知道哪些应用场景呢?
  • 在这篇文章里,我将带你列举散列算法的 基本要求 & 应用场景。如果能帮上忙,请务必点赞加关注,这真的对我非常重要。

系列文章

相关文章


目录

1. 概述

1.1 散列函数的定义

散列算法(Hash算法,又译哈希算法) 是一种将任意长度输入转换为固定长度输出的算法,输出的结果就是散列值。

散列算法一定是 压缩映射,即:值域会远小于输入值域。例如,MD5的输出散列值为 128 位,SHA256的输出散列值为 256 位。

1.2 散列算法的性质

散列算法有很多,但是都要满足以下性质 & 要求:

性质 描述
单向性 通过散列值无法反推输入数据
一致性 同一个输入数据,计算后的散列值总是相同的
高效性 散列运算过程尽量快速 & 高效
随机性 散列值在输出值域的分布尽量随机
输入敏感性 相似的数据,计算后的散列值差别很大

2. 散列冲突

2.1 什么是散列冲突?

上一节提到,散列算法是压缩映射(输出值域远小于输入值域),因此肯定会存在两个甚至多个输入数据映射到同一个散列值的情况,这就是发生了 散列冲突(又称散列碰撞,Hash Collision)

需要注意的是,散列冲突是无法完全避免的,这其实只要用鸽巢原理(又称:抽屉原理)就很好理解了,假设有 10 个鸽巢,现有 11 只鸽子,无论分配多么平均,也肯定有一个鸽巢里有两只甚至多只鸽子。

举个例子,Java中的字符串"Aa""BB"的散列值就冲突了:

String str1 = "Aa";
String str2 = "BB";
System.out.println(str1.hashCode());  2112
System.out.println(str2.hashCode());  2112 散列冲突

既然散列冲突是无法完全避免的,那么只能采取应对措施,主要有两种:降低概率 & 处理冲突

2.2 降低散列冲突概率

降低散列冲突概率的思路主要有:

  • 1、优化散列算法

前面提到了散列算法的随机性:散列值在输出值域的分布尽量随机。这是为了避免出现“堆积”现象,即散列值集中于输出值域的某一块区域,这种情况无疑会增大冲突概率。

  • 2、扩大输出值域

在输入值域相对稳定的情况下,扩大输出值域可以降低冲突概率。例如SHA的散列值长度就比MD5长,相应的冲突概率更低。HashMap 在达到阈值时执行扩容,本质上也是扩大了输出值域。

2.3 处理散列冲突

《数据结构 | 散列表是如何避免散列冲突的?》中,我们将讨论散列表中的解决方案。


3. 散列算法的应用场景

Editting...


4. 总结

  • 散列算法是一种将任意长度输入转换为固定长度输出的算法,由于是压缩映射,因而无法避免散列冲突。

参考资料

  • 《Java加密与解密的艺术》(第6、7、8、9章) —— 梁栋 著
  • 《数据结构与算法之美》(第21、22章) —— 王争 讲,极客时间 出品
  • 《散列算法》—— 维基百科

推荐阅读

感谢喜欢!你的点赞是对我最大的鼓励!欢迎关注彭旭锐的GitHub!

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示 | 支付宝红包
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1
本网站由 提供CDN/云存储服务

联系我们