[Java] Java Array와 Hash의 데이터 접근/삽입 속도 비교

 

1. 서론

Codility Lesson4. MissingInteger 문제를 풀면서 Hash와 Array간 데이터 접근/삽입 속도의 차이를 크게 체감할 수 있었다. 해당 문제에서 array로 접근하기엔 size를 100만개로 줘야 했기에 사이즈가 좀 크지 않은가 하는 생각에 Hash, Priorty Queue로 접근했는데 아무리 머리를 굴려봐도 Time Out이 났다.
 
그래서..! 메모리 제한도 없고, 그냥 배열로 풀라는 뜻인가 해서 배열로 풀었더니 바로 Pass. 도대체 Hash와 Array간 속도 차이가 얼마나 나길래 이런것인가 싶어서 직접 테스트해봤다.
 

2. 테스트 개요

• array, HashMap, ConcurrentHashMap 세 가지에 대해 데이터 삽입/접근을 테스트한다
  • 데이터 삽입(Add Element)
    • array: indexing
    • HashMap, ConcurrentHashMap: put(key, value)
  • 데이터 접근(Get Element)
    • array: indexing
    • HashMap, ConcurrentHashMap: get(key)
• 10만회부터 500만회까지 Iteration 수행
• 각 자료구조의 크기는 Iteration 횟수로 세팅
• 10회에 대한 평균 값 산출

 
 

3. 결론

★수행속도는 환경에 따라 차이가 발생할 수 있습니다. 경향성과 배속 차이를 참고해주세요

• 실험 결과 삽입(add)에서 Iteration과 자료구조의 크기가 증감함에 따라 HashMap과 ConcurrentHashMap에서 압도적으로 시간이 증가하는 것을 확인할 수 있다. 이는 Hash 자료구조에서 add되는 갯수가 증가함에 따라 Hash Table의 크기를 resize 하기 때문에 시간이 증가하기 때문이다.
• 따라서 알고리즘 문제를 풀거나, 또는 제품의 특정 로직시 속도가 중요한 부분이라면 배열 사용을 더욱 적극적으로 고려해야 한다.

3.1. 삽입(add) 실험 결과

 

❑ 시간 단위: ms

Iteration(=자료구조 크기)	Array	HashMap	ConcurrentHashMap
100,000	0.2	4.9	15.2
200,000	0.1	7.8	29.2
300,000	0.1	8.7	32.2
500,000	0.3	16.9	52.6
1,000,000	0.3	176.6	219.4
5,000,000	2.6	4402.6	5461

 

3.2. 접근(get) 실험 결과

❑ 시간 단위: ms

Iteration Size	Array	HashMap	ConcurrentHashMap
100,000	0.2	1	0.7
200,000	0.4	1.5	2.8
300,000	0.1	1	2.1
500,000	0.9	2.5	2.1
1,000,000	0.3	3.2	4.3
5,000,000	1.8	16.3	18.7

 

4. 테스트 코드

import java.time.LocalDateTime;
import java.time.temporal.ChronoUnit;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.RepeatedTest;
import org.junit.jupiter.api.Test;

public class ArrayAndMapTest {

    static int ITERATION = 5000000;
    Map<Integer, Integer> hashMap;
    Map<Integer, Integer> concurrentMap;
    int[] arr;

    @BeforeEach
    void init() {
        hashMap = new HashMap<>();
        concurrentMap = new ConcurrentHashMap<>();
        arr = new int[ITERATION];
    }

    @Test
    @DisplayName("데이터 삽입(add) 테스트")
    @RepeatedTest(value = 10, name = RepeatedTest.LONG_DISPLAY_NAME)
    void addElement() {
        /**
         * array
         */
        LocalDateTime t1 = LocalDateTime.now();
        for (int i = 0; i < ITERATION; i++) {
            arr[i] = i;
        }
        LocalDateTime t2 = LocalDateTime.now();
        System.out.println(ChronoUnit.MILLIS.between(t1, t2));

        /**
         * hashMap
         */
        LocalDateTime t3 = LocalDateTime.now();
        for (int i = 0; i < ITERATION; i++) {
            hashMap.put(i, i);
        }
        LocalDateTime t4 = LocalDateTime.now();
        System.out.println(ChronoUnit.MILLIS.between(t3, t4));

        /**
         * concurrentHashMap
         */
        LocalDateTime t5 = LocalDateTime.now();
        for (int i = 0; i < ITERATION; i++) {
            concurrentMap.put(i, i);
        }
        LocalDateTime t6 = LocalDateTime.now();
        System.out.println(ChronoUnit.MILLIS.between(t5, t6));
    }

    @Test
    @DisplayName("데이터 접근(get) 테스트")
    @RepeatedTest(value = 10, name = RepeatedTest.LONG_DISPLAY_NAME)
    void getElement() {
        /**
         * array
         */
        LocalDateTime t1 = LocalDateTime.now();
        int n;
        arr[0] = 0;
        for (int i = 0; i < ITERATION; i++) {
            n = arr[0];
        }
        LocalDateTime t2 = LocalDateTime.now();
        System.out.println(ChronoUnit.MILLIS.between(t1, t2));

        /**
         * hashMap
         */
        LocalDateTime t3 = LocalDateTime.now();
        int n2;
        hashMap.put(0, 0);
        for (int i = 0; i < ITERATION; i++) {
            n2 = hashMap.get(0);
        }
        LocalDateTime t4 = LocalDateTime.now();
        System.out.println(ChronoUnit.MILLIS.between(t3, t4));

        /**
         * concurrentHashMap
         */
        LocalDateTime t5 = LocalDateTime.now();
        int n3;
        concurrentMap.put(0, 0);
        for (int i = 0; i < ITERATION; i++) {
            n3 = concurrentMap.get(0);
        }
        LocalDateTime t6 = LocalDateTime.now();
        System.out.println(ChronoUnit.MILLIS.between(t5, t6));
    }
}