- 浏览: 19603 次
- 性别:
- 来自: 信阳
最新评论
-
Mybeautiful:
协议无处不在,当我跟你说“你收到我邮件后,立刻回一封。”这就是 ...
协议论 -
jcs130:
哈哈~顶~~
2011年 暑假集训(7.22~8.22)
略谈Hash
这几天自己写了个hash表,以前都是用的系统的,现在轮到自己写了,写的还是比较菜的,希望自己继续扩充吧,下面就简单介绍一下。
一、引文
先分析一下最基本的两种数据结构:数组和链表
优缺点分析:
数据结构 |
数据查找 |
数据增删 |
数组 |
数据储存地址是连续,对于查找数据时可以通过数组下标很快定位 |
需要重新分配空间,所耗时间较多 |
链表 |
数据之间只是通过一个地址在连接,查找数据时需要遍历许多不必要的数据 |
由于本身数据之间的连接是通过地址的指向,所以只需要改变一下指向 |
由上可以看出,以上两种数据结构在数据上的查找与增删都有自己的优缺点,而hash结构就是综合了两者的优点。
二、数据结构——Hash表
1).图示结构
2). 从上面的结构图可以看出,hash表整体是以数组为载体,数组内部元素以链表形式存在的,hash表所需要的就是把所要储存的元素平均分配到各个挂表上去,此时所需要的就是hash函数了,我所实现的哈希表是对字符串形式数据的操作,常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,另外还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数,这些函数几乎不可能找到碰撞。
算是站在巨人的肩膀上,我基本写出了一个像样的hash表。
以上常用的几个hash函数代码实现及比较,我已经上传到下面的附件,大家可以看一下。
三、代码示例
1)一些所需要的数据变量:
private int hash_length = 0;// 数组长度
private int threatHold = 0;// 重新加载的条件
private DataNode dataNodes[];// 数据表
private double load_factor = 0.8f;// 加载因子
private int size = 0;// 数据的数目
private static int default_hash_size = 10;// 数组初始大小
private int MAXIMUM_NODE = 1 << 30;// 数据最大值
2)数据的插入及删除
// 以数据单项插入 public synchronized void insert(String data) { int hash = hash(data); DataNode node = new DataNode(data); if (dataNodes[hash] == null) dataNodes[hash] = node; else { DataNode fatherNode = dataNodes[hash]; DataNode childNode = dataNodes[hash].getNextNode(); while (childNode != null) { fatherNode = childNode; childNode = childNode.getNextNode(); } childNode = node; fatherNode.setNextNode(childNode); } if (size++ > threatHold) { rehash(); } if (size > MAXIMUM_NODE) { throw new RuntimeException("Sorry,散列表已满!!!"); } } // 以数据形式删除数据项 public synchronized void delete(String data) { int hash = hash(data); DataNode node = new DataNode(data); if (dataNodes[hash] == null) { throw new RuntimeException("该数据项不存在"); } else if (dataNodes[hash].equals(node)) { dataNodes[hash] = dataNodes[hash].getNextNode(); } else { DataNode rootNode = dataNodes[hash].getNextNode(); while (rootNode != node) { if (rootNode == null) throw new RuntimeException("该数据项不存在"); rootNode = rootNode.getNextNode(); } } size--; }
3)我借用了一下前人的RS hash函数,系统是通过每个对象的hashcode进行操作
// hash函数用来计算数据的key值 public int hash(String data) { //RS hash char[] datas = data.trim().toCharArray(); int temp1 = 378551; int temp2 = 63689; int hash = 0; for(char ch:datas){ hash = hash * temp2 + ch; temp2 *= temp1; } return (hash & 0x7FFFFFFF)%hash_length; }
4)比较重要的一点,当hash表数据量达到了开始设定的边界,便需要再次加载,称之为rehash
// 重新装载
public synchronized void rehash() {
System.out.println("又要重新加载了.......");
hash_length = hash_length << 1;// 扩充为原来的两倍
if (hash_length > MAXIMUM_NODE) {
throw new RuntimeException("对不起,数组长度已达到最大!!");
}
DataNode newNodes[] = new DataNode[hash_length];
for (DataNode node : dataNodes) {
while (node != null) {
String data = node.getData();
int hash = hash(data);
DataNode nodeNew = new DataNode(data);
if (newNodes[hash] == null)
newNodes[hash] = nodeNew;
else {
DataNode fatherNode = newNodes[hash];
DataNode childNode = newNodes[hash].getNextNode();
while (childNode != null) {
fatherNode = childNode;
childNode = fatherNode.getNextNode();
}
childNode = nodeNew;
fatherNode.setNextNode(childNode);
}
node = node.getNextNode();
}
}
// 复制原来的数据
dataNodes = newNodes;
setThreatHold();
}
四.后文
这实现的基本上只有一个架构,对于很多的细节方面考虑还比较少,接下来主要考虑的还是数据的均分问题,估计更多的还是需要用到位运算,还需要继续下去....
发表评论
-
协议论
2011-09-29 01:49 922一、引文 “协议”, ... -
哈弗曼树以及压缩运用
2011-08-14 16:56 1588一.介绍 其实在还没有学习压缩之前,在学校学习中已 ... -
树与二叉树
2011-08-12 22:34 738一、介绍 对于java中“树”这个概念,顾名思义就像是现实中 ... -
链表 小结
2011-08-09 21:29 669... -
星雨——项目总结
2011-08-07 16:25 769一、项目主类: 1.Ball(子弹);2.Ba ... -
多线程 小结
2011-08-01 22:28 782一. 介绍 每个java程序都至少有一 ... -
String 小结
2011-08-01 22:27 739一.String 类是一个比较相当重要的类,像网络上很多数据 ... -
BMP
2011-07-30 23:49 773一、 介绍 开始之前先讲一 ... -
异常机制 小结
2011-07-26 17:07 661异常机制是指当程序出现错误后,程序如何处理。具体来说,异常机制 ... -
文件操作小结
2011-07-26 16:46 660系统中的文件可分为三种:目录文件、真实文件、缓存文件。j ... -
KeyWords Summary
2011-07-25 00:21 744... -
集合框架 小结
2011-07-24 23:30 630Java 中集合类定义主要 ... -
事件和监听器的使用
2011-07-23 22:58 7041 .事件其实无处不在,每个人不管是在干什么,都是事件,在类里 ... -
类与对象
2011-06-09 23:42 359 类是对象的抽象化,也就相当于与一种类型eg:int,dou ... -
登陆界面开发
2011-06-09 23:41 6641. Eclipse的简单操作 Alt+’/’ 方法提示符 ... -
方法的重载与重写,自动转型与强制转型,多态的理解
2011-06-09 01:51 9711.方法的重载与重写? 两者都是对于函数的操作,区别在于重载是 ... -
类,抽象类,接口的特点,区别
2011-06-09 01:49 675类,抽象类,接口的特点,区别 /////////////// ...
相关推荐
该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论是自定义的struct还是基本数据类型,需要注意的是不同类型的key其操作接口方式略有不通。...
uthash开源的hash函数实现,里面的uthash.h可用
内容描述:用于crypto中hash爆破的强大工具。 优势:相较于其他hash工具,具有更快的算力,使用方便简洁。 适用:适用于md5,sha256等典型hash加密方式,反推出所需的源码。
stm32f407平台上实现的hash算法
RS-Hash Function Value: " + ghl.RSHash(key)); System.out.println(" 2. JS-Hash Function Value: " + ghl.JSHash(key)); System.out.println(" 3. PJW-Hash Function Value: " + ghl.PJWHash(key)); System....
Hashcat is the self-proclaimed world's fastest password recovery tool. It had a proprietary code base until 2015, but is now released as free software. Versions are available for Linux, OS X, and ...
MurmurHash算法由Austin Appleby创建于2008年,现已应用到Hadoop、libstdc 、nginx、libmemcached,Redis,Memcached,Cassandra,HBase,Lucene等开源系统。2011年Appleby被Google雇佣,随后Google推出其变种的...
3维hashin失效准则~复合材料层合板
hashcat is the world’s fastest and most advanced password recovery tool. This version combines the previous CPU-based hashcat (now called hashcat-legacy) and GPU-based oclHashcat. Hashcat is ...
217种hashcat-V3.0所支持的哈希 举例,如md4、md5、sha1、sha256,部分特殊哈希的例子有官网说明的链接。
Hash在线解密平台最新版php实现纯txt存储哈希跟明文对应表查询
在获取到mysql用户的hash后, 可用hash直接登陆mysql进行操作 比如我们注入出数据库的hash,但是没办法拿到webshell 我们可以使用mysql_hash,用hash登陆并控制数据库 使用方法: mysql_hash.exe -u root -p Enter ...
hash函数与消息认证讲义 包括 5.1 Hash函数概述 5.1.1 Hash函数定义 5.1.2 Hash函数的安全性 5.1.3 Hash函数的迭代构造法 5.2 Hash函数MD5 5.2.1 MD5算法 5.2.2 MD5的安全性 5.3 安全Hash算法SHA-1 5.3.1 SHA-1...
Hash基础知识_Hash基础知识_Hash基础知识_Hash基础知识_Hash基础知识_Hash基础知识_
Hash函数集合,包含主流的hash函数: nginx_hash算法,OpenSSL_hash算法,RSHash,JSHash,PJWHash,ELFHash,BKDRHash,DJBHash,DEKHash,APHash等等!
Any C structure can be stored in a hash table using uthash. Just add a UT_hash_handle to the structure and choose one or more fields in your structure to act as the key. Then use these macros to store...
Hash join算法的一个基本思想就是根据小的row sources(称作build input,我们记较小的表为S,较大的表为B) 建立一个可以存在于hash area内存中的hash table,然后用大的row sources(称作probe input) 来探测前面所建...
1)GeoHash用一个字符串表示经度和纬度两个坐标,比如我现在所在位置的GeoHash值为 wx4sv61q; 2)GeoHash标识的并不是一个点,而是一个区域,比如 wx4sv61q 对应的就是一个矩形区域; 3)编码的前缀可以标识更大...
abaqus用户子程序,Hashin失效准则,abaqus显示分析,使用三维实体单元