class="p0">??????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的方法，下次补上
相关文章
