乘法散列法
作者:追风剑情 发布于:2019-1-28 12:47 分类:Algorithms
下面介绍几种常用的构造哈希函数的方法
1.直接地址法
直接地址法的哈希函数H对于关键字是数值类型的数据,直接利用关键字求得哈希地址。
H(ki)=aki+b(a、b 为常量)
在使用时,为了使哈希地址与存储空间吻合,可以调整 a和 b。例如,取 H(ki)=3*ki+5。
直接地址法的特点是哈希函数简单,并且对于不同的关键字,不会产生冲突。但在实际问题中,由于关键字集合中的元素很少是连续的,用该方法产生的哈希表会造成空间的大量浪费。因此,这种方法很少使用。
2.数字分析法
数字分析法是假设有一组关键字,每个关键字由 n 位数字组成,如 k1k2...kn。数字分析法是从中提取数字分布比较均匀的若干位作为哈希地址。
例如,对于一组关键字 k1~k8 的序列{100011211,100011322,100011413,100011556,100011613,100011756,100011822,100011911},可以取第 6 位和第 7 位作为哈希地址,即:
H(k1)=12,H(k2)=13,H(k3)=14, H(k4)=15,H(k5)=16, H(k6)=17, H(k7)=18, H(k8)=19。
3.除留余数法
除留余数法是用关键字 ki 除以一个合适的、不大于哈希表长m的正整数p所得余数作
为哈希地址的方法。对应的哈希函数 H(ki)为:
H(ki) = ki MOD p
其中,MOD 表示求余数运算符。用该方法产生的哈希函数的好坏取决于p值的选取。实践证明,当p取小于哈希表长m的某个素数时,产生的哈希函数较好。除留余数法是一种简单且行之有效的构造哈希函数的方法。
4.平方取中法
平方取中法是取关键字平方的中间几位作为散列地址的方法,具体取多少位根据实际
情况而定。即:
H(ki)=ki;的平方的中间几位
这也是一种常用的较好的设计哈希函数的方法。关键字求平方后使得它的中间几位和组成关键字的各位值均有关,从而使哈希地址的分布更为均匀,减少了发生冲突的可能性。
s指头尾要截掉的位数,平方后不足4s(即8位)位的高位补0。
5.折叠法
折叠法是首先把关键字分割成位数相同的几段(最后一段的位数可少一些),段的位数取决于哈希地址的位数,由实际情况而定,然后将它们的叠加和舍去最高进位作为哈希地址的方法。
与平方取中法类似,折叠法也使得关键字的各位值都对哈希地址产生影响。
在哈希表中,虽然冲突很难避免,但发生冲突的可能性却有大有小。这主要与 3 个因素有关。
(1)与装填因子α有关。所谓装填因子是指哈希表中已存入的记录数 n 与哈希地址空间大小 m 的比值,即α=n/m,α越小,冲突的可能性就越小;α越大(最大可取 1),冲突的可能性就越大,这很容易理解,因为a越小,哈希表中空闲单元的比例就越大,所以待插入记录同已插入存在的记录发生冲突的可能性就越小;反之,α越大,哈希表中空闲单元的比例就越小,所以待插入记录同已插入存在的记录冲突的可能性就越大;另一方面,α 越小,存储空间的利用率就越低;反之,存储空间的利用率也就越高。为了既兼顾减少冲突的发生,又兼顾提高存储空间的利用率这两个方面,通常使最终的α控制在 0.6~0.9 的范围内。
(2)与所采用的哈希函数有关。若哈希函数选择得当,就可使哈希地址尽可能均匀地分布在哈希地址空间上,从而减少冲突的发生;否则,若哈希函数选择不当,就可能使哈希地址集中于某些区域,从而加大冲突的发生。
(3)与解决冲突的哈希冲突函数有关。哈希冲突函数选择得好坏也将减少或增加发生冲突的可能性。
解决哈希冲突的方法
1.开放地址法
开放地址法又分为线性探测再散列、二次探测再散列和随机探测再散列。
假设哈希表空间为A[0...m-1],哈希函数为H(ki)。
(1) 线性探测再散列
线性探测再散列解决冲突求“下一个”地址的公式是:
d1=H(ki)
dj=(dj-1+1) MOD m j=2,3,...
(2) 二次探测再散列
二次探测再散列解决冲突求"下一个"地址的公式是:
d1=H(ki)
dj+1=(d1+j2) MOD m
该方法的缺陷是不易探查到整个散列空间。
(3) 随机探测再散列
随机探测再散列解决冲突求"下一个"地址的公式是:
d1=H(ki)
dj+1=(d1+R) MOD m
其中:
2.链地址法 当存储结构是链表时,一般采用链地址法,用链地址法处理冲突的方法是:把具有相同散列地址的关键字 值放在同一个链表中,称为同义词链表。通常把具有相同哈希地址的关键字都存放在一个同义词链表中,有m 个散列地址就有m个链表,同时用数组h[0..m-1]存放各个链表的头指针,凡是散列地址为i的记录都以结点方式插入到以 h[i]为结点的单链表中。
乘法散列公式
k: 关键字
A: 常数 (0 < A < 1)
kA mod 1: 取kA的小数部分
m: 一般选择它为2的某个幂次(m=2p)
推导公式
假设某计算机的字长为w位,而k正好可用一个单字表示。限制A=s/2w的一个分数,其中s是一个取自0<s<2w的整数。那么s=A●2w
h(k)=对r0取p个最高有效位(即,h(k)=r0>>(w-p))
A一般取下面的这个值比较理想
下面给出一个代码示例(C#版)
using System; using System.Collections.Generic; using System.Linq; using System.Text; /// <summary> /// 乘法散列法 测试 /// </summary> namespace HashTest { class Program { static void Main(string[] args) { for(int i=123454; i< 123459; i++) { Console.WriteLine("hash1 ({0})={1}", i, CalHash1(i)); Console.WriteLine("hash2 ({0})={1}", i, CalHash2(i)); } //注: 由于方案一中的A值与方案二中选的s值存在精度差,所以部分数据计算的结果不相同。 Console.Read(); } //计算方案一 public static double CalHash1(int k) { int p = 14; //选一个0-1之间的小数 double A = 0.6180339887;//(Math.Sqrt(5) - 1) / 2; //选一个2的幂次方的m值 double m = Math.Pow(2, p); //直接套用公式计算 double hash = Math.Floor(m * (k * A % 1)); return hash; } //计算方案二 (优化版) 推荐 public static int CalHash2(int k) { double s = 2654435769;//推荐值 double ks = k * s; int r0 = (int)(ks % int.MaxValue);//余数 int hash = r0 >> 18;//取高14位 (可以根据实际的存储大小调整取高几位) return hash; } } }
//计算字符串Hash public static int GetHashCode(string str) { if (string.IsNullOrEmpty(str)) return 0; //BKDR Hash ulong hash = 0; //也可以乘以31、131、1313、13131、131313.. uint p = 131; for (int i = 0; i < str.Length; i++) { //当作p进制计算,参考2进制转10进制 hash = hash * p + str[i]; } return (int)hash; }
标签: Algorithms
日历
最新文章
随机文章
热门文章
分类
存档
- 2024年10月(2)
- 2024年9月(3)
- 2024年8月(3)
- 2024年7月(11)
- 2024年6月(3)
- 2024年5月(9)
- 2024年4月(10)
- 2024年3月(11)
- 2024年2月(24)
- 2024年1月(12)
- 2023年12月(3)
- 2023年11月(9)
- 2023年10月(7)
- 2023年9月(2)
- 2023年8月(7)
- 2023年7月(9)
- 2023年6月(6)
- 2023年5月(7)
- 2023年4月(11)
- 2023年3月(6)
- 2023年2月(11)
- 2023年1月(8)
- 2022年12月(2)
- 2022年11月(4)
- 2022年10月(10)
- 2022年9月(2)
- 2022年8月(13)
- 2022年7月(7)
- 2022年6月(11)
- 2022年5月(18)
- 2022年4月(29)
- 2022年3月(5)
- 2022年2月(6)
- 2022年1月(8)
- 2021年12月(5)
- 2021年11月(3)
- 2021年10月(4)
- 2021年9月(9)
- 2021年8月(14)
- 2021年7月(8)
- 2021年6月(5)
- 2021年5月(2)
- 2021年4月(3)
- 2021年3月(7)
- 2021年2月(2)
- 2021年1月(8)
- 2020年12月(7)
- 2020年11月(2)
- 2020年10月(6)
- 2020年9月(9)
- 2020年8月(10)
- 2020年7月(9)
- 2020年6月(18)
- 2020年5月(4)
- 2020年4月(25)
- 2020年3月(38)
- 2020年1月(21)
- 2019年12月(13)
- 2019年11月(29)
- 2019年10月(44)
- 2019年9月(17)
- 2019年8月(18)
- 2019年7月(25)
- 2019年6月(25)
- 2019年5月(17)
- 2019年4月(10)
- 2019年3月(36)
- 2019年2月(35)
- 2019年1月(28)
- 2018年12月(30)
- 2018年11月(22)
- 2018年10月(4)
- 2018年9月(7)
- 2018年8月(13)
- 2018年7月(13)
- 2018年6月(6)
- 2018年5月(5)
- 2018年4月(13)
- 2018年3月(5)
- 2018年2月(3)
- 2018年1月(8)
- 2017年12月(35)
- 2017年11月(17)
- 2017年10月(16)
- 2017年9月(17)
- 2017年8月(20)
- 2017年7月(34)
- 2017年6月(17)
- 2017年5月(15)
- 2017年4月(32)
- 2017年3月(8)
- 2017年2月(2)
- 2017年1月(5)
- 2016年12月(14)
- 2016年11月(26)
- 2016年10月(12)
- 2016年9月(25)
- 2016年8月(32)
- 2016年7月(14)
- 2016年6月(21)
- 2016年5月(17)
- 2016年4月(13)
- 2016年3月(8)
- 2016年2月(8)
- 2016年1月(18)
- 2015年12月(13)
- 2015年11月(15)
- 2015年10月(12)
- 2015年9月(18)
- 2015年8月(21)
- 2015年7月(35)
- 2015年6月(13)
- 2015年5月(9)
- 2015年4月(4)
- 2015年3月(5)
- 2015年2月(4)
- 2015年1月(13)
- 2014年12月(7)
- 2014年11月(5)
- 2014年10月(4)
- 2014年9月(8)
- 2014年8月(16)
- 2014年7月(26)
- 2014年6月(22)
- 2014年5月(28)
- 2014年4月(15)
友情链接
- Unity官网
- Unity圣典
- Unity在线手册
- Unity中文手册(圣典)
- Unity官方中文论坛
- Unity游戏蛮牛用户文档
- Unity下载存档
- Unity引擎源码下载
- Unity服务
- Unity Ads
- wiki.unity3d
- Visual Studio Code官网
- SenseAR开发文档
- MSDN
- C# 参考
- C# 编程指南
- .NET Framework类库
- .NET 文档
- .NET 开发
- WPF官方文档
- uLua
- xLua
- SharpZipLib
- Protobuf-net
- Protobuf.js
- OpenSSL
- OPEN CASCADE
- JSON
- MessagePack
- C在线工具
- 游戏蛮牛
- GreenVPN
- 聚合数据
- 热云
- 融云
- 腾讯云
- 腾讯开放平台
- 腾讯游戏服务
- 腾讯游戏开发者平台
- 腾讯课堂
- 微信开放平台
- 腾讯实时音视频
- 腾讯即时通信IM
- 微信公众平台技术文档
- 白鹭引擎官网
- 白鹭引擎开放平台
- 白鹭引擎开发文档
- FairyGUI编辑器
- PureMVC-TypeScript
- 讯飞开放平台
- 亲加通讯云
- Cygwin
- Mono开发者联盟
- Scut游戏服务器引擎
- KBEngine游戏服务器引擎
- Photon游戏服务器引擎
- 码云
- SharpSvn
- 腾讯bugly
- 4399原创平台
- 开源中国
- Firebase
- Firebase-Admob-Unity
- google-services-unity
- Firebase SDK for Unity
- Google-Firebase-SDK
- AppsFlyer SDK
- android-repository
- CQASO
- Facebook开发者平台
- gradle下载
- GradleBuildTool下载
- Android Developers
- Google中国开发者
- AndroidDevTools
- Android社区
- Android开发工具
- Google Play Games Services
- Google商店
- Google APIs for Android
- 金钱豹VPN
- TouchSense SDK
- MakeHuman
- Online RSA Key Converter
- Windows UWP应用
- Visual Studio For Unity
- Open CASCADE Technology
- 慕课网
- 阿里云服务器ECS
- 在线免费文字转语音系统
- AI Studio
- 网云穿
- 百度网盘开放平台
- 迅捷画图
- 菜鸟工具
- [CSDN] 程序员研修院
- 华为人脸识别
- 百度AR导航导览SDK
- 海康威视官网
- 海康开放平台
- 海康SDK下载
交流QQ群
-
Flash游戏设计: 86184192
Unity游戏设计: 171855449
游戏设计订阅号