首页 > 编程语言 >哈希算法(上)

哈希算法(上)

时间:2022-09-26 17:26:41浏览次数:52  
标签:文件 标识 算法 哈希 散列 图片

目录

什么是哈希算法?

不管是“散列”还是“哈希”,这都是中文翻译的差别,英文其实就是“Hash”。所以,我们常听到有人把“散列表”叫作“哈希表”“Hash 表”,把“哈希算法”叫作“Hash 算法”或者“散列算法”。

将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值

要想设计一个优秀的哈希算法,需要满足的几点要求:

  • 从哈希值不能反向推导出原始数据(所以哈希算法也叫单向哈希算法);
  • 对输入数据非常敏感,哪怕原始数据只修改了一个 Bit,最后得到的哈希值也大不相同;
  • 散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小;
  • 哈希算法的执行效率要尽量高效,针对较长的文本,也能快速地计算出哈希值。

哈希算法的应用非常非常多,我选了最常见的七个,分别是安全加密唯一标识数据校验散列函数负载均衡数据分片分布式存储。这节我们先来看前四个应用。

应用一:安全加密

说到哈希算法的应用,最先想到的应该就是安全加密。最常用于加密的哈希算法是 MD5(MD5 Message-Digest Algorithm,MD5 消息摘要算法)和 SHA(Secure Hash Algorithm,安全散列算法)。除了这两个之外,当然还有很多其他加密算法,比如 DES(Data Encryption Standard,数据加密标准)、AES(Advanced Encryption Standard,高级加密标准)。

前面我讲到的哈希算法四点要求,对用于加密的哈希算法来说,有两点格外重要。第一点是很难根据哈希值反向推导出原始数据,第二点是散列冲突的概率要很小。

应用二:唯一标识

我先来举一个例子。如果要在海量的图库中,搜索一张图是否存在,我们不能单纯地用图片的元信息(比如图片名称)来比对,因为有可能存在名称相同但图片内容不同,或者名称不同图片内容相同的情况。那我们该如何搜索呢?

我们知道,任何文件在计算中都可以表示成二进制码串,所以,比较笨的办法就是,拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对。如果相同,则说明图片在图库中存在。但是,每个图片小则几十 KB、大则几 MB,转化成二进制是一个非常长的串,比对起来非常耗时。有没有比较快的方法呢?

我们可以给每一个图片取一个唯一标识,或者说信息摘要。比如,我们可以从图片的二进制码串开头取 100 个字节,从中间取 100 个字节,从最后再取 100 个字节,然后将这 300 个字节放到一块,通过哈希算法(比如 MD5),得到一个哈希字符串,用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中,这样就可以减少很多工作量。

如果还想继续提高效率,我们可以把每个图片的唯一标识,和相应的图片文件在图库中的路径信息,都存储在散列表中。当要查看某个图片是不是在图库中的时候,我们先通过哈希算法对这个图片取唯一标识,然后在散列表中查找是否存在这个唯一标识。

如果不存在,那就说明这个图片不在图库中;如果存在,我们再通过散列表中存储的文件路径,获取到这个已经存在的图片,跟现在要插入的图片做全量的比对,看是否完全一样。如果一样,就说明已经存在;如果不一样,说明两张图片尽管唯一标识相同,但是并不是相同的图片。

应用三:数据校验

电驴这样的 BT 下载软件你肯定用过吧?我们知道,BT 下载的原理是基于 P2P 协议的。我们从多个机器上并行下载一个 2GB 的电影,这个电影文件可能会被分割成很多文件块(比如可以分成 100 块,每块大约 20MB)。等所有的文件块都下载完成之后,再组装成一个完整的电影文件就行了。

我们通过哈希算法,对 100 个文件块分别取哈希值,并且保存在种子文件中。我们在前面讲过,哈希算法有一个特点,对数据很敏感。只要文件块的内容有一丁点儿的改变,最后计算出的哈希值就会完全不同。所以,当文件块下载完成之后,我们可以通过相同的哈希算法,对下载好的文件块逐一求哈希值,然后跟种子文件中保存的哈希值比对。如果不同,说明这个文件块不完整或者被篡改了,需要再重新从其他宿主机器上下载这个文件块。

内容小结

  • 第一个应用是唯一标识,哈希算法可以对大数据做信息摘要,通过一个较短的二进制编码来表示很大的数据。

  • 第二个应用是用于校验数据的完整性和正确性。

  • 第三个应用是安全加密,我们讲到任何哈希算法都会出现散列冲突,但是这个冲突概率非常小。越是复杂哈希算法越难破解,但同样计算时间也就越长。所以,选择哈希算法的时候,要权衡安全性和计算时间来决定用哪种哈希算法。

  • 第四个应用是散列函数,这个我们前面讲散列表的时候已经详细地讲过,它对哈希算法的要求非常特别,更加看重的是散列的平均性和哈希算法的执行效率。

标签:文件,标识,算法,哈希,散列,图片
From: https://www.cnblogs.com/xiayuxue/p/16731648.html

相关文章

  • 密码学算法技巧
    2.6密码学算法技巧2.6.1Hash算法1)简介:Hash算法(又称散列算法、散列函数、哈希算法)是把任意长度的输入通过散列算法变成固定长度的输出,且不可逆的单向密码机制。Hash算法是......
  • 哈希表
    用于给一个元素,判断其有没有在集合中出现过字符串的对应代码constbase="a".charCodeAt();//遍历s遇到相同字符在哈希数组中做++for(leti=0;i<s.......
  • 波函数坍缩算法
    https://www.bilibili.com/video/BV1k5411u7t7/?spm_id_from=333.788.top_right_bar_window_history.content.click&vd_source=426e9399caf4b3d209b6ac8487de530bhttps://......
  • 14 -- 排序算法之冒泡排序
    冒泡排序的基本思想:通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的数逐渐从前移向后,就像水底下的气泡一样逐渐向上冒。......
  • 排序算法总结
    本文参考十大经典排序算法总结|JavaGuide,感谢Guide哥!十大经典排序算法总结本文转自:十大经典排序算法最强总结(含Java、Python码实现)|郭耀华'sBlog(guoyaohua.c......
  • 在强化学习算法性能测试时使用训练好的模型运行游戏,此时如何控制实时游戏画面的帧数
    问题:在强化学习算法性能测试时使用训练好的模型运行游戏,此时如何控制实时游戏画面的帧数?  ========================================  看到很多训练好的模型......
  • 在 Linux 上使用《算法》第4版官网中的 algs4.jar 包
    使用《算法》第4版(AlgorithmsFourthEdition)中的algs4.jar包下载algs4.jar官网网址:https://algs4.cs.princeton.edu/code/进入网站后使用浏览器的查找功能ctrl+......
  • 计算空间物体包围球的两种算法实现
    1.概述在进行二维空间几何运算的之前,往往会用包围盒进行快速碰撞检测,从而筛掉一些无法碰撞到的可能。而在三维中,比较常用的就是包围球了。当然,如何计算包围球是一个问题......
  • MySQL的join算法优化
    在Mysql的实现中,Nested-LoopJoin有3种实现的算法:SimpleNested-LoopJoin:SNLJ,简单嵌套循环连接IndexNested-LoopJoin:INLJ,索引嵌套循环连接BlockNested-LoopJoin:BN......
  • 智能优化算法——鲸鱼优化算法(WOA) MATLAB算法实现
    智能优化算法——鲸鱼优化算法(WOA)Main%_________________________________________________________________________%---智能优化算法---......