欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Hash结构

程序员文章站 2022-03-08 16:44:58
...
数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。
而哈希表就是结合两者的数据结构。
以下的代码是个人编写的简单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);
// }
相关标签: hash