秒懂Hash算法(一):什么是Hash
Hash函数
在一般的线性表、树结构中,数据的存储位置是随机的,不像数组可以通过索引能一步查找到目标元素。为了能快速地在没有索引之类的结构中找到目标元素,需要为存储地址和值之间做一种映射关系h(key),这个h就是哈希函数,用公式表示:
h(key)=Addr
h:哈希函数
key:关键字,用来唯一区分对象的
把线性表中每个对象的关键字通过哈希函数h(key)映射到内存单元地址,并把对象存储到该内存单元,这样的线性表存储结构称为哈希表或散列表。
构造哈希函数
构造哈希函数的方法有很多种,下面介绍几种常见的算法。在设置哈希函数时,通常要考虑以下因素:
○ 计算函希函数所需的时间
○ 关键字的长度
○ 哈希表的长度
○ 关键字的分布情况
○ 记录的查找频率
1. 直接定址法
直接定址法取关键字或关键字的某个线性函数作为哈希地址,即
h(key) = key
或
h(key) = a*key + b
其中a,b为常数,调整a与b的值可以使哈希地址取值范围与存储空间范围一致。这种方法简单并且不会发生冲突,适用于关键字分布基本连续的情况,若关键字分布不连续,将造成存储空间的巨大浪费。
2. 数字分析法
数字分析法是提取关键字中随机性较好的数字位,将其拼接作为哈希地址,适用于所有关键字已知的情况,并需要对关键字中每位的取值情况进行分析。如下图,经分析c,f,g,h这几位取值较为集中,随机性不好,不适用于哈希函数,而a,e取值分散,可将这两个数字拼接位哈希地址。需要注意,提取多少位数字应该根据哈希表长度来确定。
位 h g f e d c b a 提取结果
6 1 3 1 7 6 3 2 12
6 2 3 2 6 8 7 5 25
6 2 3 4 3 6 3 4 44
6 2 7 0 6 6 1 6 6
6 1 7 7 4 6 3 8 78
6 1 3 8 1 2 6 1 81
6 1 3 9 4 2 2 0 90
3. 除留余数法
除留余数法采用取模运算,把关键字除以某个不大于哈希表表长的整数得到的余数作为哈希地址。哈希函数形式为:
h(key) = key % p
除留余数法的关键是选好P,使得记录集合中的每个关键字通过该整数转换后映射到哈希表范围内任意地址上的概率相等,从而尽可能减少发生冲突的可能性。
例如,P不要设为2的次幂,如设P=25,则对P的取模相当于截取P的最低5位二进制数,这等于将关键字的所有高位二进制数都忽略了。理论研究表明,P取奇数比偶数效果好,P取不大于哈希表长度的质数效果最好。
507683的二进制 11110111111001
507683%2相当于取低5位二进制数
最新文章
- 提升 LaTeX 效率的小工具:Detexify LaTeX handwritten symbol recognition
- 测试常用SQL注入语句大全
- Mysql数据库的使用经验总结
- SQL SERVER with递归示例一则
- 8款超酷而实用的CSS3按钮动画
- 反射机制及开源框架xUitls的使用,使用HttpUtils通过断点续传下载文件
- BZOJ1537: [POI2005]Aut- The Bus
- cf459B Pashmak and Flowers
- erp crm oa
- jvm栈-运行控制,jvm-堆运行存储共享单元
- Tutorial 01_熟悉常用的Linux操作和Hadoop操作
- 如何在Rails6内通过Webpacker使用JavaScript; flatpicker日期时间组件选择器
- Android开发利器之Data Binding Compiler V2 —— 搭建Android MVVM完全体的基础
- [书籍]用UWP复习《C#并发编程经典实例》
- CF1108F MST Unification
- 使用gulp和bable实现实时编译ES6代码
- 重写&;重载
- MPVUE - 使用vue.js开发微信小程序
- myeclipse debug不显示变量值解决的方法
- 在SpringMVC Controller中注入Request成员域
热门文章
- 【Android工具类】用户输入非法内容时的震动与动画提示——EditTextShakeHelper工具类介绍
- WCF寄宿与IIS里时遇到的问题
- QT 内存文件映射就是如此简单!
- UVE开发环境搭建及项目启动
- 带参跳转其他controller
- wpf中防止界面卡死的写法
- p标签内不能嵌套div(注解)
- Qt 事件处理 快捷键(重写eventFilter的函数,使用Qt::ControlModifier判断)
- android adb socket 通信
- Arch Linux 是个 针对 i686 优化的 Linux 发行版(通过可以轻松使用的二进制包系统 - pacman)