字符串哈希的研究
关于hash函数,其存在的理由就是让存入的数据得到好的立足之地(就像给存入的数据一个唯一的门牌号,我们就可以很容易的找到它所在地点),而且不让数据扎堆也是很重要的(而不是让数据扎堆,毕竟在一间几十上百号人的屋子找个人相对比较困难的)。
由此,hash函数应该,也必须要让数据“散开”,数据不必争房子住,如此冲突就少了,社会也就和谐了。
以下为hash设计历程:(一步一步、做足苦力啊!先贴代码,然后是自己的一点分析,再后是测试的统计数据)
设计1:
private int FirstHash(String str){
char[] chars = str.trim().toCharArray();
int hash = 0;
int count = 0;
int length = chars.length;
while (count < length) {
hash = (int) chars[count] + (hash << 8) + (hash << 16);
count++;
}
return hash & 0x7FFFFFFF;
}
设计2:
while (count < length) {
hash = (int) chars[count] + (hash << 8) + (hash << 16) – hash;
count++;
}
设计3:(只改动了一个数据哦!!!)
while (count < length) {
hash = (int) chars[count] + (hash << 7) + (hash << 16) – hash;
count++;
}
设计4:
while (count < length) {
hash = (int) chars[count] + (hash << 7) + (hash << 16) + (hash << 24) – hash;
count++;
}
附:hashSet、hashMap的哈希函数(以便比较)
private int SystemHash(String s) {
int hash = s.hashCode();
hash ^= (hash >>> 20) ^ (hash >>> 12);
return (hash ^ (hash >>> 7) ^ (hash >>> 4));
}
必须说明:现在只测试“英文单词”为存入的数据对象。
分析:
刚开始想到设计1是根据字符的二进制编码的。Java中char型数据是2 byte。但想到超过ASCLL值256的char型数据没法手工输入(我试了一下,char型数据超过256的都打印个“?”),最常用的英文单词实际上就是char数组,每个字母必不超过256。说了这么多,只想说明此时一个字母虽然是2 byte,但是变成二进制的话只有低8位存数据,高8位就都是 0 了。
OK,上面的前提是解释我的测试的铺垫。
将上面的32位存储结构分为四份(即将一个int型数据8位8位的分为四份,并分别标号为1、2、3、4)。
假如现在有一个数组a,数组存有5个元素,假设为“12345”,设计1的哈希过程是这样的:
最终插入“12345”完成!!!
这个设计在存储数据少的时候还是比较让人满意的,但是,一看这个表格,顿时就惊呆了,这个表格说明了什么——加入hash表的长度为1000,那么取余后得到的索引位置只与存入的字符串的最后2个字母有关!!!那肯定是不行的,加入有“abcde”和“cbade”存入,那肯定得撞车了。
然后,稍微改进了一下,得到设计2:
同样的有:
嗯,现在好多了,3、4两个低位都与整个数组元素扯上了关系,当再加入“abcde”和“cbade”后,再撞车已经几乎不可能发生了。
现在想想,既然扯关系,那不如把关系扯得错综复杂一点,然后就得到设计3:把“hash<<8”改为“hash<<7”,即标号4的低位模块的数据没有全部移到标号3的模块,而是插一腿到原来自己呆的模块。此时,额,已经很难追寻踪迹了。。。
那设计4怎么又加上“hash<<24”呢?很简单,就是让hash更复杂,但这个复杂是有道理的,目的就是让标号1和2的模块也与存入的整个字符串扯上关系(由表可见,标号1的模块只与少数字符数组关联),自此,便可大胆提出类似巴赫猜想的假设:如果字符数组的长度越长,那么设计4的散列效果肯定比较好。
下表为根据运行结果得到的统计数据:
现在只能看着数据发呆了,不管怎么说,还是能得到些信息的:
1. 设计2和设计4的数据基本一样,也就是说“hash<<8”和“hash<<7”是差不多的,“hash<<7”并不能增加散列效果;
2. 在哈希表容量少、插入数组短的时候,自己的设计还是可以的,但是容量大、插入数据长的时候,那就比较劣了。
3. “hash<<24”这一句并没有给设计4带来长数组的散列效果。(唉,有时候,猜想没有得到 验证也是很痛苦的)。
4. 最重要的一点:我输了,彻底的输了,平均下来,系统的hash函数就远远抛下了我写的hash,特别是容量更大、数组长度更长的时候,差距就更明显了。
不过,没有绝对好的hash,只有相对合适的hash。
探索路程,依然的,在路上……
- 大小: 2.9 KB
- 大小: 11.7 KB
- 大小: 7.1 KB
- 大小: 6.9 KB
分享到:
相关推荐
面向大规模特征集的字符串匹配技术在病毒检测、内容过滤等问题上的应用愈加广泛,而短模式串一直是阻碍性能提升的重要瓶颈。针对短模式串进行分析讨论,基于跳跃算法优化,采用了动态块大小和动态Hash处理以及Hash...
该算法采用自底向上的机制,对目标位置的Geohash编码进行字符串模糊查询来确定组成匿名区域的[k-1]个近邻,在扩大扫描区域时,对请求用户所在网格以及周边网格跨域扫描,然后再进行层级的递归,同时使用[Lmax]和[Lm...
“Hash将一段数据(小数据或大数据)转换成一段相对短小的数据,如字符串或整数。” 这是依靠单向hash函数来完成的。所谓单向是指很难(或者是实际上不可能)将其反转回来。一个常见的hash函数的例子是md5(),它...
通过对Peer wire协议、TCP-Tracker协议、UDP-Tracker协议、DHT(Distributed Hash Table,分布式哈希表)协议和实际网络流量的分析,找出各协议中的特征字符串,从而利用特征字符串匹配对BT明文流量进行识别。...
字符串处理单元,完全兼容宽字节处理(即使用wideString),特有的中文字符串处理函数(如简繁转换等等),经过多次优化,大多以编表的方式进行处理(一般来说是最快的处理方式)。 BiosHelp.pas 读取Bios信息的...
2.字符串的顺序及链式存储结构、相关运算的算法实现 本章自学 第五章 数组和广义表 4 1.多维数组的表示及运算 2.数组的存储映像、矩阵的压缩存储 3.广义表的定义和存储结构 掌握基本内容 多媒体课件 1 2 1 ...
StrFuncs.pas 字符串处理单元,完全兼容宽字节处理(即使用wideString),特有的中文字符串处理函数(如简繁转换等等),经过多次优化,大多以编表的方式进行处理(一般来说是最快的处理方式)。 BiosHelp.pas...
[原网页] 程序员编程艺术第三十~三十一章:字符串转换成整数,通配符字符串匹配 [原网页] 程序员编程艺术第二十八~二十九章:最大连续乘积子串、字符串编辑距离 [原网页] 数据挖掘中所需的概率论与数理统计知识、...
基本数据结构 基本数据结构部分包括线性表、堆栈与队列、数组、字符串、整数集合类、树(包括AVL树、伸展树等)、图(包括网络流等问题的讨论)、散列(Hash)等 典型算法 典型算法部分主要介绍了若干典型算法的实现...
计算机找工作必备基础概念(逗逼篇...java 内部类的创建和使用操作系统:linux 常用命令linux 中如何查找替换字符串linux 中防火墙 iptables 是如何工作的?如何使用 linux 定时任务?linux 文件系统研究linux 权限lin
+ [字符串匹配](#字符串匹配) * [动态规划](#动态规划) + [动态规划](#动态规划-1) + [状态压缩](#状态压缩) + [状态设计](#状态设计) + [树形DP](#树形dp) + [优化](#优化-1) * [计算几何](#计算几何) + ...
但这里有个致命问题——不管是火龙还是war3,不可能预知到游戏过程中全部的文件读取,更确切说,全部的字符串。如果字符串是明文写在脚本中,如“sound\\aaa.mp3”,那么火龙会认为这可能是个文件,然后顺藤摸瓜找到...
将原始形态的统一资源定位符字符串,解析为服务器域名、资源路径、服务器 IP地址,乃至服务器通信端口等。WEBCRAWLER 网络爬虫实训项目 8 2.2.5. 统一资源定位符队列(UrlQueues) 封装原始统一资源定位符队列和解析...
唯独这个加密的密码我们不好处理,因为我们必须把密码转换为加密方式,其实,QQ密码的加密方式也是非常简单的,先用MD5的HASH进行一次加密,然后把结果再用一次Base64加密即可得到这个加密字符串,有了这个信息,...
7.2.3 字符串过滤程序 256 7.2.4 整数溢出 256 7.2.5 类型转换错误 260 7.3 案例研究:IIS索引服务漏洞 262 7.3.1 CVariableSet:: 7.3.1 AddExtensionControlBlock 263 7.3.2 DecodeURLEscapes 267 7.4 结论 271 第8...
哈希计算工具 java-hash 用来计算 MD5、SHA 哈希算法的 Java 类库,支持 "MD5", "SHA", "SHA-1", "SHA-256", "SHA-384", "SHA-512". 高性能RPC框架 nfs-rpc nfs-rpc是一个集成了各种知名通信框架的高性能RPC框架,...