哈希算法 订阅
安全散列算法(英语:Secure Hash Algorithm,缩写为SHA)是一个密码散列函数家族,是FIPS所认证的安全散列算法。能计算出一个数字消息所对应到的,长度固定的字符串(又称消息摘要)的算法。且若输入的消息不同,它们对应到不同字符串的机率很高。 展开全文
安全散列算法(英语:Secure Hash Algorithm,缩写为SHA)是一个密码散列函数家族,是FIPS所认证的安全散列算法。能计算出一个数字消息所对应到的,长度固定的字符串(又称消息摘要)的算法。且若输入的消息不同,它们对应到不同字符串的机率很高。
信息
外文名
Secure Hash Algorithm
别    称
安全散列算法
国    家
美国
中文名
SHA家族
SHA家族家族成员
SHA家族的五个算法,分别是SHA-1、SHA-224、SHA-256、SHA-384,和SHA-512,由美国国家安全局(NSA)所设计,并由美国国家标准与技术研究院(NIST)发布;是美国的政府标准。后四者有时并称为SHA-2。SHA-1在许多安全协定中广为使用,包括TLS和SSL、PGP、SSH、S/MIME和IPsec,曾被视为是MD5(更早之前被广为使用的杂凑函数)的后继者。但SHA-1的安全性如今被密码学家严重质疑;虽然至今尚未出现对SHA-2有效的攻击,它的算法跟SHA-1基本上仍然相似;因此有些人开始发展其他替代的杂凑算法。 [1] 
收起全文
精华内容
下载资源
问答
  • 哈希算法 万次阅读 多人点赞
    2019-01-21 14:51:16

    对于哈希算法,在我们平时的开发中,都是基本上拿来就用就行了,所以这节我们将重点放在如何使用,并不进行哈希算法的原理剖析和如何设计一个哈希算法的讲解.

    什么是哈希算法?

    将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值(散列值).一个优秀的哈希算法需要满足:

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

    mysqlMD5举个例子:
    在这里插入图片描述

    MD5 的哈希值是 128 位的 Bit 长度,为了方便表示,mysql把它们转化成了 16 进制编码)。可以看出来,无论要哈希的文本有多长、多短,通过 MD5 哈希之后,得到的哈希值的长度都是相同的,而且得到的哈希值看起来像一堆随机数,完全没有规律。

    两个非常相似的文本11.的哈希值也是不同的呐

    经过哈希算法得到的哈希值,很难反向推导出原始数据。比如上面的例子中,我们就很难通过哈希值“36c942351ec9cc3ad124e288a5c9cf0b”反推出对应的文本“李四”。

    哈希算法要处理的文本可能是各种各样的。比如,对于非常长的文本,如果哈希算法的计算时间很长,那就只能停留在理论研究的层面,很难应用到实际的软件开发中。比如,我们把今天这篇包含 几千多个汉字的文章,用 MD5 计算哈希值,还是用不了 1ms 的时间。

    哈希算法的应用

    哈希算法的应用非常非常多,最常见的有七个,分别是安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。

    1.安全加密

    说到哈希算法的应用,最先想到的应该就是安全加密。

    最常用于加密的哈希算法是MD5(MD5 Message-Digest Algorithm,MD5 消息摘要算法)和SHA(Secure Hash Algorithm,安全散列算法)。

    除了这两个之外,当然还有很多其他加密算法,比如DES(Data Encryption Standard,数据加密标准)、AES(Advanced Encryption Standard,高级加密标准)。

    在前面提到的哈希算法四点要求中,对用于加密的哈希算法来说,有两点格外重要。

    • 很难根据哈希值反向推导出原始数据(为了防止数据泄露,最基本的要求)
    • 散列冲突的概率要很小

    提问:为什么无法做到完全不冲突?

    答:组合数学中一个非常基础的理论,鸽巢原理(也叫抽屉原理):这个原理本身很简单,它是说,如果有 10 个鸽巢,有 11 只鸽子,那肯定有 1 个鸽巢中的鸽子数量多于 1 个,换句话说就是,肯定有 2 只鸽子在 1 个鸽巢内。

    还是拿MD5来讲:

    哈希算法产生的哈希值的长度是固定且有限的。比如MD5 ,哈希值是固定的 128 位二进制串,能表示的数据是有限的,最多能表示 2^128 个数据,而我们要哈希的数据是无穷的。基于鸽巢原理,如果我们对 2^128+1 个数据求哈希值,就必然会存在哈希值相同的情况。这里你应该能想到,一般情况下,哈希值越长的哈希算法,散列冲突的概率越低。


    不过,即便哈希算法存在散列冲突的情况,但是因为哈希值的范围很大,冲突的概率极低,所以相对来说还是很难破解的。像 MD5,有 2^128 个不同的哈希值,这个数据已经是一个天文数字了,所以散列冲突的概率要小于 1/2^128。

    提问:为什么冲突的概率高的话,就会容易破解?

    答:首先我们需要理解破解的意思,这里的破解不是指的搞出算法是如何运行的,而是根据哈希值找到原始数据!如何找到,那就穷举呗.找一堆数据,然后通过该算法计算哈希值,直到找到一个与我们要破解的哈希值相同的哈希值,那么我们穷举的原始数据就是我们需要破解的原始数据!!!


    如果我们拿到一个 MD5 哈希值,希望通过毫无规律的穷举的方法,找到跟这个 MD5 值相同的另一个数据,那耗费的时间应该是个天文数字。所以,即便哈希算法存在冲突,但是在有限的时间和资源下,哈希算法还是被很难破解的。

    除此之外,没有绝对安全的加密。越复杂、越难破解的加密算法,需要的计算时间也越长。比如 SHA-256 比 SHA-1 要更复杂、更安全,相应的计算时间就会比较长。密码学界也一直致力于找到一种快速并且很难被破解的哈希算法。我们在实际的开发过程中,也需要权衡破解难度和计算时间,来决定究竟使用哪种加密算法。

    2. 唯一标识

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

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

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

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

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

    3.数据校验

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

    我们知道,网络传输是不安全的,下载的文件块有可能是被宿主机器恶意修改过的,又或者下载过程中出现了错误,所以下载的文件块可能不是完整的。如果我们没有能力检测这种恶意修改或者文件下载出错,就会导致最终合并后的电影无法观看,甚至导致电脑中毒。现在的问题是,如何来校验文件块的安全、正确、完整呢?

    具体的 BT 协议很复杂,校验方法也有很多,我来说其中的一种思路。

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

    4. 散列函数

    前面讲了很多哈希算法的应用,实际上,散列函数也是哈希算法的一种应用。

    我们前两节讲到,散列函数是设计一个散列表的关键。它直接决定了散列冲突的概率和散列表的性能。不过,相对哈希算法的其他应用,散列函数对于散列算法冲突的要求要低很多。即便出现个别散列冲突,只要不是过于严重,我们都可以通过开放寻址法或者链表法解决。

    不仅如此,散列函数对于散列算法计算得到的值,是否能反向解密也并不关心。散列函数中用到的散列算法,更加关注散列后的值是否能平均分布,也就是,一组数据是否能均匀地散列在各个槽中。除此之外,散列函数执行的快慢,也会影响散列表的性能,所以,散列函数用的散列算法一般都比较简单,比较追求效率。


    以下三个都与分布式有关:

    ***5.负载均衡

    我们知道,负载均衡算法有很多,比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞(session sticky)的负载均衡算法呢?也就是说,我们需要在同一个客户端上,在一次会话中的所有请求都路由到同一个服务器上。

    最直接的方法就是,维护一张映射关系表,这张表的内容是客户端 IP 地址或者会话 ID 与服务器编号的映射关系。客户端发出的每次请求,都要先在映射表中查找应该路由到的服务器编号,然后再请求编号对应的服务器。这种方法简单直观,但也有几个弊端:

    • 如果客户端很多,映射表可能会很大,比较浪费内存空间;
    • 客户端下线、上线,服务器扩容、缩容都会导致映射失效,这样维护映射表的成本就会很大;

    如果借助哈希算法,这些问题都可以非常完美地解决。我们可以通过哈希算法,对客户端 IP 地址或者会话 ID 计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器编号。 这样,我们就可以把同一个 IP 过来的所有请求,都路由到同一个后端服务器上。(这里是对每一个请求都要计算一次hash值,不知道nginx是不是这样实现的,还需要进一步了解...)

    6. 数据分片

    哈希算法还可以用于数据的分片。我这里有两个例子。

    1. 如何统计“搜索关键词”出现的次数?

    假如我们有 1T 的日志文件,这里面记录了用户的搜索关键词,我们想要快速统计出每个关键词被搜索的次数,该怎么做呢?

    我们来分析一下。这个问题有两个难点,第一个是搜索日志很大,没办法放到一台机器的内存中。第二个难点是,如果只用一台机器来处理这么巨大的数据,处理时间会很长。

    针对这两个难点,我们可以先对数据进行分片,然后采用多台机器处理的方法,来提高处理速度。

    具体的思路是这样的:为了提高处理的速度,我们用 n 台机器并行处理。我们从搜索记录的日志文件中,依次读出每个搜索关键词,并且通过哈希函数计算哈希值,然后再跟 n 取模,最终得到的值,就是应该被分配到的机器编号。 这样,哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说,同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数,最后合并起来就是最终的结果。 实际上,这里的处理过程也是 MapReduce 的基本设计思想。

    我的疑问:"也就是说,同一个搜索关键词会被分配到同一个机器.上。”这句话我的理解就是一台机器对应与一-个关键字,如果是这样的话,那么,如果搜索的词全都不相同的话,那得用多少台服务器呢?像这种情况该如何处理啊?

    目前还没有想通 ^-^

    2.如何快速判断图片是否在图库中?

    如何快速判断图片是否在图库中?上面介绍了一种方法,即给每个图片取唯一标识(或者信息摘要),然后构建散列表。 但是我们现在要给他加一点需求了

    假设现在我们的图库中有 1 亿张图片,很显然,在单台机器上构建散列表是行不通的。因为单台机器的内存有限,而 1 亿张图片构建散列表显然远远超过了单台机器的内存上限。

    我们同样可以对数据进行分片,然后采用多机处理。我们准备 n 台机器,让每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片,计算唯一标识,然后与机器个数 n 求余取模,得到的值就对应要分配的机器编号,然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。

    当我们要判断一个图片是否在图库中的时候,我们通过同样的哈希算法,计算这个图片的唯一标识,然后与机器个数 n 求余取模。假设得到的值是 k,那就去编号 k 的机器构建的散列表中查找。

    现在,我们来估算一下,给这 1 亿张图片构建散列表大约需要多少台机器。

    散列表中每个数据单元包含两个信息,哈希值和图片文件的路径。假设我们通过 MD5 来计算哈希值,那长度就是 128 比特,也就是 16 字节。文件路径长度的上限是 256 字节,我们可以假设平均长度是 128 字节。如果我们用链表法来解决冲突,那还需要存储指针,指针只占用 8 字节。所以,散列表中每个数据单元就占用 152 字节(这里只是估算,并不准确)。

    假设一台机器的内存大小为 2GB,散列表的装载因子为 0.75,那一台机器可以给大约 1000 万(2GB*0.75/152)张图片构建散列表。所以,如果要对 1 亿张图片构建索引,需要大约十几台机器。在工程中,这种估算还是很重要的,能让我们事先对需要投入的资源、资金有个大概的了解,能更好地评估解决方案的可行性。

    实际上,针对这种海量数据的处理问题,我们都可以采用多机分布式处理。借助这种分片的思路,可以突破单机内存、CPU 等资源的限制。

    7.分布式存储

    现在互联网面对的都是海量的数据、海量的用户。我们为了提高数据的读取、写入能力,一般都采用分布式的方式来存储数据,比如分布式缓存。我们有海量的数据需要缓存,所以一个缓存机器肯定是不够的。于是,我们就需要将数据分布在多台机器上。

    该如何决定将哪个数据放到哪个机器上呢?我们可以借用前面数据分片的思想,即通过哈希算法对数据取哈希值,然后对机器个数取模,这个最终值就是应该存储的缓存机器编号。

    但是,如果数据增多,原来的 10 个机器已经无法承受了,我们就需要扩容了,比如扩到 11 个机器,这时候麻烦就来了。因为,这里并不是简单地加个机器就可以了。

    原来的数据是通过与 10 来取模的。比如 13 这个数据,存储在编号为 3 这台机器上。但是新加了一台机器中,我们对数据按照 11 取模,原来 13 这个数据就被分配到 2 号这台机器上了。
    在这里插入图片描述

    因此,所有的数据都要重新计算哈希值,然后重新搬移到正确的机器上。这样就相当于,缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存,直接去请求数据库。这样就可能发生雪崩效应,压垮数据库。

    所以,我们需要一种方法,使得在新加入一个机器后,并不需要做大量的数据搬移。这时候,一致性哈希算法就要登场了。

    假设我们有 k 个机器,数据的哈希值的范围是 [0, MAX]。我们将整个范围划分成 m 个小区间(m 远大于 k),每个机器负责 m/k 个小区间。当有新机器加入的时候,我们就将某几个小区间的数据,从原来的机器中搬移到新的机器中。这样,既不用全部重新哈希、搬移数据,也保持了各个机器上数据数量的均衡。 一致性哈希算法的基本思想就是这么简单。除此之外,它还会借助一个虚拟的环和虚拟结点,更加优美地实现出来。这里我就不展开讲了,如果感兴趣,你可以看下这个https://www.sohu.com/a/158141377_479559。

    拿上面的例子来说:

    其实就是将%10之后对应于机器3的数据copy到机器2上去即可,只要是对应机器编号会改变的都需要搬移(这里我想得是这种海量数据的搬移,难道不需要花费时间和精力吗?)

    除了我们上面讲到的分布式缓存,实际上,一致性哈希算法的应用非常广泛,在很多分布式存储系统中,都可以见到一致性哈希算法的影子。

    附录:区块链

    首先可以看看:区块链入门

    总的来说:

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

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

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

    我们拿修改一个区块来一步步看为什么后面所有区块保存的哈希值就不对了:

    • 修改一个区块,就是区块体变了
    • 区块体变了,区块头中存储的自己区块体的哈希值就得发生变化,也就是说,区块头变了
    • 区块头变了,对应于下一个区块来讲那就是上一个区块头变了
    • 上一个区块头变了,那么自己区块头中存储的上一个区块头的哈希值也就得跟着变。
    • 以此类推,后面的区块都得改变,而哈希的计算又很耗时间,所以这是不可能的事情
      正是通过这种联动机制,区块链保证了自身的可靠性,数据一旦写入,就无法被篡改。这就像历史一样,发生了就是发生了,从此再无法改变。

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

    参考自:极客时间 数据结构与算法之美

    更多相关内容
  • 针对非局部均值(NLM)算法度量邻域块相似度不够准确的缺点,提出了一种基于差异哈希算法与汉明距离的改进NLM算法。传统算法通过欧氏距离度量邻域块之间的相似度,保持边缘和细节的能力较弱,易导致滤波后的图像模糊失真...
  • 多索引哈希是目前使用最广泛的针对二进制码的索引算法. 由于多索引哈希基于数据集中的二进制码呈均匀... 在大规模数据集上的实验表明,与多索引哈希算法相比数据依赖的多索引哈希算法可以使查询速度提升36.9%–87.4%.
  • 参考网上博客的感知哈希算法的理论知识,实现基本的感知哈希算法,内有几张图片用来测试,程序可参考。
  • CRC16算法,哈希算法,用于数据传输校验
  • #资源达人分享计划#
  • Python3实现基于PHA实现图像配准
  • 本文提出了一种基于点对相似度的深度非松弛哈希算法, 在卷积神经网络的输出端使用可导的软阈值函数代替传统方法中所用的符号函数使准哈希码非线性接近−1或1, 将网络输出的结果直接用于计算训练误差, 在损失函数中...
  • 为克服此类问题, 设计了基于改进的局部二值模式(LBP)算子与动态更新变换的紧凑图像哈希算法。引入线性插值技术, 对输入图像实现预处理, 改善哈希序列对尺度缩放的稳健性。利用Ring分割, 将插值图像转化成二次图像。...
  • 千金难买,肯定不会后悔,因为google的感知哈希算法准确率不怎么样,本代码通过对google的算法进行改良,能生成图片指纹进行图像相似度比对,高速检索,图片搜索,基于Java语言实现的,亲测相似度图片搜索准确率极高...
  • 本人为在校大学生,所写源码可能不够尽善尽美,希望各位包涵指正。写这个代码只是为了练手,可能有错误,只为大家提供思路和方法。
  • 此压缩包有关于哈希算法的资料介绍以及其在Matlab和Visual studio中的代码实现。
  • 局部敏感哈希(LSH)算法是有效的高维数据索引方法之一,该算法成功地解决了“维数灾难”问题。分析了LSH算法中主要参数对索引性能的影响,在规模不同的图像数据集上应用了LSH算法,实验结果表明选择合适的参数时,其性能...
  • 利用OpenCvSharp实现感知哈希算法进行图片相似度对比及Stitcher类图像拼接生成全景图像 vs2015环境
  • 主要介绍了c#哈希算法的实现方法及思路,有需要的朋友可以参考一下
  • MD5_哈希算法_md5_

    2021-10-04 04:16:30
    MD5哈希算法, 任意长度数据提取出固定长度的数组,MD5 hash algorithm
  • 哈希算法C语言实现

    2016-02-17 12:56:54
    哈希算法C语言实现
  • 图像相似度比较哈希算法: 什么是哈希(Hash)? • 散列函数(或散列算法,又称哈希函数,英语:Hash Function)是一种从任何一种数据中创建小 的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变...

    图像相似度比较哈希算法:

    什么是哈希(Hash)?

    • 散列函数(或散列算法,又称哈希函数,英语:Hash Function)是一种从任何一种数据中创建小 的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定 下来。该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums, 或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。

    • 通过哈希算法得到的任意长度的二进制值映射为较短的固定长度的二进制值,即哈希值。此外, 哈希值是一段数据唯一且极其紧凑的数值表示形式,如果通过哈希一段明文得到哈希值,哪怕只 更改该段明文中的任意一个字母,随后得到的哈希值都将不同。

    • 哈希算法是一个函数,能够把几乎所有的数字文件都转换成一串由数字和字母构成的看似乱码的 字符串。

    哈希函数的特点

    哈希函数作为一种加密函数,其拥有两个最重要特点:

    1. 不可逆性。输入信息得出输出的那个看似乱码的字符串(哈希值)非常容易,但是从输出的字符 串反推出输入的结果却是却非常非常难。
    2. 输出值唯一性和不可预测性。只要输入的信息有一点点区别,那么根据哈希算法得出来的输出值 也相差甚远。

    哈希算法的种类

    哈希算法是一类算法的总称,共有三种:

    1. 均值哈希算法aHash
    2. 差值哈希算法dHash
    3. 感知哈希算法pHash

    汉明距离

    两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
    在这里插入图片描述

    均值哈希算法

    步骤:

    1. 缩放:图片缩放为8*8,保留结构,除去细节。
    2. 灰度化:转换为灰度图。
    3. 求平均值:计算灰度图所有像素的平均值。
    4. 比较:像素值大于平均值记作1,相反记作0,总共64位。
    5. 生成hash:将上述步骤生成的1和0按顺序组合起来既是图片的指纹(hash)。
    6. 对比指纹:将两幅图的指纹对比,计算汉明距离,即两个64位的hash值有多少位是不一样的,不 相同位数越少,图片越相似。

    差值哈希算法

    差值哈希算法相较于均值哈希算法,前期和后期基本相同,只有中间比较hash有变化。

    步骤:

    1. 缩放:图片缩放为8*9,保留结构,除去细节。
    2. 灰度化:转换为灰度图。
    3. 求平均值:计算灰度图所有像素的平均值。
    4. 比较:像素值大于后一个像素值记作1,相反记作0。本行不与下一行对比,每行9个像素, 八个差值,有8行,总共64位
    5. 生成hash:将上述步骤生成的1和0按顺序组合起来既是图片的指纹(hash)。
    6. 对比指纹:将两幅图的指纹对比,计算汉明距离,即两个64位的hash值有多少位是不一样 的,不相同位数越少,图片越相似。

    感知哈希算法

    均值哈希算法过于严格,不够精确,更适合搜索缩略图,为了获得更精确的结果可以选择感知哈希 算法,它采用的是DCT(离散余弦变换)来降低频率的方法。

    步骤:

    1. 缩小图片:32 * 32是一个较好的大小,这样方便DCT计算
    2. 转化为灰度图:把缩放后的图片转化为灰度图。
    3. 计算DCT:DCT把图片分离成分率的集合
    4. 缩小DCT:DCT计算后的矩阵是32 * 32,保留左上角的8 * 8,这些代表图片的最低频率。
    5. 计算平均值:计算缩小DCT后的所有像素点的平均值。
    6. 进一步减小DCT:大于平均值记录为1,反之记录为0.
    7. 得到信息指纹:组合64个信息位,顺序随意保持一致性。
    8. 最后比对两张图片的指纹,获得汉明距离即可。

    代码实现:均值哈希算法和差值哈希算法

    import cv2
    import numpy as np
     
    #均值哈希算法
    def aHash(img):
        #缩放为8*8
        img=cv2.resize(img,(8,8),interpolation=cv2.INTER_CUBIC)
        #转换为灰度图
        gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
        #s为像素和初值为0,hash_str为hash值初值为''
        s=0
        hash_str=''
        #遍历累加求像素和
        for i in range(8):
            for j in range(8):
                s=s+gray[i,j]
        #求平均灰度
        avg=s/64
        #灰度大于平均值为1相反为0生成图片的hash值
        for i in range(8):
            for j in range(8):
                if  gray[i,j]>avg:
                    hash_str=hash_str+'1'
                else:
                    hash_str=hash_str+'0'            
        return hash_str
     
    #差值感知算法
    def dHash(img):
        #缩放8*9
        img=cv2.resize(img,(9,8),interpolation=cv2.INTER_CUBIC)
        #转换灰度图
        gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
        hash_str=''
        #每行前一个像素大于后一个像素为1,相反为0,生成哈希
        for i in range(8):
            for j in range(8):
                if   gray[i,j]>gray[i,j+1]:
                    hash_str=hash_str+'1'
                else:
                    hash_str=hash_str+'0'
        return hash_str
     
    #Hash值对比
    def cmpHash(hash1,hash2):
        n=0
        #hash长度不同则返回-1代表传参出错
        if len(hash1)!=len(hash2):
            return -1
        #遍历判断
        for i in range(len(hash1)):
            #不相等则n计数+1,n最终为相似度
            if hash1[i]!=hash2[i]:
                n=n+1
        return n
     
    img1=cv2.imread('lenna.png')
    img2=cv2.imread('lenna_noise.png')
    hash1= aHash(img1)
    hash2= aHash(img2)
    print(hash1)
    print(hash2)
    n=cmpHash(hash1,hash2)
    print('均值哈希算法相似度:',n)
     
    hash1= dHash(img1)
    hash2= dHash(img2)
    print(hash1)
    print(hash2)
    n=cmpHash(hash1,hash2)
    print('差值哈希算法相似度:',n)
    
    

    运行结果:

    输入:
    在这里插入图片描述
    在这里插入图片描述
    输出:
    在这里插入图片描述

    图像相似度比较哈希算法

    三种算法的比较:
    • aHash:均值哈希。速度比较快,但是常常不太精确。
    • pHash:感知哈希。精确度较高,但是速度方面较差一些。
    • dHash:差值哈希。精确度较高,且速度也非常快。
    • 均值哈希本质上是对颜色的比较;
    • 感知哈希由于做了 DCT 操作,本质上是对频率的比较;
    • 差值哈希本质上是基于渐变的感知哈希算法。

    展开全文
  • 主要介绍了用Python实现通过哈希算法检测图片重复的教程,这个方法被Iconfinder用作防盗版技术,需要的朋友可以参考下
  • sm3哈希算法.rar

    2020-12-26 01:37:11
    sm3哈希算法.rar
  • #资源达人分享计划#
  • 哈希
  • 为了提高图像哈希方法的鲁棒性,提出一种基于 BP神经网络的新型图像哈希算法,首先利用图像像素 矩阵和构造的函数来训练BP神经网络,再将图像进行离散小波变换,利用低频分量来组成矩阵,最后利用已经训 练好的 BP神经...
  • 算法将3D卷积神经网络与哈希学习方法结合应用于视频数据,既能快速学习视频时空特征表示,又能极大地缩短视频检索时间。在常用视频数据集上的实验结果表明,利用所提出的方法对视频进行相似性检索性能优于当前主流...
  • 该压缩包包含编译方式,示例代码,只需拍两张图片即可比较,比较打印输出值小于10,即为相似图片。使用改代码的用户linux系统必须先安装opencv环境.
  • 运行平台:VS 2019 一致性哈希算法演示项目,演示新增节点key分布情况;移除节点key分布情况! C#,C#,C#.......
  • SHA256哈希算法VB源码

    2018-12-15 21:39:42
    VB6.0语言,SHA256哈希算法源码,做成函数,可以直接调用!!
  • 数据结构之哈希算法

    2022-03-04 18:18:09
    1:什么是哈希算法? 将一个任意长度的二进制串映射为固定长度的二进制串的算法,我们叫做是哈希算法,其中固定长度的二进制串结果叫做哈希值。 比如md5算法就是一种哈希算法,md5算法将任意长度的二进制串映射为...

    1:什么是哈希算法?

    将一个任意长度的二进制串映射为固定长度的二进制串的算法,我们叫做是哈希算法,其中固定长度的二进制串结果叫做哈希值。

    比如md5算法就是一种哈希算法,md5算法将任意长度的二进制串映射为长度128bit的二进制串。

    2:一个合格的哈希算法需要满足哪些条件?

    1:哈希冲突概率极低
    2:差别很小的原始串哈希的结果差别也要很大
    3:哈希计算速度快(如md5算法加密4000个字左右的汉字只需要1ms左右)
    4:无法反向从哈希值推到出原始值
    

    3:哈希算法都有哪些应用?

    A:加密(密码存储)
    B:唯一标示(数据库主键,文件存储)
    C:数据校验(接口请求数据有效性)
    D:散列函数(散列表生成散列值)
    E:负载均衡
    F:数据分片
    G:分布式存储
    

    4:为什么哈希算法无法做到无冲突?

    借鉴鸽巢原理(抽屉原理),假设有10个鸽巢,11只鸽子,每个鸽子下一个鸽子蛋,则至少有一个鸽巢鸽子蛋的数量不少于2,在1:什么是哈希算法?部分我们分析了哈希算法的定义,从中可以看出哈希值是一个定长的结果,因此哈希值结果个数必定存在上限,比如md5算法,哈希值长度为128bit,也就是哈希值一共有2^128次方个可能的值,则根据鸽巢原理,当有2^128+1个原始串时,必定会出现冲突,但是出现冲突的概率极低。

    5:哈希算法在分布式的应用实例

    为了提高系统的查询性能,我们现在需要构建一个分布式的缓存系统,前端系统通过分布式缓存系统来获取数据,可以达到减少数据库查询的目的,架构如下图:

    在这里插入图片描述

    这样子,一个简单的分布式缓存系统就构建完毕了,注意图中的步骤2,假设我们使用的是md5算法执行哈希,则可能的代码如下:

    class FakeCls {
        int hash(String userId) {
            // 分布式缓存系统中一共有10个节点
            int cacheSystemNodeNum = 10;
            return Md5(userId) % cacheSystemNodeNum;
        }
    }
    

    需要注意,哈希值的计算严重依赖于了分布式缓存系统中节点的个数,当节点个数发生变更时,该函数的结果必定发生比较大的变化,从而造成将请求分配到了无对应缓存数据的节点,此时大量的请求都会打到DB,从而造成缓存雪崩的发生。

    延伸知识:缓存雪崩,缓存击穿,缓存穿透。

    缓存雪崩:当突然大规模的出现无法从缓存中获取数据的情况时,请求全部打到了DB,从而造成DB的宕机,这是缓存雪崩。

    缓存击穿:当某个热点key失效,导致获取该热点key的请求打到DB,这是缓存击穿。

    缓存穿透:当查询的key在缓存中不可能存在,此时一定会将请求打到DB,这是缓存穿透。

    想要解决这个问题就不能使用普通的哈希函数,而需要考虑使用一致性哈希了,关于一致性哈希具体参考6:一致性哈希,使用一致性hash后,步骤2的伪代码如下:

    class FakeCls {
        int hash(String userId) {
            return someConsistencyHash(userId);
        }
    }
    

    这样,当节点发生变更,影响的也只是部分键哈希的结果,不会造成特别严重的后果,经过一段时间的自动预热(即将缓存中不存在key查询之后放到缓存中)之后,就能恢复正常了。

    6:一致性哈希

    一致性哈希依赖于哈希环,哈希环是一个具有一定范围的环,机器节点和数据都会被映射到环上的某个位置,如下是一个范围是[1,10000]的环:

    在这里插入图片描述

    比如我们现在有三个节点,哈希值分别如下:

    节点1:508
    节点2:6010
    节点3:2056
    

    则我们将这三个节点映射到哈希环上之后,如下图:

    在这里插入图片描述

    接下来数据查找过程是这样子的,首先经过哈希函数获取[1,10000]内的一个数字,按照如下两种情况处理:

    1:如果是当前哈希值对应的位置恰好有映射的节点,则使用该节点查询数据
    2:如果是当前哈希值没有映射的节点,则顺时针旋转,使用第一个遇到的节点,作为目标节点来查询数据
    

    比如我们现在要查询用户ID=20201303-1对应的用户信息,假设hash(20201303-1)=5632,则会使用节点2,来作为目标节点查找数据,这个过程如下图:

    在这里插入图片描述

    但是此时还是有一个问题,那就是,节点映射是失衡的,如下的映射关系:

    [509,2056]映射到node3,可映射的哈希值个数为1548。
    [2057,6010]映射到node2,可映射哈希值个数为3954。
    [6011,10000],[1,508]映射到node1,可映射的哈希值个数是4498。
    

    则映射到各个节点的比例为node1:node2:node3=4498:3954:1548,可以看到这个比例并不是接近1:1:1的,为了解决这个问题,我们可以将这3个节点都克隆若干份,然后再映射到哈希环上,这个克隆的副本我们叫做是虚拟机节点,增加虚拟节点后哈希环可能如下:

    在这里插入图片描述

    这样子就能解决映射不均匀的问题了。回过头看,在5:哈希算法在分布式的应用实例我们提到可以使用一致性哈希来解决机器节点个数发生改变导致的雪崩问题,这是为什么呢?接上图,假设我们现在增加了节点4,哈希环变为下图:

    在这里插入图片描述

    此时受影响的哈希范围是[2057,2789],原来是映射到node1,现在映射到node4,[6529,7923]原来映射到node3,现在映射到node4,可以看到影响的范围还是比较小的,基于此来解决缓存雪崩问题。

    以上使用虚拟节点的算法其实是ketama一致性哈希算法。

    展开全文
  • SM3哈希算法的硬件实现与研究.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 283,185
精华内容 113,274
关键字:

哈希算法