Hash结构

原非珏

浏览: 9801 次

最近访客更多访客>>

devcang

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

hash

数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。
而哈希表就是结合两者的数据结构。
以下的代码是个人编写的简单Hash表结构，并与系统的进行了测试和比较。

//节点数据结构
class Node{
    private Object value;//节点的值
    private Node next;//链表中指向下一结点
   
    public Node(Object value){
    	this.value = value;
    }
    public Object getValue(){
    	return value;
    }
    public Node getNext(){
    	return next;
    }
    public void setNext(Node next){
    	this.next=next;
    }
}
/**
 * Hash结构
 * @author suer
 *
 */
public class MyHashTest{ 
	private Node[] array;//存储数据链表的数组
	//创建指定长度的数组
	public MyHashTest(int length){
		array = new Node[length];
	}
	//对数据进行Hash计算
	private static int hash (Object o){   
		int h = o.hashCode();
		h ^= (h >>> 20) ^ (h >>> 12);//java.util.HashMap中用的hash算法
		return h ^ (h >>> 7) ^ (h >>> 4);
		}
	//根据Hash码得到其索引位置
	private int indexFor(int hashCode){    
	    return hashCode & (array.length-1);
	}
	/**
	 * 添加数据
	 * @param value 添加的数据值
	 */
	public void add(Object value) {
		//根据value得到index
	    int index = indexFor(hash(value));
	    System.out.println("index:" + index + " value:" + value);
	    //由value创建一个新节点newNode
	    Node newNode = new Node(value);
	    //由index得到一个节点node
	    Node node = array[index];
	    //判断由index得到的节点是否为空，若空则将新节点放入其中，若不为空则遍历这个点上的链表
	    if (node == null) {
	        array[index]=newNode;
	    } else {
	        Node nextNode;
	        //判断下一个节点是否或者该节点等于新节点的值
	        while (!node.getValue().equals(value) && (nextNode = node.getNext())!=null) {
	            node = nextNode;
	        }
	       //若值不相等则加入新节点
	        if (!node.getValue().equals(value)) {
	            node.setNext(newNode);
	        }
	    }
	}
	/**
	 * 移除数据
	 * @param value 要移除的数据值
	 * @return 移除是否成功
	 */
	public boolean remove(Object value) {
	    int index = indexFor(hash(value));
	    Node node = array[index];
	    //若对应的第一个节点就是要remove的值
	    if (node!=null && node.getValue().equals(value)) {
	        array[index]=node.getNext();
	        return true;
	    }
	    Node lastNode = null;
	    //若不是第一个节点就通过链表继续查找
	    while (node!=null && !node.getValue().equals(value)) {
	        lastNode = node;//记录上一个节点
	        node = node.getNext();
	    }
	    if (node!=null && node.getValue().equals(value)) {
	        lastNode.setNext(node.getNext());
	        return true;
	    }else {
	        return false;
	    }
	}
	//测试	
	public static void main(String[] args) {
		MyHashTest mht = new MyHashTest(55);
		//MyHashTest mht = new MyHashTest(100000);
        Long aBeginTime=System.currentTimeMillis();    
        for(int i=0;i<10000;i++){    
        mht.add(""+i);    
        }    
        Long aEndTime=System.currentTimeMillis();//记录EndTime    
        System.out.println("insert time:"+(aEndTime-aBeginTime));     
          
        Long rBeginTime=System.currentTimeMillis();//记录BeginTime    
        mht.remove(""+10000);    
        Long rEndTime=System.currentTimeMillis();//记录EndTime    
        System.out.println("remove time:"+(rEndTime-rBeginTime));  

      HashSet<String> mht2 = new HashSet<String>();     
      Long aBeginTime2=System.currentTimeMillis();//记录BeginTime    
      for(int i=0;i<10000;i++){    
      mht2.add(""+i);    
      }    
      Long aEndTime2=System.currentTimeMillis();//记录EndTime    
      System.out.println("insert time:"+(aEndTime2-aBeginTime2));    
        
      Long rBeginTime2=System.currentTimeMillis();//记录BeginTime    
      mht.remove(""+10000);    
      Long rEndTime2=System.currentTimeMillis();//记录EndTime    
      System.out.println("remove time:"+(rEndTime2-rBeginTime2)); 
	}
}

测试结果如下：

很显然，当添加的数据多时，系统提供的要快的多~

还试用了一下其他的hash算法，还不完全~有兴趣的可以多找些试试~

//加法hash,h%37的37为质数，可变~
//	private static int hash(String value){   
//		int h,i;
//		h=value.length();
//		for(i=0;i<value.length();i++)
//			h+=value.charAt(i);
//	    return h%37;
//	}
//旋转hash
//	public static int hash(String value){    
//	   int hash, i;    
//	   for (hash=value.length(), i=0; i<value.length(); ++i)    
//	     hash = (hash<<4)^(hash>>28)^value.charAt(i);    
//	   return (hash ^ (hash>>10) ^ (hash>>20));    
//	}   
//Bernstein's hash 
//	public static int hash(String value){    
//	   int hash = 0;    
//	   int i;    
//	   for (i=0; i<value.length(); ++i)
//		   hash = 33*hash + value.charAt(i);    
//	   return hash;  
//改进的32位FNV算法1
//	 public static int hash(String value){    
//	        final int p = 16777619;    
//	        int hash = (int)2166136261L;    
//	        for(int i=0;i<value.length();i++)    
//	            hash = (hash ^ value.charAt(i)) * p;    
//	        hash += hash << 13;    
//	        hash ^= hash >> 7;    
//	        hash += hash << 3;    
//	        hash ^= hash >> 17;    
//	        hash += hash << 5;    
//	        return hash;    
//	 }    
//RS算法hash   
//    public static int hash(String value){    
//        int b    = 378551;    
//        int a    = 63689;    
//        int hash = 0;       
//       for(int i = 0; i < value.length(); i++){    
//          hash = hash * a + value.charAt(i);    
//          a    = a * b;    
//       }    
//       return (hash & 0x7FFFFFFF);    
//    }    
//BKDR算法   
//    public static int hash(String value)  {    
//        int seed = 131; // 31 131 1313 13131 131313 etc..    
//        int hash = 0;    
//       for(int i = 0; i < value.length(); i++)    
//       {    
//          hash = (hash * seed) + value.charAt(i);    
//       }    
//    
//       return (hash & 0x7FFFFFFF);    
//    }       
// SDBM算法     
//    public static int hash(String value){    
//        int hash = 0;    
//       for(int i = 0; i < str.length(); i++){    
//          hash = value.charAt(i) + (hash << 6) + (hash << 16) - hash;    
//       }    
//       return (hash & 0x7FFFFFFF);    
//    }    
//DJB算法     
//    public static int hash(String value){    
//       int hash = 5381;    
//       for(int i = 0; i < value.length(); i++){    
//          hash = ((hash << 5) + hash) + value.charAt(i);    
//       }       
//       return (hash & 0x7FFFFFFF);    
//    }     
//DEK算法   
//    public static int hash(String value){    
//        int hash = value.length();       
//       for(int i = 0; i < value.length(); i++)    
//       {    
//          hash = ((hash << 5) ^ (hash >> 27)) ^ value.charAt(i);    
//       }       
//       return (hash & 0x7FFFFFFF);    
//   }