JAVA中的哈希表结构

      Java中的Hash结构有HashSet，HashTable和HashMap，哈希表中的每个位置称为桶（bucket），当发生哈希冲突时就以链表形式存放多个元素。

      关键字值key和储存位置的对应关系h，这种对应关系我们称之为Hash函数，h(key)就是Hash地址。按这种思想建立的查找表就是Hash表。这样查询速度必须快。但是一般情况下不存在理想的一对一关系，关键字通常也不是数值类型，而是字符型或其他数据类型。

     在构造Hash函数之前，我们需要知道：

1.Hash函数本质上是集合到集合的映像，一个数学函数很难完成反应这种对应关系。

2.Hash要尽量减少冲突。

 

Hash函数的构造方法:

1.直接定值法，现行函数直接定值：

       h(key) = key 或者 h(key) = a*key + b

2.字符串数值散列法：

       Eg: public int hash1(String s,int n){

int i,sum;

        i=0;

        int[] x= stringToInts(s);

        while(i<10 ){

        sum=sum+x[i++];

        sum=sum%n;

}

    public static int[] stringToInts(String s){

           int[] n = new int[s.length()]; 

           for(int i = 0;i<s.length();i++){

             n[i] = Integer.parseInt(s.substring(i,i+1));

           }

           return n;

        }

其他函数如：UNIX系统V4版本中可执行文件与目标文件中的ELFHash函数（Exextable and Linking Format)。*自行百度*

3.平方取中法

  现将关键字平方然后去其而兼职表达式中的r位作为函数值

4.取值散列法

  最简单了，h(key) =  key mod p

5.随机数法

  适用于关键字长度不等的Hash函数构造

  h(key) = random(key)

 

 

处理冲突的方法：

 

1.开放定位法

  再次确定Hash地址：

  h1 = (h(key)+d)mod n 

2.Rehash法

 

现在写一个简单的旋转Hash函数并与系统的HashSet函数进行比较：

package Hash;

import java.util.HashSet;


public class Test {    
	    //存储数据链表的数组
	    private node[] array;   
	    public Test(int length){   
	        array = new node[length];   
	    }   
      //对数据进行Hash计算   
	  //旋转hash   
	  public static int hash(Object value){       
	     int hash, i;
	     String s;
	     s=value.toString();
	     for (hash=s.length(), i=0; i<s.length(); ++i)       
	       hash = (hash<<4)^(hash>>28)^s.charAt(i);       
	     return (hash ^ (hash>>10) ^ (hash>>20));       
	  }  
	    //根据Hash码得到其索引位置   
	    private int indexFor(int hashCode){       
	        return hashCode & (array.length-1);   
	    }   
	    /**  
	     * 添加数据  
	     */  
	    public void add(Object value) {   
	        //根据value得到index   
	        int index = indexFor(hash(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);   
	            }   
	        }   
	    }   
	    /**  
	     * 移除数据  
	     * @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) {   
	        Test test = new Test(100);  
	        Long abegin=System.currentTimeMillis();       
	        for(int i=0;i<10000;i++){       
	        test.add(""+i);       
	        }       
	        Long aend=System.currentTimeMillis();     
	        System.out.println("旋转哈希插入数据时间"+(aend-abegin));        
	             
	        Long bbegin=System.currentTimeMillis();   
	        test.remove(""+10000);       
	        Long bend=System.currentTimeMillis();       
	        System.out.println("旋转哈希移除时间:"+(bend-bbegin));     
	  
	      HashSet<String> test2 = new HashSet<String>();        
	      Long begin=System.currentTimeMillis();   
	      for(int i=0;i<10000;i++){       
	      test2.add(""+i);       
	      }       
	      Long end=System.currentTimeMillis();     
	      System.out.println("系统HashSet插入时间:"+(end-begin));       
	           
	      Long rBeginTime2=System.currentTimeMillis();     
	      test2.remove(""+10000);       
	      Long rEndTime2=System.currentTimeMillis();  
	      System.out.println("系统HashSet移除时间:"+(rEndTime2-rBeginTime2));    
	    }   
	}  

 

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;   
 }   


}

 

旋转哈希插入数据时间189

旋转哈希移除时间:0

系统HashSet插入时间:37

系统HashSet移除时间:0

 

代码参考自 http://931646813.iteye.com/blog/1967976

没有写rehash的方法，下次补上

<!--EndFragment--><!--EndFragment-->