[JAVA / 자바] ArrayList vs HashSet

이번 포스팅은 ArrayList와 HashSet을 어떤 상황에 사용하면 좋을 지에 대해 말해보려 한다.

 

이전에 성능과 상관없이 코드를 작성할 때는 굳이 HashSet은 사용하지 않았다. 왜냐면 정렬도 되지 않고 순서를 보장해주지 않기 때문이다. 그러나, 알고리즘 문제를 풀면서 HashSet을 다시 보게 되었고 그래서 두 자료형에 대해 장단점을 비교하여 어떤 상황에서 어떤 선택이 좋은 선택이 될지 알아보겠다.

---

  성질  

List는 중복을 허용, 순서를 보장
Set은 중복을 허용하지 않음, 순서를 보장하지 않음

 

위 성질을 바탕으로 우린 다음 두 가지를 비교해 볼 수 있다.

  1. 중복의 허용

  2. 순서의 보장

 

그렇다면 순서가 상관없으면서 중복 없이 저장하고 싶을 때만 Set자료형을 사용해주면 되는 것이 아닌가?라고 생각할 수 있을 것이다.

결론부터 말하자면 반은 맞고 반은 틀린 얘기이다.

 

---

 탐색 성능 

ArrayList와 HashSet의 탐색 성능에는 정말 상당한 차이가 난다.

다음 코드를 작성하여 각각의 탐색 시간을 알아보겠다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.stream.IntStream;
import java.time.Instant;
import java.time.Duration;

public class Main {
    public static void main(String args[]) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        HashSet<Integer> hashSet = new HashSet<>();
        
        // ArrayList와 HashSet에 각각 0~10000000까지의 수 저장
        IntStream.range(0, 10000000).forEach(value -> {
            arrayList.add(value);
            hashSet.add(value);
        });
        
        // ArrayList 탐색 시간
        Instant start = Instant.now();
        arrayList.contains(9876543);
        Instant end = Instant.now();
        long elapsedTime = Duration.between(start, end).toMillis();
        System.out.println("ArrayList search time : " + elapsedTime + "ms"); // 탐색시간
		
        // HashSet 탐색 시간
        start = Instant.now();
        hashSet.contains(9876543);
        end = Instant.now();
        elapsedTime = Duration.between(start, end).toMillis();
        System.out.println("HashSet search time : " + elapsedTime + "ms"); // 탐색시간
    }
}

결괏값은 다음과 같다 >>>

엄청난 시간 차이를 보이고 있다.

ArrayList에서는 46ms가 걸린 반면에 HashSet에서는 0ms 즉, 밀리초 단위로 측정이 불가능하다는 뜻이다. 이처럼 탐색에서 정말 강한 성능을 HashSet이 보여주고 있다.

 

물론 두 자료형의 자료의 양, 그리고 탐색하려는 자료의 저장 위치에 따라 성능 차이는 증가할 수도, 감소할 수도 있다.

ArrayList

①리스트의 크기가 클수록 찾으려는 ②원소의 저장 위치가 뒤(나중)일수록 원소의 탐색 시간이 오래 걸리지만,

HashSet

저장된 원소의 양이 많던 작던 몇 번째로 저장했던 상관없이 거의 동일하게 매우 짧은 시간 내에 검색이 가능하다.

 

이는 둘의 저장 방식, 탐색 방식의 차이 때문이다.

ArrayList 

저장 : 저장된 순서대로 차례대로 List에 저장

탐색 : 맨 앞에서부터 순차적으로 하나씩 탐색하면서 저장 유무를 판단한다.

 

HashSet

저장 : 저장된 순서와 상관없이 Hash값을 사용하여 저장

탐색 : 탐색할 원소의 해시값을 구해 해당 해시값을 저장한 위치에 저장된 원소와 비교하여 탐색한다.

---

결론은 다음과 같다.

 

ArrayList

  1. 배열을 정렬할 필요가 있는 경우

  2. 배열에 중복된 원소를 저장해야 하는 경우

  3. 배열에 저장된 순서가 필요한 경우

  4. 배열에 저장된 원소를 호출해야 하는 경우

 

HashSet

  1. 배열에 저장된 원소를 호출할 필요 없는 경우

  2. 배열에 중복이 허용되지 않은 경우

  3. 배열에 순서가 중요하지 않은 경우

  4. 저장 유무만 판단하면 되는 경우

 

상황에 맞게 ArrayList나 HashSet을 사용해주면 된다.