江苏龙网

  1. 首页 > 人文 > >

『Odaily星球日报』一文告诉你哈希思想与哈希表构造到底是什么


编者按：本文来自区块链大本营（ID：blockchain_camp） ， 作者：代号[K] ， Odaily星球日报经授权转载 。
Hash ， 一般翻译做散列、杂凑 ， 或音译为哈希 ， 是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出 ， 该输出就是散列值 。
今天我们就一起来探索一下 ， 哈希最底层的奥秘 。
哈希概念构造一种储存结构 ， 通过某种函数 ， 使得其元素的储存位置与他的关键码之间能够建立一一映射关系 ， 那么在查找时通过该函数很快找到相应元素 。
简言之 ， 就是设定某一固定函数(hashFunc) ， 通过此函数来使插入元素的值与元素位置相对应 ， 往后我们需要查找此元素时就可以通过此函数(hashFunc)找到该值 。
哈希函数散列函数（英语：Hash function）又称散列算法、哈希函数 ， 是一种从任何一种数据中创建小的数字“指纹”的方法 。 散列函数把消息或数据压缩成摘要 ， 使得数据量变小 ， 将数据的格式固定下来 。
该函数将数据打乱混合 ， 重新创建一个叫做散列值（hash values ， hash codes ， hash sums ， 或hashes）的指纹 。 散列值通常用一个短的随机字母和数字组成的字符串来代表 。
哈希函数使得计算出来的地址均匀分布在整个空间 。
插入及搜索元素根据待插入元素的关键码 ， 根据哈希函数计算出其存储位置 。
我们用除留余数法的哈希函数进行介绍：
例： 现有 1， 3 ， 4 ， 5 ， 6 ， 9几个数进行储存 ， 将n%10求模运算的结果作为哈希地址进行元素插入 。
『Odaily星球日报』一文告诉你哈希思想与哈希表构造到底是什么
本文插图
若想查找某一元素时 ， 则只需要对查找元素进行哈希函数运算 ， 得到其存放地址 ， 就能找到该元素 。 当出现插入一个元素 ， 其根据哈希函数计算出的地址 ， 已经被其他元素占用的情况称为哈希冲突 。
如：
『Odaily星球日报』一文告诉你哈希思想与哈希表构造到底是什么
本文插图
为了能更好的识别当前位置是否被占用 ， 我们需要对每个位置进行标记enum state{EMPTY,FULL,DELETE};
注意：如果我们要删除某一元素时 ， 不能将其直接删除 ， 如果直接删除 ， 会对当前结构产生影响 ， 导致其他元素的搜索出错 ， 所以当我们要删除一个元素时 ， 需要将其标记为删除 ， 而非空 。
『Odaily星球日报』一文告诉你哈希思想与哈希表构造到底是什么
本文插图
开散列开散列又称链地址法 ， 首先对关键码集合用哈希函数计算哈希地址 ， 当具有相同地址的关键码时 ， 将所有同一地址的元素 ， 通过单链表的形式链接起来 ， 而各链表的头结点存储在哈希表中 。
『Odaily星球日报』一文告诉你哈希思想与哈希表构造到底是什么
本文插图
【『Odaily星球日报』一文告诉你哈希思想与哈希表构造到底是什么】


    推荐阅读


    上一篇：『猎云网』滴滴：为全国警车安装隔离防护膜

    下一篇：专利■苹果ARKit和RealityKit技术获得专利