Hash结构
程序员文章站
2022-03-08 16:44:58
...
数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。
而哈希表就是结合两者的数据结构。
以下的代码是个人编写的简单Hash表结构，并与系统的进行了测试和比较。
测试结果如下：
[img]http://dl2.iteye.com/upload/attachment/0090/7382/dcff9379-3866-3182-b7c7-6cdbc7bf5ca3.png[/img]
很显然，当添加的数据多时，系统提供的要快的多~
还试用了一下其他的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));
}
}
测试结果如下：
[img]http://dl2.iteye.com/upload/attachment/0090/7382/dcff9379-3866-3182-b7c7-6cdbc7bf5ca3.png[/img]
很显然，当添加的数据多时，系统提供的要快的多~
还试用了一下其他的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);
// }