数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。
而哈希表就是结合两者的数据结构。
以下的代码是个人编写的简单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);
// }
- 大小: 10.4 KB
分享到:
相关推荐
这是百度一位大牛写的hash结构
1. hash key值计算,key的比较,内存分配,可以通过实现模板类重新定制 2. 实现按插入时间的先后,通过有序链表访问节点。用于按照时间先后,快速遍历(删除)超时节点。 3. hash 实现快速存取, 链表快速实现...
(1) 首字 Hash 索引:首字 Hash 函数根据汉字的国标区位 (2)词索引:词索引的每个单元包括两项内容:①所有词长 (3)词典正文:以词为单位的有序表
该文针对支持度阈值变化时的关联规则维护问题,提出了关联规则交互挖掘算法HIUA,该算法改进了原始IUA算法的剪枝过程,并通过Hash结构提高算法运行效率。在UCI数据集及企业实际财务数据集中的实验结果表明:在支持度...
Yew 允许像遍历对象树一样遍历 Hash 结构。 用法 鉴于位于config/env.yml的以下 yml 文件: orientdb : url : ' remote:localhost/db ' user : admin pass : secret testing : frameworks : minitest : true ...
Map数据结构 数据结构 JavaScript 的对象(Object),本质上是键值对的集合(Hash 结构),但是传统上只能⽤字符串当作键。这给它的使⽤带来了很⼤的限 制。 为了解决这个问题,ES6 提供了 Map 数据结构。它类似于...
该套开源代码采用宏的方式实现hash函数的相关功能,支持C语言的任意数据结构最为key值,甚至可以采用多个值作为key,无论是自定义的struct还是基本数据类型,需要注意的是不同类型的key其操作接口方式略有不通。...
学校的数据结构的实验报告,关于hash查找的课程设计
数据结构课程设计, hash表,哈希表。
数据结构(字符串匹配,hash,二叉树)训练 数据结构(字符串匹配,hash,二叉树)训练
带一个基本的shell,有cat,ls,play3个基本命令(并非使用树结构和hash结构,使用简单的那种命令解析,如果想研究命令解析的这个不适合。) 使用sd卡,fsfat文件系统。 使用网上的一些代码,源代码版权归原作者...
数据结构第16次作业,hash表 Spellchecking Prerequisites, Goals, and Outcomes Prerequisites: Students should have mastered the following prerequisite skills. • Hash Tables - Understanding of the ...
本程序主要应用了hash结构,为提高效率,并未选择拉连法解决冲突, 发生冲突时利用 双备用hash 函数查找,如果失败再利用线性探查法查找 存储位置的方法 同时,程序设计了用户选项,选择可能出现单词数量,为...
数据结构中hash函数的实现,自己写的,VC平台。
这个是基于redis的购物车流程 所有的数据都是储存在redis中 redis的hash结构来储存所有用户购物车的数据。咱们都知道在使用hash的时候,涉及到key,field,value这三个方面的参数信息 购物车中包含 商品总件数,总价格...
数据结构课程实验Hash表设计实验报告,严蔚敏C语言版。
②Hash表中的结点结构。频度、冲突次数 三、功能设计 ①从一个大字符串中分解单词 ②识别是否是关键词;用哪种方法:有序表查找、二叉查找树? ③Hash函数,解决冲突,统计冲突次数。key => 地址 ④插入Hash表,或...
本文档为吉林大学计算机科学与技术专业大三上学期的操作系统实验课的实验报告,有需要的可以借鉴。
Hash结构 5.在虚拟页式存储管理系统中,地址越界中断属于( )。 A.输入输出中断 B.程序性中断 C.时钟中断 D.自愿性中断 6.在ISO/OSI参考模型中,数据格式转换,数据加密/解密、压缩/恢复,实现互通和互...