Java语言下的数组、链表、哈希表的增删查改效率

几种数据结构，就把这几样拿出来实现了一下，比较他们的效率。

其中链表和哈希表是直接调用的java.util包下的LinkedList类和HashTable类。

hash算法是采用%操作(mod)，效率不是很高，但是作为hash表的代表应该问题不是很大。

创建100万个对象将其放入存储结构中，然后进行增加、删除、查找操作。

每次操作后调用system.nanoTime()方法，获取时间数据。代码如下：

/**
	 * 测试数组时间的方法
	 */
	public void f1(){
		int i[] = new int[1000000];
		long time1 = System.nanoTime();

		//创建一个数组
		for(int a=0;a<i.length;a++){
			i[a] = a;
		}
		long time2 = System.nanoTime();
		System.out.println("创建数组时间："+(time2-time1));
		//插入
		time1 = System.nanoTime();
		int b[] = new int[1000001];
		int c = 100;
		for(int a=0;a<b.length;a++){
			if(a<99){
				b[a]=i[a];
			}else if(a==99){
				b[a] = c;
			}else{
				b[a] = i[a-1];
			}
		}
		time2 = System.nanoTime();
		System.out.println("插入数组时间："+(time2-time1));
		//删除
		time1 = System.nanoTime();
		int d = 99;
		for(int a = 0;a<i.length;a++){
			if(a<d){
				i[a]=b[a];
			}else{
				i[a]=b[a+1]; 
			}
		}
		time2 = System.nanoTime();
		System.out.println("删除数组时间："+(time2-time1));
		//查找
		time1 = System.nanoTime();
		int e = 678;
		for(int a = 0;a<i.length;a++){
			if(i[a] ==e){
//				System.out.println("找到了e");
			}
		}
		time2 = System.nanoTime();
		System.out.println("查找数组的时间："+(time2 - time1));
	}
	/**
	 * 链表
	 */
	public void f2(){
//		User deleteUser = null;
		//创建链表
		long time1 = System.nanoTime();
		for(int i = 0;i<1000000;i++){
			User u = new User(i);
			u1.add(u);
		}
		long time2 = System.nanoTime();
		System.out.println("创建链表的时间："+(time2 - time1));
		//插入
		time1 = System.nanoTime();
		User u = new User(99999999);
		u1.add(100, u);
		time2 = System.nanoTime();
		System.out.println("插入链表的时间："+(time2 - time1));
		//删除
		time1 = System.nanoTime();
		u1.remove(100);
		time2 = System.nanoTime();
		System.out.println("删除链表的时间："+(time2 - time1));
		//查找
		time1 = System.nanoTime();
		int findId = 999;
		for(User findUser:u1){
			if(findUser.id == findId){
				System.out.println("找到了对应的链表中的对象");
			}
		}
		time2 = System.nanoTime();
		System.out.println("查找链表的时间："+(time2 - time1));
	}
/**
	 * hash算法测试
	 */public void f4(){
		Hashtable<User, Integer> ht = new Hashtable<User, Integer>();
		long time1 = System.nanoTime();
		for(int i=0;i<1000000;i++){
			User u = new User(i);
			//这里默认的put方法自带的hash算法是采用%操作(mod)使数据分布在编号为0~10的bucket中
			ht.put(u, i);
		}
		long time2 = System.nanoTime();
		System.out.println("创建哈希表的时间："+(time2 - time1));

		time1 = System.nanoTime();
		int cutId = 999;
		int cutID2 = 2;
		User cutU = new User(cutId);
		cutU.id2 = cutID2;
		ht.put(cutU, cutId);
		time2 = System.nanoTime();
		System.out.println("插入哈希表的时间："+(time2 - time1));
		time1 = System.nanoTime();
		int delId = 999;
		User delU = new User(delId);
		ht.remove(delU);
		time2 = System.nanoTime();
		System.out.println("删除哈希表的时间："+(time2 - time1));
		time1 = System.nanoTime();
		int findId = 999;
		ht.get(new User(findId));
		time2 = System.nanoTime();
		System.out.println("查找哈希表的时间："+(time2 - time1));
	}

一共进行了4次测试：数据如下：

 

 

 

由图可知，哈希表的平均创建时间最长，但是插入、删除和查找平均用时最少。数组创建用时最少，但是插入、删除操作用时最多，查找用时仅次于链表。链表除了查找用时最大，其余都排在数组和哈希表之间。

 

       由以上数据可知，数组的优势在于创建数组用时少，可以适用于规模较小的数据。

 

       链表创建时间比哈希表稍快（约17倍），但是查找用时是哈希表的1000倍以上，是数组的7倍左右。这意味着你要花较多的时间来方便你的插入、删除，但是查找还是算了吧，反正我是不会想经常去查链表里存储的东西的。

 

       哈希表在插入、删除、以及查找操作方面有着优异的表现，但是超长的创建时间提醒：除非你之后要进行大量的增删查改，不然还是用数组来的方便快捷。每次执行代码我的机器总是在创建哈希表的时候要停顿一下。