关于对hash结构的理解以及java语言的实现

       这几天了解了一下哈希的结构，现在就将我的理解进行一下总结。首先我先解释一下什么叫做哈希函数。哈希函数说白了就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。然后我们再根据这个摘要来得到我们所放进去的数据。那么哈希的内部到底是怎么样的呢。在java中有两种基本的结构：数组和模拟指针（引用），所用的数据结构都是由这两种结构得来的。当然在java中hashMap也是由这两种结构得来的，但是相比较而言，hash的结构是比较优秀的，它能快速高效的进行查找与存储数据。现在，就hash的结构来重点讲解一下。

 

       首先在java中，虽然我们说集合是可以直接来存储对象的，那么到底它内部是怎么存的，在我们实例化一个对象后然后调用一下对象的hashCode（）方法。下面一小段代码：

 

 

public class MyHash {
	
	public static void main(String[]args){
		
		MyHash myHash = new MyHash();
		MyHash myHash1 = new MyHash();
		MyHash myHash2 = new MyHash();
		MyHash myHash3 = new MyHash();
		 int j = myHash.hashCode();
		 int k = myHash1.hashCode();
		 int l = myHash2.hashCode();
		 int m = myHash3.hashCode();
		 
		 System.out.println("myHash的引用"+j);
		 System.out.println("myHash1的引用"+k);
		 System.out.println("myHash2的引用"+l);
		 System.out.println("myHash3的引用"+m);
	}

       通过结果我们可以看到是一串数字。那么这一串数字到底表示什么，是干嘛用的呢？其实这串

数字就是对象的引用，那么所谓的存对象就是存储这些对象的引用，然后再根据这些引用来找

到对象。那么在哈希表中到底是怎么实现对这些引用和数据的存储。前面我们已经说过了，

hash的基本结构是数组和链表的结合，那么到底是怎么实现的呢。我们有一个图来进行说明：

       如图横向的是一个数组，纵向的是一个链表。我们先对一个对象的hashCode()方法得到的

一串数字进行hash（）算法，然后根据所得到的key值找到在数组上相应的的位置，然后将

key-value键值对存储进去，那么如果原来的位置上有值怎么办，我们先检验一下值，然后再

根据值来决定是直接覆盖还是以链表的方式链接。说到这里可能会有这样的一个疑问，我们为

什么要用这么复杂的方式来存储数据，直接用链表或者数组不就行了吗。我们分别来讨论一下

。当使用数组来存储对象时我们要根据什么来作为缩引，如果是根据对象的引用，那么必然会

造成内存的巨大的浪费，同时当我们来声明数组是也是无法预测最大的范围。当使用链表时。

我们的确可以解决上面的索引以及内存消耗问题，但是我们每次索引一个值都要遍历整个链表

。这样必然会造成时间的大量消耗。这样hash表就能很好的解决这样的问题，但是问题又来了

。如果但我们经过hash过后的key值对应在一个数组的值上，也就是说存储在数组中的链表过

于长，那么我们就算能很好的找到key值也还是要遍历一条很长的链表才能得到数据。这样我

们又有了rehash（）的方法的概念了。说白了就是当我们链表的长度超过一定的值，就重新

建立一个数组，这个数组的长度将比原来的数组的长度要大，然后在将原来数组中的所有数据

冲新hash（）然后再将数据存储进去。当然rehash（）是最消耗时间的。一般而言我们申明

数组的长度是会是2的n次方（具体原因自己百度），在rehash（）是我们也是会将新建的数

据的长度是原来数组的2倍。

 

下面我将结合着自己写的hash表来讲解一下，当然我的hash表是没有系统提供的那么优化，

想要更进一步了解就自己查看源代码吧。

 

首先建立一个节点类

package hash;

public class Node {
	
	private Object value;
	private Node next;
	
	public Node(){
		
	}
	public Node(Object value){
		
		this.value = value;
	}
	public Object getValue() {
		return value;
	}
	public void setValue(Object value) {
		this.value = value;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
	
	

}

 

然后结合这来分析MyHash中的代码，首先是hash（）函数，这里我用了比较笨的方法，

//写一下hash方法，在这里我用一种比较笨拙hash方法，直接取余数,那么这个返回值就是在数组中下标
	public  int hash(Object o){
		
		int hashCode = o.hashCode();
		int re = hashCode%(array.length);
		
		return re;
	}

 

然后我就写了一个向我的hash结构中加数据的方法：

//向hashSet中加数据
	//把对象加入集合，不允许加入重复的元素
	 public void add(Object value) {
		//先根据value得到index
	        int index = hash(value);
	      //由value创建一个新节点newNode
	        Node newNode = new Node(value);
	      //由index得到一个节点node
	        Node node = array[index];
	      //若这个由index得到的节点是空，则将新节点放入其中
	        if (node == null) {
	            array[index]=newNode;
	            size++;
	        } else {//若不为空则遍历这个点上的链表（下一个节点要等于空或者该节点不等于新节点的值--不允许重复）
	            Node nextNode;
	            while (!node.getValue().equals(value) && (nextNode = node.getNext())!=null) {
	            	listSize++;
	                node = nextNode;
	            }
	          //当链表遍历到最后一个节点时
	            if (!node.getValue().equals(value)) {
	                node.setNext(newNode);
	                listSize++;
	                size++;
	            }
	            
	            //在此处进行rehash的判断
	            if(listSize>(this.loadFactor*this.NodeNum)){
	            	
	            	this.NodeNum = 2*this.NodeNum;
	            	listSize=0;
	            	reHash(this.NodeNum);
	            	
	            	
	            }
	        }
	    }

 上面的在添加数据的时候我们首先判断相应的索引位置是否有数据，如果有就先与相应链表的数据进行分析，看是否相等以及最后的添加，当添加完后我们再判断是否要进行reHash（）的操作，rehash（）的具体代码在下面：

	//获取所有的数据，用来进行reHash（）；
	 	public Object[] getAll() {
	        Object [] values = new Object[size];
	        int index = 0;
	        for (int i = 0; i < array.length; i++) {
	            Node node = array[i];
	            while (node!=null) {
	                values[index++]=node.getValue();
	                node = node.getNext();
	            }   
	        }
	        return values;   
	    }
	 	//reHash()
	 	public void reHash(int length){
	 		//重新定义数组长度
	 		array = new Node[length];
	 		Object [] values = getAll();
	 		//将数据加到新的hash结构中
	 		for(Object value:values){
	 			
	 			add(value);
	 			
	 		}
	 	}

我们先根据负载因子以及数组长度来计算每个数组中链表的最大长度，如果长度过大，就进行reHash（）方法，有此可见Rehash（）是最耗时间的。以上的代码写的不是很好，主要是用来了解hash的结构。