投稿    登录
欢迎来访~

浅入浅出Hash算法

Other Payne 1363浏览 0评论

扫码或搜索:进击的Coder

发送

即可立即永久解锁本站全部文章

本文预计阅读需3min

你好,我是你老朋友Payne,大家都或许过我之前写的水文-JS解密入门,没看过的童鞋开源回头看看啊。里面主要讲述了Hash MD5的例子,以及加密与解密,相关的。那么今天我们去搞一下MD5的“父亲”, Hash。主要阐述了什么是哈希,哈希运用方向以及hash碰撞及解决方向,请查阅

Hash算法

哈希

(hash)也叫散列。Hash算法,是将一个不定长的输入,通过散列函数变换成一个定长的输出,即散列值。

应用

Hash主要应用在数据结构以及密码学领域。

数据结构:

使用Hash算法的数据结构叫做哈希表,也叫散列表,主要是为了提高查询的效率。它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数就是hash function,存放记录的数组叫做哈希表。

在数据结构中应用时,有时需要较高的运算速度而弱化考虑抗碰撞性,可以使用自己构建的哈希函数。

密码学:

这种hash散列变换是一种单向运算,具有不可逆性即不能根据散列值还原出输入信息,因此严格意义上讲Hash算法是一种消息摘要算法,不是一种加密算法。常见的hash算法有:SM3、MD5、SHA-1等 。

在不同的应用场景下,hash函数的选择也会有所侧重。比如在管理数据结构时,主要要考虑运算的快速性,并且要保证hash均匀分布;而应用在密码学中就要优先考虑 抗碰撞性 ,避免出现两段不同明文hash值相同的情况发生。

哈希碰撞:

不同的值经过Hash function得到同一值则产生哈希碰撞防止哈希碰撞的最有效方法,就是扩大哈希值的取值空间

hash碰撞解决办法:

1. 开放地址法

  1. 线性探测再散列
  2. 二次探测再散列
  3. 伪随机探测再散列
  4. 再哈希法

再哈希法又叫双哈希法,有多个不同的Hash函数,当发生冲突时,使用第二个,第三个,….,等哈希函数去计算地址,直到无冲突。
虽然不易发生聚集,但是增加了计算时间。

  1. 链地址法(Java hashmap)

链地址法的基本思想是:每个哈希表节点都有一个next指针,多个哈希表节点可以用next指针构成一个单向链表,将所有关键字为同义词的结点链接在同一个单链表中,

  1. 建立公共溢出区

建立公共溢出区的基本思想是:假设哈希函数的值域是 [1,m-1],则设向量 HashTable[0…m-1] 为基本表, 每个分量存放一个记录,另外设向量 OverTable[0…v] 为溢出表,所有关键字和基本表中关键字为同义词的记录,不管它们由哈希函数得到的哈希地址是什么,一旦发生冲突,都填入溢出表。

转载请注明:静觅 » 浅入浅出Hash算法

更多文章、联系博主、技术交流、商务合作

扫码或搜索:进击的Coder

进击的Coder

微信公众号 扫一扫关注

喜欢 (3)or分享 (0)

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请狠狠点击下面的

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址