[Java] ArrayList 와 HashMap

자바 컬렉션 내 가장 많이 사용하는 자료구조 중 ArrayList 와 HashMap 이 있다. 사용하면서도 용도를 제대로 이해하지 않고 사용하는 것 같아 성능 및 사용 사례에 대해 정리해보려한다.

 

---

ArrayList 와 HashMap

1. ArrayList 

- 구조 :  내부적으로 데이터를 배열 형태로 저장하며 요소를 추가하거나 제거할 때 크기를 동적으로 조정한다.

- 접근 방법 : 인덱스를 통해 접근.

- 사용 사례 : 순서가 중요하거나 혹은 인덱스를 통한 빠른 접근이 필요할 때 사용한다.

- 크기 조정을 해야하는 경우 내부적으로 배열을 재할당하고 기존 요소를 새 배열로 복사해야하기 때문에 많은 양의 데이터를 추가하거나 삭제하는 경우 성능 저하가 발생할 수 있다. 

 

2. HashMap

- 구조 : 키-값 쌍으로 데이터를 저장하는 해시 테이블 구조를 가지고 있으며, 키는 고유하고 하나의 값에만 매핑된다.

- 접근 방법 : 특정 키를 통해 값에 접근.

- 사용 사례 : 키를 사용하여 데이터를 찾아야 할 때 사용한다.

- 해시 충돌이 발생하면 특정 키에 대한 접근 시간이 느려질 수 있으며 HashMap 은 요소의 순서를 보장하지 않는다. 

 

---

특정 값 조회 시 시간복잡도

1. ArrayList

- 시간복잡도 : 평균 O(n)

- 특정 값을 검색하기위해 시작부터 끝까지 리스트를 순차적으로 탐색해야 하기 때문에 최악의 경우 리스트의 모든 요소를 검사해야한다.

 

2. HashMap

- 시간복잡도 : 평균 O(1), 최악 O(n)

- 해시 함수를 사용해 키를 기반으로 값을 검색하기 때문에 평균적으로 O(1) 의 시간복잡도를 갖지만 해시 충돌이 많아서 많은 요소들이 동일한 해시 버킷에 위치할 때는 모든 요소를 검사해야 하므로 O(n)의 시간 복잡도를 가질 수 있다.

 

3. 검색 시간 확인하기

1000000 개의 데이터 중 임의의 타깃 문자열을 추가하여 검색 속도를 확인해보자.

public class SearchTest {
    public static void main(String[] args) {
        int cnt = 1000000; // 검색할 데이터 수
        String target = "limnj"; // 찾을 문자열
        List<String> list = createArrayList(cnt, target); // ArrayList 생성
        Map<Integer, String> map = createHashMap(cnt, target); // HashMap 생성

        // ArrayList 에서 타겟 검색
        long startTime = System.nanoTime();
        int index = list.indexOf(target);
        long endTime = System.nanoTime();
        System.out.println("ArrayList 검색 시간: " + (endTime - startTime) + " ns");

        // HashMap 에서 타겟 검색
        startTime = System.nanoTime();
        String value = map.get(cnt);
        endTime = System.nanoTime();
        System.out.println("HashMap 검색 시간: " + (endTime - startTime) + " ns");
    }
}

 

먼저 target 문자열을 앞 쪽에 추가하여 검색 시간을 확인해보자. 그럼 거의 비슷한 검색 시간이 걸린 것을 확인할 수 있다. 

..
    private static Map<Integer, String> createHashMap(int cnt, String target) {
        Map<Integer, String> map = new HashMap<>();
        map.put(cnt, target); // target 문자열
        for (int i = 0; i < cnt; i++) {
            map.put(i, "str " + i);
        }
        return map;
    }

    private static List<String> createArrayList(int cnt, String target) {
        List<String> list = new ArrayList<>();
        list.add(target); // target 문자열
        for (int i = 0; i < cnt; i++) {
            list.add("str " + i);
        }
        return list;
    }
}

- 실행 결과

 

그 다음으로 타깃 문자열을 가장 끝에 추가하여 다시 검색시간을 확인해보자. 

..
    private static Map<Integer, String> createHashMap(int cnt, String target) {
        Map<Integer, String> map = new HashMap<>();
        for (int i = 0; i < cnt; i++) {
            map.put(i, "str " + i);
        }
        map.put(cnt, target); // target 문자열
        return map;
    }

    private static List<String> createArrayList(int cnt, String target) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i < cnt; i++) {
            list.add("str " + i);
        }
        list.add(target); // target 문자열
        return list;
    }
}

- 실행 결과

 

ArrayList 검색 시간은 8998 ms, HashMap 검색 시간은 16.9 ms 로 순차적으로 탐색하는 ArrayList 검색 시간의 속도가 많이 느려졌음을 확인할 수 있다. 

 

---

정리

인덱스를 통해 접근해야하거나 데이터를 순서대로 처리해야하는 경우 ArrayList 가, 키를 통해 빠른 접근을 해야할 때는 HashMap 이 적합해보인다. 이 뿐만 아니라 각 상황에 맞는 자료 구조를 고민해보는 것이 좋을 것 같다.

 

 

참고

https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

https://www.geeksforgeeks.org/difference-between-arraylist-and-hashmap-in-java/

https://www.javatpoint.com/arraylist-vs-hashmap-in-java

https://www.baeldung.com/java-arraylist-vs-linkedlist-vs-hashmap