Java - List vs Map

List vs Map

 인프런 강의를 듣던 중 "List로 조회를 하면 성능이 저하될 수 있으니 Map으로 바꾸자"라는 말을 들었다. 사실 별다른 생각 없이 두 컬렉션을 사용해왔다. 키를 통해 값을 조회해야하는 상황에선 Map을 쓰고, 그 외의 상황에선 일반적으로 List를 사용해 왔다. 특정 상황에서 분명 유리한 컬렉션이 있다. 그렇기에 두 컬렉션의 구조적 차이와 성능 차이에 대해 알아보고자 한다. 

---

List vs Map(조회 시 성능 차이)

두 컬렉션에서 주로 사용되는 구현체인 ArrayList와 HashMap을 사용해 비교를 해보자

1. 저장 성능 차이

1-1. List  -  순차 저장

// ArrayList - 순차 저장
saveListSequentially(1000);
saveListSequentially(10000);
saveListSequentially(100000);
saveListSequentially(1000000);

private static void saveListSequentially(int size){
    arrayList = new ArrayList<>();
    
    start = System.currentTimeMillis();
    for (int i=0; i<size; i++) {
        arrayList.add("string"+i);
    }
    end = System.currentTimeMillis();
    
    System.out.println("ArrayList 순차 저장 - " + form.format(size) + "개 = " + (end-start) + "ms");
}

// 결과 값
ArrayList 순차 저장 - 1,000개 = 8ms
ArrayList 순차 저장 - 10,000개 = 1ms
ArrayList 순차 저장 - 100,000개 = 13ms
ArrayList 순차 저장 - 1,000,000개 = 57ms

 흔히 알고 있는 상식처럼 순차적으로 저장하는 것은 빠르다. 1,000개의 경과 시간이 10,000개의 경과시간 보단 빠른 것은 정확한 이유를 모르겠다. 해당 실험에서만 이러한 결과가 도출된다. JVM warm-up과 관련된 문제일거라 추측은 하지만 여러번 실행해도 비슷한 결과를 내기에 확답을 내리기 어렵다.

 

1-2. List  -  랜덤 저장

// ArrayList - 랜덤 저장
saveListRandomIndex(1000);
saveListRandomIndex(10000);
saveListRandomIndex(100000);
//saveListRandomIndex(1000000);

private static void saveListRandomIndex(int size){
    arrayList = new ArrayList<>();
    
    start = System.currentTimeMillis();
    for (int i=0; i<size; i++) {
        int idx = (int)(Math.random()*i);
        arrayList.add(idx, "string" + i);
    }
    end = System.currentTimeMillis();
    
    System.out.println("ArrayList 랜덤 저장 - " + form.format(size) + "개 = " + (end-start) + "ms");
}

// 결과 값
ArrayList 랜덤 저장 - 1,000개 = 0ms
ArrayList 랜덤 저장 - 10,000개 = 9ms
ArrayList 랜덤 저장 - 100,000개 = 201ms

 예상했던 것처럼 특정 인덱스에 값을 삽입하는 것은 느리다. 심지어 1,000,000개는 다른 경우에 비해 너무 느리기에 비교를 하지 않았다.

 

List는 데이터 저장의 순서를 보장하는 컬렉션이다. 이를 위해 List를 쓰는 경우가 많기 때문에 해당 테스트는 사실 무의미하다고 볼 수 있다.

 

1-3. Map - 저장

// HashMap - 저장
saveMap(1000);
saveMap(10000);
saveMap(100000);
saveMap(1000000);

private static void saveMap(int size) {
    hashMap = new HashMap<>();
    start = System.currentTimeMillis();
    for(int i=0; i<size; i++) {
        hashMap.put(i, "value" + i);
    }
    end = System.currentTimeMillis();
    System.out.println("HashMap       저장 - " + form.format(size) + "개 = " + (end-start) + "ms");
}

// 결과 값
HashMap       저장 - 1,000개 = 0ms
HashMap       저장 - 10,000개 = 7ms
HashMap       저장 - 100,000개 = 13ms
HashMap       저장 - 1,000,000개 = 130ms

100,000개 이하의 경우 List에 순차적으로 데이터를 삽입하는 것과 큰 차이가 없었다. 하지만 1,000,000개에선 약 2.5배 느린 결과를 보여준다.

 

저장 속도 차이

List(순차) < Map < List(랜덤)

---

2. 조회 성능 차이

2-1. List  -  조회(contains)

// ArrayList - 순차 조회
getList(1000);
getList(10000);
//getList(100000);
//getList(1000000);

private static void getList(int size) {
    arrayList = new ArrayList<>();
    for (int i=0; i<size; i++) {
        arrayList.add("string" + i);
    }

    start = System.currentTimeMillis();
    for (int i=0; i<size; i++) {
        // 순차적으로 조회하는 것과 큰 차이 없음
        int idx = (int) (Math.random()*size);
        boolean contains = arrayList.contains("string" + idx);
    }
    end = System.currentTimeMillis();
    
    System.out.println("ArrayList 순차 조회 - " + form.format(size) + "개 = " + (end-start) + "ms");
}

// 결과 값
ArrayList 순차 조회 - 1,000개 = 5ms
ArrayList 순차 조회 - 10,000개 = 123ms

List 조회의 경우 get(index)를 사용하는 것이 일반적이다. 하지만 get은 해당 인덱스에 어떤 값이 담겨 있는지 아는 경우에만 사용할 수 있다. 그렇기 때문에 랜덤한 값의 존재 여부를 확인하는 contains()를 활용했다.

 

참고로 get()의 경우 조회 속도가 1,000,000개에서도 약 10ms내외로 상당한 속도를 보여줬다.

 

2-2. Map  -  조회 

// HashMap - 조회
getMap(1000);
getMap(10000);
getMap(100000);
getMap(1000000);

private static void getMap(int size) {
    hashMap = new HashMap<>();

    for(int i=0; i<size; i++) {
        hashMap.put(i, "value" + i);
    }

    start = System.currentTimeMillis();
    for(int i=0; i<size; i++) {
        int key = (int) (Math.random()*size);
        hashMap.get(key);
    }
    end = System.currentTimeMillis();
    System.out.println("HashMap       조회 - " + form.format(size) + "개 = " + (end-start) + "ms");
}

// 결과 값
HashMap       조회 - 1,000개 = 0ms
HashMap       조회 - 10,000개 = 0ms
HashMap       조회 - 100,000개 = 10ms
HashMap       조회 - 1,000,000개 = 111ms

해시함수를 통해 변환되어 저장되기 때문에 조회속도가 상당히 빠르다.

 

조회 속도 차이

List(순차) < Map < List(랜덤)

 

그렇다면 두 컬렉션은 어떠한 구조적 차이가 있어서 저장, 조회를 할 때 성능차이가 발생하는 걸까?

---

ArrayList의 구조

ArrayList의 경우 Object[]의 구조와 같다. 즉, 메모리에 연속적으로 저장되는 구조다. 다만 크기가 고정된 배열과는 달리 ArrayList는 크기가 가변적이다. 

 

배열과 구조가 같은데 크기가 가변적이라는 것은 결국 크기를 늘리거나 줄일 때 배열을 복사해서 옮겨야 함을 뜻한다.

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList를 생성할 때 인자를 주지 않으면 기본적으로 길이가 10인 빈 배열을 생성한다. 이 때, capacity(배열의 크기)와 size(배열에 저장된 데이터의 개수)의 개념 혼동에 주의해야 한다.

 

앞서 기술한 기본적인 구조를 통해 테스트 결과에 대해 알아보자. 

 

1. 순차 저장

add(E e)를 통해 값을 넣게 될 경우 배열의 마지막에 값을 넣게 된다. 이 때 size가 capacity와 같아지면 크기를 grow() 한다. 

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length) // size와 capacity가 같다면
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

private Object[] grow() {
    return grow(size + 1);
}

 

2. 랜덤 저장

랜덤 저장의 경우 특정 인덱스에 값을 삽입한다. 그렇기 때문에 size와 capacity비교를 통해 크기 변경을 해주고 중간에 값이 들어가 뒤에 있는 값들을 복사해야 한다.

https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4-Array-%EB%B0%B0%EC%97%B4-%EB%A6%AC%EC%8A%A4%ED%8A%B8-ArrayList-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-LinkedList

순차 저장의 경우 크기 변경(grow())이 없다면 배열의 복사를 하지 않지만 랜덤 저장의 경우는 매번 배열 복사가 이뤄지고 삭제를 할 때도 똑같다.

그렇기 때문에 특정 순서에 값을 저장하는 랜덤 저장은 ArrayList를 사용할 때 적절하지 않다. 만약 이러한 단점을 보완하는 List의 자료구조를 쓰고 싶다면 LinkedList를 사용하면 된다. 하지만 ArrayList보단 순차조회의 경우 속도가 떨어진다는 것을 알고 사용해야 한다.

 

3. 순차 조회

순차적으로 데이터를 가져올 경우 get()을 사용해 가져오면 된다. 인덱스로 데이터를 찾기 때문에 빠르다.

public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

 

4. 랜덤 조회

하지만 랜덤 조회의 경우 특정 데이터가 어떤 인덱스에 있는지 모를 경우 contains()를 통해 해당 값이 있는지 확인해야 한다. 또는 indexOf()를 통해 해당 인덱스를 알아내야 한다. 이 때, 내부적으로 반복문을 돌리기 때문에 속도가 느릴 수 밖에 없다.

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

만약 랜덤 조회라고 하더라도 값의 위치(인덱스)를 특정할 수 있는 경우는 get을 사용해 빠른 속도로 데이터를 조회할 수 있다.

---

HashMap의 구조

먼저 Map이라는 컬렉션에 대해 간단히 설명하자면 key(중복x)와 value(중복o)의 형태로 데이터를 저장하는 자료구조다.

HashMap은 이러한 key-value형태의 Map 속성을 해싱을 통해 구현한다. 

 

그렇다면 해싱은 무엇일까?

0	1	2	3	4	5	6
3	8	9	11	49	59	89

0	1	2	3	4	5	6	7
3	8	9	11	43	49	59	89

위와 같이 값이 정렬된 배열에서 11과 49사이에 43이라는 값을 삽입하기 위해선 49을 포함한 오른쪽의 모든 값들을 오른쪽으로 한 칸씩 옮겨야 한다. 이 때, O(n)이라는 적지 않은 비용이 발생한다. 

 

하지만 값들을 임의의 수로 일정하게 나눠서 삽입하게 되면 듬성듬성 데이터가 삽입된다. 예를 들어 값을 9라는 수로 나눴을 때 나머지값을 인덱스로 하는 배열을 만들어보자

0	1	2	3	4	5	6	7	8	9
9	8	11		49	59	3	43	89

기존의 값을 옮기지 않아도 데이터를 삽입할 수 있다.

이렇게 기존의 키값을 임의의 수 또는 다른 방법들로 해시값(인덱스)으로 만드는 것을 해시 함수라고 한다. 그리고 해시값을 인덱스로 값을 저장한 위와 같은 배열을 해시 테이블이라고 한다.

그리고 Java에서의 HashMap은 아래와 같은 Node라는 내부 클래스를 객체 배열로 만들어 테이블을 만든다.

 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        
        .
        .
        . 
 }

이게 해싱의 기본적인 방식이고 Java에서는 해당 방식을 응용해 사용한다.

좀 더 자세한 내용은 아래를 참고하자.

https://lordofkangs.tistory.com/78

 

1. 저장

put()을 이용해 키와 값을 저장하게 된다. 이때 키값은 위에서 설명한 해시함수를 통해 int형의 숫자로 변환이 된다. 

같은 해시값을 얻게 되는 상황을 충돌(conflict)이라고 부르는데, 충돌이 발생했을 때 이를 처리위한 로직이 있다. 이런 과정들 때문에 ArrayList의 순차 저장보다는 상대적으로 느린것으로 판단된다. 

 

2. 조회

키 값을 알고 있으면 해시함수를 통해 해시 값을 알 수 있기 때문에 대량의 데이터에서도 원하는 값을 빠르게 찾을 수 있다.

 

 

List vs Map(뭘 사용해야 할까?)

 정해진 답은 없다. 다만 강의 흐름 상 모든 데이터를 순차적으로 조회하는 것이 아니라 특정 값을 기준으로 조회하기 때문에 Map을 사용하는 것이 바람직했다. 이번 테스트의 결과에서 볼 수 있듯 상황에 따라 유용한 컬렉션을 사용하면 된다. 또한 각 컬렉션에 구현체가 ArrayList, HashMap만 있는 것은 아니기에 더 세세한 상황을 고려해야 한다.

 

ArrayList

• 데이터의 저장 순서가 보장되어야 하는 경우
• 특정 인덱스에 특정 값이 예상되는 경우
• 순서대로 데이터를 저장, 조회해야 하는 경우

HashMap 

• 데이터의 저장 순서가 보장되지 않아도 되는 경우
• 특정 키를 통해 값을 조회해야하는 경우
• 대량의 데이터를 빠른 속도로 조회, 저장, 삭제해야 하는 경우

 

 

전체코드 확인 

https://github.com/jonghunbaek/java-study/blob/master/src/listvsmap/ListVSMap.java