인공지능 과제에서 인덱싱을 하면서 무심코 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();
	}
}


'밤을 지새다 > Java' 카테고리의 다른 글

Java 8 메서드 파라미터의 이름 얻기  (2) 2015.04.30
int 와 long 의 해시 값은 다르다?  (0) 2014.03.15
이클립스 환경에서 AWT에서 한글이 깨질 때  (0) 2012.05.16
Java PriorityQueue  (0) 2012.05.07
Java StAX Event  (0) 2012.05.01
  1. 잘봤습니다. 2013.12.15 01:25

    Hashmap은 중복된 값이 들어오면 이전의 값이 새로 들어온 값으로 바뀝니다.
    즉 입력하는 과정에서 계속 중복되므로 결국에 size는 1이 됩니다.
    이는 탐색속도를 측정할때 영향을 주게됩니다. (결국 size가 1인 map에서 탐색하니 속도가 빠르게 나올껍니다.)

    • 마음이 뛰다 2013.12.16 13:28 신고

      글의 제일 위쪽에 보시면
      테스트 엘리먼트는 Integer 인스턴스 5,000,000(5백만개)를 이용하여 수행하였다.
      탐색과 삭제에서는 균등하게 떨어진 4990개의 데이터를 이용하였다.
      라고 써두었습니다. 키를 같은 값으로 하지는 않았습니다.

  2. HELLO 2014.02.25 15:01

    ArrayList가 배열을 사용해서 검색에 빠르다고는 하나 아무래도 HashMap이 빠르겠죠. 잘보았습니다.

    • 마음이 뛰다 2014.04.17 15:55 신고

      둘다 O(1)이긴 하나, 연산 자체가 직접 접근과 해시 계산 후 접근이니,
      접근 자체는 ArrayList가 빠르지요. 삽입, 삭제, 검색 등의 연산이 각각 특성화된 것들이 있으니 무엇이 빠르다, 느리다 보다는 무엇을 어디에 적절하게 써야 하는지를 알아야 할 것 같습니다 :)

    • hhh 2017.10.31 13:47

      HashMap은 get 함수 자체로, key에 대한 value를 검색해서 가져오고, ArrayList는 get을 사용할 경우에는 index를 기준으로 가져오는 것입니다.
      ArrayList는 String 혹은 별도의 Object에 대하여 많이 사용하는데, index를 모를 경우에는 별도로 검색하는 부분을 구현해주어야하고 그러면 검색은 HashMap에 비해서는 많이 느려질겁니다.

+ Recent posts