我已授权

注册

一文告诉你哈希思想与哈希表构造到底是什么

2020-03-10 12:04:17 和讯区块链 

  Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。

  今天我们就一起来探索一下,哈希最底层的奥秘。

  哈希概念

  构造一种储存结构,通过某种函数,使得其元素的储存位置与他的关键码之间能够建立一一映射关系,那么在查找时通过该函数很快找到相应元素。

  简言之,就是设定某一固定函数(hashFunc),通过此函数来使插入元素的值与元素位置相对应,往后我们需要查找此元素时就可以通过此函数(hashFunc)找到该值。

  哈希函数

  散列函数(英语:Hash function)又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。

  该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。

  哈希函数使得计算出来的地址均匀分布在整个空间。

  插入及搜索元素

  根据待插入元素的关键码,根据哈希函数计算出其存储位置。

  我们用除留余数法的哈希函数进行介绍:

  例: 现有 1 ,3,4,5,6,9几个数进行储存,将n%10求模运算的结果作为哈希地址进行元素插入。

一文告诉你哈希思想与哈希表构造到底是什么

  若想查找某一元素时,则只需要对查找元素进行哈希函数运算,得到其存放地址,就能找到该元素。

  哈希冲突

  当出现插入一个元素,其根据哈希函数计算出的地址,已经被其他元素占用的情况称为哈希冲突。

  如:

  为了能更好的识别当前位置是否被占用,我们需要对每个位置进行标记

一文告诉你哈希思想与哈希表构造到底是什么

  注意:如果我们要删除某一元素时,不能将其直接删除,如果直接删除,会对当前结构产生影响,导致其他元素的搜索出错,所以当我们要删除一个元素时,需要将其标记为删除,而非空。

一文告诉你哈希思想与哈希表构造到底是什么

  开散列

  开散列又称链地址法,首先对关键码集合用哈希函数计算哈希地址,当具有相同地址的关键码时,将所有同一地址的元素,通过单链表的形式链接起来,而各链表的头结点存储在哈希表中。

一文告诉你哈希思想与哈希表构造到底是什么

  这下,你该了解哈希的思想和哈希表构造了吧?

  本文来源:区块链大本营,不代表和讯网官方观点。

(责任编辑:张雅洁 HF083)
看全文
写评论已有条评论跟帖用户自律公约
提 交还可输入500

最新评论

查看剩下100条评论

和讯热销金融证券产品

【免责声明】本文仅代表作者本人观点,与和讯网无关。和讯网站对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考,并请自行承担全部责任。