hash函数

对于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就是将链表溢满的数据放到其他下标的链表上。其代码实现还有点问题、暂时我就不放上来了。。如有不足、请原谅