1.什么是hash
来源于百度百科:
Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
2.hash表的作用:
我拿了10w级别的数据,分别对3种结构,数组实现的Arraylist,链表实现的LinkedList和hashmap进行了测试,
测试了增删查改4种操作
测试结果表明hashmap在查询上不具有任何优势,它的优势在于修改,增加,删除数据时提高效率,它是链表和数组的一种结合.(测试代码在本文结尾处)
3.hash表可能存在的问题:
碰撞:不同的输入值,得到相同的散列值,
解决方法:挂外链,重新构造hash函数
4.测试代码如下
4.1ArrayList
package s0404数组列表哈希表效率测试; import java.util.ArrayList; public class ArrayMain { public static void main(String[] args){ int n=100000; ArrayList<User> list=new ArrayList<User>(); long startTime=System.currentTimeMillis(); //增加100w个数据的时间********************************************************* for(int i=0;i<n;i++) { list.add(new User(i)); } long endTime=System.currentTimeMillis(); System.out.println("增加10w个数据所用的时间"+(endTime-startTime)+"ms"); //增加100w个数据的时间********************************************************* // //删除数据的时间********************************************************* // long startTime3=System.currentTimeMillis(); // for(int i=list.size()-1;i>=0;i--) // { // list.remove(list.get(i)); // // } // long endTime3=System.currentTimeMillis(); // System.out.println("删除10w个数据所用的时间"+(endTime3-startTime3)+"ms"); // //删除数据的时间********************************************************* // //查询10w个数据的时间********************************************************* // long startTime4=System.currentTimeMillis(); // for(int i=list.size()-1;i>=0;i--) // { // list.get(i).getAge(); // // } // long endTime4=System.currentTimeMillis(); // System.out.println("查询10w个数据所用的时间"+(endTime4-startTime4)+"ms"); // //查询10w个数据的时间********************************************************* // //改数据的时间********************************************************* // long startTime4=System.currentTimeMillis(); // for(int i=0;i<list.size();i++) // { // list.get(i).setAge(i+1); // // } // long endTime4=System.currentTimeMillis(); // System.out.println("改数据所用的时间"+(endTime4-startTime4)+"ms"); // //改数据的时间********************************************************* } }
4.2LinkedList
package s0404数组列表哈希表效率测试; import java.util.LinkedList; public class LieBiaoMain { public static void main(String[] args){ int n=100000; LinkedList<User> list=new LinkedList<User>(); long startTime=System.currentTimeMillis(); //增加数据的时间********************************************************* for(int i=0;i<n;i++) { list.add(new User(i)); } long endTime=System.currentTimeMillis(); System.out.println("增加10w个数据所用的时间"+(endTime-startTime)+"ms"); //增加数据的时间********************************************************* // //删除数据的时间********************************************************* // long startTime3=System.currentTimeMillis(); // for(int i=0;i<list.size();i++) // { // list.remove(list.get(i)); // } // long endTime3=System.currentTimeMillis(); // System.out.println("删除10w个数据所用的时间"+(endTime3-startTime3)+"ms"); // //删除数据的时间********************************************************* // //查询数据的时间********************************************************* // long startTime4=System.currentTimeMillis(); // for(int i=0;i<list.size();i++) // { // list.get(i).getAge(); // } // long endTime4=System.currentTimeMillis(); // System.out.println("查询10w个数据所用的时间"+(endTime4-startTime4)+"ms"); // //查询数据的时间********************************************************* // //改数据的时间********************************************************* // long startTime4=System.currentTimeMillis(); // for(int i=0;i<list.size();i++) // { // list.get(i).setAge(i+1); // // } // long endTime4=System.currentTimeMillis(); // System.out.println("改数据所用的时间"+(endTime4-startTime4)+"ms"); // //改数据的时间********************************************************* } } 4.3 hashmap package s0404数组列表哈希表效率测试; import java.util.HashMap; public class HashMain { public static void main(String[] args){ int n=100000; HashMap<Integer,User> list=new HashMap<Integer,User>(); long startTime=System.currentTimeMillis(); //增加100w个数据的时间********************************************************* for(int i=0;i<n;i++) { list.put(i,new User(i)); } long endTime=System.currentTimeMillis(); System.out.println("增加"+n+"个数据所用的时间"+(endTime-startTime)+"ms"); //增加100w个数据的时间********************************************************* // //删除数据的时间********************************************************* // long startTime3=System.currentTimeMillis(); // for(int i=list.size()-1;i>=0;i--) // { // list.remove(list.get(i)); // // } // long endTime3=System.currentTimeMillis(); // System.out.println("删除"+n+"个数据所用的时间"+(endTime3-startTime3)+"ms"); // //删除数据的时间********************************************************* // //查询10w个数据的时间********************************************************* // long startTime4=System.currentTimeMillis(); // for(int i=0;i<list.size();i++) // { // list.get(i).getAge(); // // } // long endTime4=System.currentTimeMillis(); // System.out.println("查询"+n+"个数据所用的时间"+(endTime4-startTime4)+"ms"); //查询10w个数据的时间********************************************************* //改数据的时间********************************************************* long startTime4=System.currentTimeMillis(); for(int i=0;i<list.size();i++) { list.get(i).setAge(i+1); } long endTime4=System.currentTimeMillis(); System.out.println("改数据所用的时间"+(endTime4-startTime4)+"ms"); //改数据的时间********************************************************* } }
4.4User类
package s0404数组列表哈希表效率测试; public class User { private int age; public User(int age) { this.age=age; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } }
相关推荐
数据结构课程设计, hash表,哈希表。
void find(char num[11]) //在以电话号码为关键字的哈希表中查找用户信息 { hash(num); node *q=phone[key]->next; while(q!= NULL) { if(strcmp(num,q->num)==0) break; q=q->next; } if(q) cout<<q->...
合工大数据结构C++实验报告拉链法哈希表查找算法
《数据结构与算法分析》课程设计教学任务书 通讯录系统设计: 设计要求 设计以姓名为关键字的散列表(哈希表),实现通讯录查找系统,完成相应的建表和查表程序。 (1)设每个记录有下列数据项:用户名、电话号码、...
针对本班的人名设计一个杂凑表,数据表的长度为50~80个记录;分析平均查找长度,完成相应的建表和查表程序,设计直观的界面显示杂凑表的内容。
课题的目的和任务:根据数据元素的关键字和哈希函数建立哈希表并初始化哈希表,用开放定址法处理冲突,按屏幕输出的功能表选择所需的功能实现用哈希表对数据元素的插入,显示,查找,删除。 初始化哈希表时把elem...
通过对哈希算法的演示,很快能理解哈希表的功能和作用
此文档,包含了 树,二叉树,数据结构与算法,排序,哈希表等难点重点详解。希望对于学习有帮助。
【问题描述】 利用哈希表进行存储。...哈希表(Hash table)是一种基于哈希函数(Hash function)实现的数据结构,用于实现关联数组或者映射等抽象数据类型。哈希表将元素的键(key)通过哈希函数转换为哈希值
哈希表(Hash Table)是一种高效的数据结构
这是一个关于通讯录基本功能的简单程序希望对大家有用
自己整理的数据结构哈希表详解,参考其他博客、算法导论。包括哈希表构造方法、解决冲突的方法、包含牛客上的练习题。
数据结构课程设计-哈希表设计 代码,报告,灰常完美
哈希表
数据结构课程设计C++基于哈希表实现的通讯录系统源码+课程设计报告(95分以上).zip本系统为电话号码查找系统,本系统最频繁的操作为查询功能,查询速度的快慢对此系统有至关重要的影响,因此应该选择合适的数据结构...
哈希表,数据结构,完整代码,值得学习。C++语言
现在只能实现关键字为数字,存储单位为为字符串类型的,给大家简单的提供下HASH表的存储原理
数据结构课程实验Hash表设计实验报告,严蔚敏C语言版。