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;
}
}
相关推荐
总结来说，哈希表是通过哈希函数和冲突解决策略来提供高效查找的数据结构。在C语言中，可以通过自定义结构体和相应的操作函数来实现哈希表，以满足各种实际应用需求。在设计哈希表时，应关注哈希函数的选择、冲突...
哈希表是一种高效的数据结构，它...总结来说，这个实习项目旨在通过设计和实现哈希表，让学生掌握哈希数据结构的基本概念、哈希函数的设计以及冲突解决策略。通过实际操作，加深对这些理论知识的理解，并提高编程能力。
哈希表，又称散列表，是数据结构课程中一种高效的数据组织方式，它通过特定的函数（哈希函数）将键（key）映射到数组的特定位置来实现快速访问。这种数据结构允许我们以接近常数时间的复杂度进行插入、删除和查找...
哈希表是一种高效的数据结构，它通过哈希函数将键（在这个案例中是人名的汉语拼音）映射到数组的索引位置，以实现快速的插入和查找操作。 1. **问题描述**： - 主要任务是为30个人名建立哈希表，其中名字以汉语...
哈希表，又称散列表，是一种高效的数据存储和检索结构，它通过特定的函数（哈希函数）将数据映射到一个固定大小的数组中，从而实现快速查找...这是一个综合性的任务，涵盖了数据结构、算法和基本的I/O操作等多个方面。
哈希表是一种高效的数据结构，它通过特定的函数——哈希函数，将任意大小的键（key）映射到一个固定大小的数组中，从而实现快速查找、插入和删除操作。在“数据结构试验：哈希表设计”中，我们将探讨哈希表的基本...
哈希表（Hash Table）是一种基于数组的数据结构，它通过将关键字映射到数组的某个位置来存储和检索数据，这种映射过程通常由一个哈希函数完成。哈希表能够实现快速的数据查找、插入和删除操作，在理想情况下，这些...
哈希表，也被称为散列表，是一种非常重要的数据结构，它在计算机科学中扮演着关键角色，尤其是在存储和检索大量数据时。哈希表通过使用哈希函数将键（Key）映射到数组的索引位置，实现了快速的查找、插入和删除操作...
### 数据结构哈希表设计与实现课程设计 #### 一、问题描述 ##### 1.1 问题描述 本课程设计的任务是针对某一个集体（例如所在班级）中的人名设计一个哈希表，使该表能够高效地完成查找操作。具体来说，目标是使得...
哈希表（Hash Table）是一种常用的数据结构，它的原理是通过哈希函数（Hash Function）将关键码值映射到表中一个位置，以加快查找的速度。哈希表的优点是其理想算法复杂度为 O(1)，即利用哈希表查找某个值，系统所...
1. 哈希表的抽象数据类型：ADT Hash 2. 哈希函数的实现：除留余数法 3. 二次探测再散列解决冲突的实现：开放地址的二次探测再散列 4. 哈希表的创建：creat 函数 5. 查找哈希表：search 函数 6. 顺序表的抽象数据类型...
哈希表（Hash Table）是一种基于数组的数据结构，它允许以平均时间复杂度为O(1)的方式进行插入、删除和查找操作。哈希表通过将键映射到数组的一个位置上来实现这些操作，该映射过程称为哈希函数。哈希函数决定了键将...
合工大数据结构C++实验报告拉链法哈希表查找算法
数据结构中的哈希表是一种高效的数据组织方式，用于快速存储和检索数据。在这个实验中，哈希表的设计和实现是核心任务。哈希表通过哈希函数将关键字映射到数组的索引位置，以此来达到快速访问的目的。实验的需求分析...
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->...
哈希表（Hash Table）是一种高效的数据结构，用于存储和检索键值对。它通过将键（Key）映射到数组的索引位置来实现快速访问。哈希表的实现通常涉及两个主要部分：哈希函数和冲突解决策略。在这个项目中，我们将深入...
链式哈希表是一种常见的数据结构，用于存储和检索数据，它结合了数组和链表的特点，以提高数据存取的效率。哈希表（Hash Table）的核心思想是通过哈希函数将数据的关键字（key）映射到一个固定大小的数组中，使得...
在IT领域，特别是软件开发和计算机科学中，掌握C语言、算法、数据结构以及哈希表等基础知识至关重要。这些概念是构建高效程序的基础，对于理解计算机如何处理信息有着深远的影响。 首先，我们来深入探讨一下C语言。...
《数据结构与算法分析》课程设计教学任务书 通讯录系统设计: 设计要求 设计以姓名为关键字的散列表（哈希表），实现通讯录查找系统，完成相应的建表和查表程序。 （1）设每个记录有下列数据项：用户名、电话号码、...
本实验通过对哈希表的基本概念、初始化过程、哈希函数设计、冲突解决策略以及查找与插入操作等关键环节进行了实现与探索，有助于加深对哈希表这种高效数据结构的理解和掌握。通过编写相应的C程序，不仅可以学习到...