对于hash函数、一般来讲它属于数据结构知识里的一个需要重要掌握的方面;而这些数据结构和算法分析对我们搞IT的同学来说、它的重要性就不言而喻了。有这么一个简单的比方:学习java工资是5000,学习C++工资是6000;如果你搞好了算法分析和数据结构;那么你的工资就是1万了;所以很感谢公司对我们花费大量的时间来对待它。。。在这里,我想对hu总说声对不起、平常上课总是没听他讲课,总想着做自己的;这种在课堂上自顾自己不顾他人感受的做法是一种很坏的习惯。那种换位思考自己会不会感到难过的事就不说了。我还是先说说hash函数吧。
Hash,一般翻译做"散列",也有直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
Hash的主要用途是在两个方面:信息安全领域的加密算法、另一个则是在数据存储的地址上。今天、在这里着重介绍数据存储方面;我们应该知道通过hash可以把大量数据需要大空间存储变成小空间存储、从而节省存储空间。这种算法对于过去少而贵的磁盘空间来说异常重要。怎么通过hash达到这种效果呢?首先我们建立一个数组;对于这个数组来说,我们查找数据就很方便;
public Object[] array = new Object[15];
int value = 13;// 定义一个除数取余法的除数
double number=0.75;//加载因子
int d;
但是这个数组因为空间有限、我们仅仅
用它来存储数据就达不到想要的结果;怎么办呢?数组的长度是不能增加的、但我们知道链表的长度是可以随意增加删减的。所以、在建立数组后,我们可以在每个数组对应的下标下放入链表。
/**
* 用来存储在数组中
* @author Administrator
*
*/
public class Type {
public Node node;//添加结点
public int length;//记录数组当前位置上链表的长度
public Node cur;//记录链表的当前结点
}
package hash;
/**
* 链表结点
*
* @author Administrator
*
*/
public class Node {
// 节点类的数据对象
private Object obj;
private Node next;//指向下一结点
private Node pre;//指向上一结点
public int length=0;
static Node top;
public Node getPre() {
return pre;
}
public void setPre(Node pre) {
this.pre = pre;
length++;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
length++;
}
// 返回节点
public Object getObj() {
return obj;
}
// 设置节点
public void setObj(Object obj) {
this.obj = obj;
}
public int getLength(){
return length;
}
}
//主函数中添加数据
//增加数据
public void addData() {
// while (!(d==13)) {
Scanner stdin = new Scanner(System.in);
System.out.println("Please input a int");
d = stdin.nextInt();
System.out.println("刚输入的数据是:" + d);
// 每增加一个数,将其存储到hash表中
int mod = d % value;
System.out.println("得到的余数是:"+mod);
if (array[mod] == null) {// 判断是否为空
Node node = new Node();
node.setNext(null);//设置前一结点为空
node.setObj(d);//设置数据域
node.length++;
Type type=new Type();//用来存储在数组中的数据:包括链表长度、
type.node=node;
type.length=1;
type.cur=node;//将下一指针指向当前结点
array[mod] = type;//存储到数组中
} else {
//判断是否存在此数据
if(find(d)){
return;//有则返回
}
// 如果当前位置有数据,则向下移动;建立链表结构
Node node = new Node();
node.setObj(d);//设置数据域
node.setNext(((Type)array[mod]).cur);//设置上结点
((Type)array[mod]).length++;//此数组下的链表长度加1
((Type)array[mod]).cur=node;// 定义一个结点、用来标识当前结点;
}
// }
}
这样、对于每个数据我们先对它进行除数取余法;如果数组中对应取余的下标位置中没有数据则将此数据放入;如果当前下标中存有数据则添加到链表中、就这样我们可以将多个数据添加存储起来。不过、这里还有一个问题,如果当前数组下标位置中的数据足够多、那我们是无限地添加下去吗?答案是否定的、我们不能那样无限次的添加下去;否则就与链表没啥区别了。所以这里我们还要介绍另一个名词:加载因子;它是由链表的长度比上数组的长度所得的值;这个值可以自己自由设定;如果你将它设定在0-1之间、那么它最体现的效果就是节省空间;如果是大于1、那么它最体现的效果就是节省时间了。。。当数组中此下标位置上的链表数据大于数组的长度与加载因子的乘积时,我们解决的办法就是再hash。rehash就是将链表溢满的数据放到其他下标的链表上。其代码实现还有点问题、暂时我就不放上来了。。如有不足、请原谅
分享到:
相关推荐
Hash函数和数字签名 Hash函数和数字签名 Hash函数和数字签名
关于hash函数的ppt
提出了一种基于可并行和变参数的混沌分段线性映射hash函数算法。该函数通过明文扩展将并行处理的明文消息矩阵元素信息关联起来,实现了并行性。由矩阵元素位置标号决定的可变参数和矩阵元素相应的ASCII码值分别作为...
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函数研究综述 一篇非常不错的关于哈希函数的研究综述 07年发表的
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....
Hash函数及数字签名应用实验 验证码的实现过程
该文档中包含 bloomFilter过滤器中用到的对于字符串进行hash的hash函数共十一个,并带有测试程序..
HASH函数,用来提取摘要160bits。HASH函数,用来提取摘要160bits。HASH函数,用来提取摘要160bits。
这是清华大学王老师报告PPT,介绍了密码HASH函数上研究的最新成果
本文主要介绍Hash函数的设计优化,包括数字、字符串、排列等,并给出相关的代码。
HASH函数及其应用_朱全民.ppt
混沌加密算法与HASH函数构造研究_12767438.zip
所有有关HASH函数的论文,hash,安全散列算法,值得参考有几十篇关于密码学的论文
一种基于混沌的带密钥hash函数的碰撞问题及分析 指出了一种基于混沌射影构造带密钥单向hash函数算法的碰撞问题
针对基于耦合映像格子的并行 Hash 函数算法和带密钥的基于动态查找表的串行 Hash 函数算法进行了安全性分析。对于前者,发现耦合映像格子系统导致算法中存在一种结构缺陷, 在分组序号和分组消息满足特定约束关系的...
hash函数实例 c语言版 不喜勿喷!
分析了一种基于混沌构造的Hash函数方法,发现其中存在着碰撞。提出了一种基于改进Hash函数的一次数字签名方案,并对此方案的统计性和安全性进行了分析。
ECC结合轻量级Hash函数的RFID系统安全认证方案,黎远松,论文类
hash函数 的 c语言版 大家可以试试 不喜勿喷!