HashMap, ArrayList, LinkedList 속도 비교

인공지능 과제에서 인덱싱을 하면서 무심코 HashMap을 사용했는데,

다른 조의 시연을 보니 인덱싱에 상당한 시간이 소요되었다.

갑자기 궁금증이 생겨서 세 컬렉션의 속도를 비교하게 되었다.

테스트 엘리먼트는 Integer 인스턴스 5,000,000(5백만개)를 이용하여 수행하였다.

탐색과 삭제에서는 균등하게 떨어진 4990개의 데이터를 이용하였다.

테스트 결과 :

5000000개의 인스턴스 생성 시간 0.548829807초

HashMap Test

입력 소요 시간  2.415268645초

탐색 소요 시간 0.002399381초

삭제 소요 시간 0.002615092초

ArrayList

입력 소요 시간  0.381054002초

탐색 소요 시간 1.99475E-4초

삭제 소요 시간 137.231368119초

LinkedList

입력 소요 시간  1.503839756초

탐색 소요 시간 52.905209243초

삭제 소요 시간 52.587791295초

HashMap의 경우는 입력되는 시간을 제외하면 우수한 성능을 보였고,

(탐색과 삭제 시에 인덱스가 아닌 키값으로 하였음)

ArrayList 의 경우에는 내부적으로 배열을 쓰는 컬렉션 답게 탐색에서는 매우 우수한 속도를 보였지만

삭제 시에 배열의 구조가 변경되므로 매우 느린 속도를 보였다.

LinkedList는.. 탐색, 삭제 모두 순차 탐색을 하므로(실제로 이중 연결 링크드리스트로 되어있고, Head, Rear 포인터를 이용해서, 탐색하려고 하는 인덱스와 리스트 크기의 반과 비교해서 인덱스가 작은 경우 앞에서부터 탐색하고, 큰 경우 뒤에서부터 탐색하도록 되어있어 평균적으로 n / 2의 시간 복잡도를 가진다.) 많이 느렸다. -_-

따라서 HashMap은 Key, Value 쌍을 가지는 데이터를 관리할 때 용이하고,

ArrayList는 데이터가 입력 되고 삭제가 빈번하지 않은 경우에 사용하면 되고,

Linkedlist는 Queue와 같이 Head와 Read와 가까이에서 탐색, 삭제가 이뤄지는 경우에 쓰면 좋을 듯 하다.

테스트에 사용한 코드는 아래와 같습니다. 참고 하실 분은 아래의 소스를 사용하시면 됩니다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class TestCode {
	static Integer[] testArray = new Integer[5000000];
	Integer[] values = new Integer[4990];

	public void hashMapTest() {
		long start = System.nanoTime();

		HashMap hashmap = new HashMap();
		for(Integer integer : testArray){
			hashmap.put(integer, integer);
		}
		
		long end = System.nanoTime();
		
		System.out.println("\nHashMap Test");
		System.out.println("\t입력 소요 시간  " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			hashmap.get(value);
		}		
		end = System.nanoTime();
		System.out.println("\t탐색 소요 시간 " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			hashmap.remove(value);
		}
		end = System.nanoTime();
		System.out.println("\t삭제 소요 시간 " + second(start, end) + "초");
	}
	
	public void arrayListTest(){
		long start = System.nanoTime();
		
		ArrayList arrayList = new ArrayList();
		for(Integer integer : testArray){
			arrayList.add(integer);
		}
		
		long end = System.nanoTime();
		
		System.out.println("\nArrayList");
		System.out.println("\t입력 소요 시간  " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			arrayList.get(value);
		}		
		end = System.nanoTime();
		System.out.println("\t탐색 소요 시간 " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(Integer value : values){
			arrayList.remove(value);
		}
		end = System.nanoTime();
		System.out.println("\t삭제 소요 시간 " + second(start, end) + "초");
	}
	
	public void linkedListTest(){
		long start = System.nanoTime();
		
		List linkedList = new LinkedList();
		for(Integer integer : testArray){
			linkedList.add(integer);
		}
		
		long end = System.nanoTime();
		
		System.out.println("\nLinkedList");
		System.out.println("\t입력 소요 시간  " + second(start, end) + "초");
		start = System.nanoTime();
		for(int value : values){
			linkedList.get(value);
		}		
		end = System.nanoTime();
		System.out.println("\t탐색 소요 시간 " + second(start, end) + "초");
		
		start = System.nanoTime();
		for(int value : values){
			linkedList.remove(value);
		}
		end = System.nanoTime();
		System.out.println("\t삭제 소요 시간 " + second(start, end) + "초");
	}


	private void prepare() {
		long start = System.nanoTime();
		for (int i = 0; i < testArray.length; i++) {
			testArray[i] = i;
		}
		long end = System.nanoTime();
		
		ArrayList temp = new ArrayList(1000);
		for(int i = 0 ; i < 4990 ; i++){
			temp.add(i * 1000);
		}
		temp.toArray(values);
		
		
		System.out.println(testArray.length + "개의 인스턴스 생성 시간 " +
				second(start, end) + "초");
		
	}
	
	private double second(long start, long end){
		return (end - start) / Math.pow(10, 9);
	}

	public void start() {
		prepare();
		hashMapTest();
		arrayListTest();
		linkedListTest();
	}

	public static void main(String[] args) {
		TestCode test = new TestCode();
		test.start();
	}
}