当前位置:首页 > 开发 > 编程语言 > 数据结构 > 正文

数据结构哈希表(hash)总结

发表于: 2015-04-11   作者:永夜-极光   来源:转载   浏览:
摘要: 1.什么是hash 来源于百度百科: Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。  

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)总结

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
//散列表查找算法(Hash) #include <stdio.h> #include <stdlib.h> #define OK 1 #def
散列表(Hash table,也叫哈希表)是一种查找算法,与链表、树等算法不同的是,散列表算法在查找时
$hs=@() #定义数组 $hs=@{} #定义Hash表,使用哈希表的键可以直接访问对应的值,如 $hs["王五"] 或
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说
一、哈希表的构造 哈希表的构造方法包括直接定址法、数字分析法、平方取中法、折叠法、随机数法和除
哈希表,也叫散列表,是根据关键字而直接访问在内存存储位置的数据结构。也就是说,它通过把键值经
数据结构哈希表 参考代码如下: /* 名称:哈希表 语言:数据结构C语言版 编译环境:VC++ 6.0 日期:
今天初步学习了数据结构中的哈希表。 首先在概念上,哈希表和数组队列,链表一样,是一种用来储存数
以下是阅读了《算法导论》后,对哈希表的一些总结: 哈希表又叫散列表,是实现字典操作的一种有效数
导言: 数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号