其他
从哈希函数、哈希冲突、开散列出发,一文告诉你哈希思想与哈希表构造到底是什么!
作者 | 代号[K]
责编 | Carol
来源 | CSDN 博客
Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。
今天我们就一起来探索一下,哈希最底层的奥秘。
哈希概念
哈希函数
散列函数(英语:Hash function)又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。
该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。
哈希函数使得计算出来的地址均匀分布在整个空间。
插入及搜索元素
若想查找某一元素时,则只需要对查找元素进行哈希函数运算,得到其存放地址,就能找到该元素。
哈希冲突
当出现插入一个元素,其根据哈希函数计算出的地址,已经被其他元素占用的情况称为哈希冲突。
为了能更好的识别当前位置是否被占用,我们需要对每个位置进行标记
enum state{EMPTY,FULL,DELETE};
注意:如果我们要删除某一元素时,不能将其直接删除,如果直接删除,会对当前结构产生影响,导致其他元素的搜索出错,所以当我们要删除一个元素时,需要将其标记为删除,而非空。
开散列
开散列又称链地址法,首先对关键码集合用哈希函数计算哈希地址,当具有相同地址的关键码时,将所有同一地址的元素,通过单链表的形式链接起来,而各链表的头结点存储在哈希表中。
这下,你该了解哈希的思想和哈希表构造了吧?欢迎在评论区和我们分享你的想法!
即日起至 3月21日,千万流量支持原创作者,更有专属【勋章】等你来挑战
谈论新型冠状病毒、比特币、苹果公司……沃伦•巴菲特受访中的 18 个金句,值得一看! 建议收藏!告诉你以太坊交易可能经历的8个状态以及 Dapp 该如何应对 阿里华为百度三足鼎立,5G 资费高,操作系统 Linux 称王 | 中国物联网开发者真实现状报告 不看就亏系列!这里有完整的 Hadoop 集群搭建教程,和最易懂的 Hadoop 概念!| 附代码 Python数据清理终极指南(2020版) 计算机博士、加班到凌晨也要化妆、段子手……IT 女神驾到!