哈希

时间:2024-03-12 10:29:18编辑:奇事君

什么是哈希

我们先来讲个故事哈。


有一个人每次打开区块链文章,都意气风发,暗暗下决心要发愤图强,看了一会儿,发现很难看懂什么,硬逼着自己学习,却已是强弩之末,最后只能末学肤受,学了个皮毛而已。

那个人就是我哈,希望大家不要末学肤受,而能食髓知味,深刻理解区块链知识。

这四个成语。

意气风发~发奋图强~强弩之末~末学肤受

每个成语的第一个字,是前一个成语的最后一个字,组成了一个成语链的链式结构。

我们来类比一下,区块链的链式结构。


区块链0,1,2,3的链式结构是靠什么形成的呢?


是靠前一个区块的哈希值,也叫做父区块哈希值。

区块0是区块1的父区块。

区块1是区块0的子区块。

区块0的哈希值对区块1而言,就是父区块的哈希值。

父区块哈希值,就是上面成语链式结构里,把前后两个成语连接起来的那个字。

要理解区块链链式结构,还要理解什么叫哈希。


再讲个故事哈。


小黑同学要把一袋猫粮快递给大白老师。

他让哈希公司的快递员上门取件,打包完成后,拿到了快递单号。

这个寄快递的过程中,有三个关键步骤。

1.选择要寄送的物品。

2.选择哈希快递公司,对物品进行快递打包。

3.拿到快递单号。

哈希公司给的快递单号就是哈希值。

大白老师对小黑选择的哈希公司很满意。

1.不论小黑寄的东西有多大,经过哈希公司打包后,拿到手的快递包裹都一样大。

2.哈希公司打印出来的快递单号也就是哈希值,除了让你查询物流的实时状况,还可以让你知道包裹中的物品有没有被人调包或撰改。

比如小黑寄给大白的猫粮,在运送过程中,哪怕袋子上的配料表,被人改了一个标点符号,哈希公司给的快递单号,也就是哈希值都会实时发生变化,警示小黑快递包裹发生了异常情况。

哈希公司确实很厉害哈。


哈希是什么,谁能解释一下?

哈希音译自“Hash”,又名为“散列”。本质上是一种计算机程序,可接收任意长度的信心输入,然后通过哈希算法,创建小的数字“指纹”的方式。
例如数字与字母的结合,输出的就为“哈希值”。从数学术语上说,就是这个哈希函数,是将任意长度的数据,映射在有限长度的域上。总体而言,哈希函数用于,将消息或数据压缩,生成数据摘要,最终使数据量变小,并拥有固定格式。
那么哈希算法的作用又是什么呢?
(1) 在庞大的数据库中,由于哈希值更为短小,被找到更为容易,因此,哈希使数据的存储与查询速度更快。
(2) 哈希能对信息进行加密处理,使得数据传播更为安全。
哈希算法解决了什么生活问题?
看似深奥的数学函数,又或是计算机程序的哈希算法,其实跟我们的生活息息相关。就拿每年双十一的快递来说,实际上,哈希算法原理提高了快递入库出库的速度。


哈希值怎么查询

以波场为例,用户可以去TRONSCAN波场区块链浏览器(https://tronscan.org/)中,将哈希值输入搜索栏,获取相应信息。拓展资料:①哈希是英文Hash的音译,我们也可以把它译为散列,因此哈希值又称为散列值。哈希值是由哈希函数(又称散列函数/散列算法)计算而得的值。想要了解哈希值,就需要了解哈希函数的性质。哈希函数能够通过计算把任意长度的输入转换成固定长度的输出。所有哈希函数都有以下特性:只要输入值相同,则输出的哈希值是相同的;输入值不同,输出的哈希值一般是不同的,但也有极小可能性产生哈希碰撞,这时候的情况是不同的输入产生相同的输出;在输入值改动一点点的情况下,在排除哈希碰撞的情况下,会输出完全不相干的哈希值;哈希函数具有不可逆和易于验证的性质,通过想要通过输出的哈希值来倒推得到输入值几乎是不可能的,而如果有输入值,就可以立刻验证它对应的哈希值。②哈希查找的产生有这样一种背景——有些数据本身是无法排序的(如图像),有些数据是很难比较的(如图像)。如果数据本身是无法排序的,就不能对它们进行比较查找。如果数据是很难比较的,即使采用折半查找,要比较的次数也是非常多的。因此,哈希查找并不查找数据本身,而是先将数据映射为一个整数(它的哈希值),并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构造一个数组。在哈希查找的过程中,只需先将要查找的数据映射为它的哈希值,然后查找具有这个哈希值的数据,这就大大减少了查找次数。如果构造哈希函数的参数经过精心设计,内存空间也足以存放哈希表,查找一个数据元素所需的比较次数基本上就接近于一次。③基于哈希函数的上诉特性,产生了很多应用,比如比特币的区块首尾相连、算力挖矿、简单支付验证等,以及IPFS基于内容的寻址等。以后大家遇到哈希值/哈希函数的应用,不妨来回顾一下它的性质,思考一下为什么在那些地方运用哈希值/哈希函数。


哈希查找算法

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

通过某种转换关系,使关键字适度的分散到指定大小的的顺序结构中,越分散,则以后查找的时间复杂度越小,空间复杂度越高。

Hash是一种典型以空间换时间的算法,比如原来一个长度为100的数组,对其查找,只需要遍历且匹配相应记录即可,从空间复杂度上来看,假如数组存储的是byte类型数据,那么该数组占用100byte空间。现在我们采用Hash算法,我们前面说的Hash必须有一个规则,约束键与存储位置的关系,那么就需要一个固定长度的hash表,此时,仍然是100byte的数组,假设我们需要的100byte用来记录键与位置的关系,那么总的空间为200byte,而且用于记录规则的表大小会根据规则,大小可能是不定的。

通过哈希函数,我们可以将键转换为数组的索引(0-M-1),但是对于两个或者多个键具有相同索引值的情况,我们需要有一种方法来处理这种冲突。

一种比较直接的办法就是,将大小为M 的数组的每一个元素指向一个链表,链表中的每一个节点都存储散列值为该索引的键值对,这就是拉链法。下图很清楚的描述了什么是拉链法。

“John Smith”和“Sandra Dee” 通过哈希函数都指向了152 这个索引,该索引又指向了一个链表, 在链表中依次存储了这两个字符串。

单独链表法:将散列到同一个存储位置的所有元素保存在一个链表中(聚集),该方法的基本思想就是选择足够大的M,使得所有的链表都尽可能的短小,以保证查找的效率。当链表过长、大量的键都会映射到相同的索引上,哈希表的顺序查找会转变为链表的查找,查找时间将会变大。对于开放寻址会造成性能的灾难性损失。

实现基于拉链表的散列表,目标是选择适当的数组大小M,使得既不会因为空链表而浪费内存空间,也不会因为链表太而在查找上浪费太多时间。拉链表的优点在于,这种数组大小M的选择不是关键性的,如果存入的键多于预期,那么查找的时间只会比选择更大的数组稍长。另外,我们也可以使用更高效的结构来代替链表存储。如果存入的键少于预期,索然有些浪费空间,但是查找速度就会很快。所以当内存不紧张时,我们可以选择足够大的M,可以使得查找时间变为常数,如果内存紧张时,选择尽量大的M仍能够将性能提高M倍。

线性探测法是开放寻址法解决哈希冲突的一种方法,基本原理为,使用大小为M的数组来保存N个键值对,其中M>N,我们需要使用数组中的空位解决碰撞冲突。如下图所示:

对照前面的拉链法,在该图中,“Ted Baker” 是有唯一的哈希值153的,但是由于153被“Sandra Dee”占用了。而原先“Snadra Dee”和“John Smith”的哈希值都是152的,但是在对“Sandra Dee”进行哈希的时候发现152已经被占用了,所以往下找发现153没有被占用,所以索引加1 把“Sandra Dee”存放在没有被占用的153上,然后想把“Ted Baker”哈希到153上,发现已经被占用了,所以往下找,发现154没有被占用,所以值存到了154上。

单纯论查找复杂度:对于无冲突的Hash表而言,查找复杂度为O(1)。

原文: 哈希查找 - 卖贾笔的小男孩 - 博客园 (cnblogs.com)


上一篇:锂电池充电

下一篇:中英字典