草庐IT

区块链前置知识之Hash (一)

这波能反杀丶 2023-03-28 原文

定义

hash 是一种把任意长度输入变换成固定长度输出的一种算法。

假设我们已经定义了一个 hash 函数名为 H,输入内容为 message,输出内容为 x,那么就有如下公式。

H(message) = x
这是一个压缩的过程,通常情况下,我们会把输出值称之为 hash 值。

接下来通过一个具体的案例来了解 hash 的过程。

我们定义这样一个场景,约定任意正整数,要存放在长度为 6 的数组中,那么此时,我们可以利用 hash 的思想设计什么样的方案来做到这个事情呢?

数组的具体位置我们可以用下标来表示 0, 1, 2, 3, 4, 5。想要将任意正整数放入到数组中,那么我们只需要设计一个函数,输入值为任意正整数,输出值为该数组下标中的任意一个即可,得到了输出值,我们就相当于知道应该把输入值放到数组中的某个位置了。

我们可以使用求余法来定义这个 hash 函数。

function suplus(number) {
return number % 6
}
于是,随便取几个数,得到 hash 值之后就能存入数组对应的位置。

// 输入值:61
suplus(61) = 1

// 输入值:101
suplus(101) = 5

此时的哈希值表示的是数组的下标,因此在很多应用场景,输出结果哈希值也被称为哈希地址。

哈希碰撞

在上面的例子中,输入值的范围一定大于输出值的范围,这是 hash 的重要特性之一。因此在某些情况下,不同的输入会得到相同的输出结果。

// 不同的输入,得到了相同的输出,哈希地址相同
suplus(7) = 1
suplus(61) = 1
此时哈希地址相同,按照规则,我们不得不把不同的值,存入相同的位置,这种情况就被称之为哈希碰撞(collision)。

解决哈希碰撞的方法很多,这里介绍一个比较常见的方法:以数组的每个地址为根节点,构建一个新的链表。

例如当输入数字分别为 7, 61 时。

但是当数据量庞大时,链表的查询速度比较低效,因此我们在实践中,会将链表替换成红黑树等操作效率更高的数据结构。

当然,最理想的情况是输出范围足够广,不出现 hash 碰撞。因此我们实践中使用的 hash 函数,输出值的范围都非常庞大,例如早期用得比较多的 md5,现在使用比较多的sha256:比特币中使用的哈希算法。但是由于输入值范围一定大输出值范围,因此理论上哈希碰撞一定会存在。

现在 md5 已经可以人为制造 hash 碰撞,因此实用性大大降低。

本文转载自微信公众号「这波能反杀」,可以通过以下二维码关注。转载本文请联系这波能反杀公众号。

有关区块链前置知识之Hash (一)的更多相关文章

  1. ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2

    在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中,它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has

  2. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据,就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理?我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题;这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML,但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中,将我的XML代码修改为

  3. ruby - Ruby 的 Hash 在比较键时使用哪种相等性测试? - 2

    我有一个围绕一些对象的包装类,我想将这些对象用作散列中的键。包装对象和解包装对象应映射到相同的键。一个简单的例子是这样的:classAattr_reader:xdefinitialize(inner)@inner=innerenddefx;@inner.x;enddef==(other)@inner.x==other.xendenda=A.new(o)#oisjustanyobjectthatallowso.xb=A.new(o)h={a=>5}ph[a]#5ph[b]#nil,shouldbe5ph[o]#nil,shouldbe5我试过==、===、eq?并散列所有无济于事。

  4. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么? 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设? 关于java-等价于Java中的RubyHash,我们在StackOverflow上找到一个类似的问题: https://stackoverflow.com/questions/22737685/

  5. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息,信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同,算法可以分为对称加密、非对称加密、对称加密和非

  6. ruby - 如何将 lambda 传递给 Hash.each? - 2

    如何将lambda传递给hash.each,以便我可以重复使用一些代码?>h={a:'b'}>h.eachdo|key,value|end=>{:a=>"b"}>test=lambdado|key,value|puts"#{key}=#{value}"end>test.call('a','b')a=b>h.each&testArgumentError:wrongnumberofarguments(1for2)from(irb):1:in`blockinirb_binding'from(irb):5:in`each'from(irb):5from/Users/jstillwell/.rv

  7. Ruby:行 "m = Hash.new {|h,k| h[k] = []}"完成了什么而 "Hash.new"没有完成? - 2

    一边学习thisRailscast我从Rack中看到了以下源代码:defself.middleware@middleware||=beginm=Hash.new{|h,k|h[k]=[]}m["deployment"].concat[[Rack::ContentLength],[Rack::Chunked],logging_middleware]m["development"].concatm["deployment"]+[[Rack::ShowExceptions],[Rack::Lint]]mendend我的问题是关于第三行。什么是传递block{|h,k|h[k]=[]}到Has

  8. ruby-on-rails - 在 Ruby 或 Rails 中,hash.merge({ :order => 'asc' }) can return a new hash with a new key. 什么可以返回带有已删除键的新散列? - 2

    在Ruby(或Rails)中,我们可以做到new_params=params.merge({:order=>'asc'})现在new_params是一个带有添加键:order的散列。但是是否有一行可以返回带有已删除key的散列?线路new_params=params.delete(:order)不会工作,因为delete方法返回值,仅此而已。我们必须分3步完成吗?tmp_params=paramstmp_params.delete(:order)returntmp_params有没有更好的方法?因为我想做一个new_params=(params[:order].blank?||para

  9. ruby - 我怎样才能更好地了解/了解更多关于 Ruby 的知识? - 2

    按照目前的情况,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visitthehelpcenter指导。关闭9年前。我最近开始学习Ruby,这是我的第一门编程语言。我对语法感到满意,并且我已经完成了许多只教授相同基础知识的教程。我已经写了一些小程序(包括我自己的数组排序方法,在有人告诉我谷歌“冒泡排序”之前我认为它非常聪明),但我觉得我需要尝试更大更难的东西来理解更多关于Ruby.关于如何执行此操作的任何想法?

  10. ruby object.hash - 2

    一个对象的散列值是什么意思?在什么情况下两个对象具有相同的哈希值??还有说Array|Hash不能是Hashkeys,这个跟对象的hash值有关系,为什么? 最佳答案 对于要存储在HashMap或哈希集中的对象,必须满足以下条件:如果认为两个对象相等,则它们的哈希值也必须相等。如果两个对象不被认为是相等的,那么它们的哈希值应该很可能不同(两个不同的对象具有相同哈希值的次数越多,对HashMap/集合的操作性能就越差)。因此,如果两个对象具有相同的哈希值,则很有可能(但不能保证)它们相等。上面“相等”的确切含义取决于散列方法的实现者。

随机推荐