[ Java ] 자바 HashMap, ArrayList contains메소드 성능 비교

최근에 특정 모듈을 분석해서 다시 만들어야 하는 작업을 진행하였다.

해당 모듈이 약간 성능에 민감한 모듈이다 보니 가능한 한 빠르게 동작하도록 하였어야 했다.

그러다가 ArrayList.contains() 메서드로 된 부분이 있어 HashSet.continas으로 수정해 성능이 조금 높아 진 것을 확인했는데

기본적인 개념으로만 HashSet이 내부적으로 HashMap을 구현하고 있어서 빠를 것 같다는 생각을 했었는데

좀 더 자세히 알고 싶어 포스팅 하게 되었다.

[ HashSet.Contains() ]

내부적으로 HashSet은 HashMap Instance를 구현하고 있고 contains() 메서드를 호출하게되면 HashMap.containsKey(object)가 호출된다고 보면 된다. 자세한 설명은 밑을 참고하자.

Internally, the HashSet implementation is based on a HashMap instance. The contains() method calls HashMap.containsKey(object).

Here, it’s checking whether the object is in the internal map or not. The internal map stores data inside of the Nodes, known as buckets. Each bucket corresponds to a hash code generated with hashCode() method. So contains() is actually using hashCode() method to find the object’s location.

Now let’s determine the lookup time complexity. Before moving ahead, make sure you are familiar with Big-O notation.

On average, the contains() of HashSet runs in O(1) time. Getting the object’s bucket location is a constant time operation. Taking into account possible collisions, the lookup time may rise to log(n) because the internal bucket structure is a TreeMap.

This is an improvement from Java 7 which used a LinkedList for the internal bucket structure. In general, hash code collisions are rare. So we can consider the elements lookup complexity as O(1).

[ ArrayList.contains() ] 

ArrayList는 해당 값이 list에 있는지 판단하기 위해 내부적으로 indexOf(object) 메서드를 사용한다. indexOf(object) 메서드는 array 전체를 반복해서 돌고 각각의 element와 비교를 진행한다. 자세한 설명은 밑을 참고하자.

Internally, ArrayList uses the indexOf(object) method to check if the object is in the list. The indexOf(object)method iterates the entire array and compares each element with the equals(object) method.

Getting back to complexity analysis, the ArrayList.contains() method requires O(n) time. So the time we spend to find a specific object here depends on the number of items we have in the array. 

설명을 봤듯이 HashSet은 내부적으로 HashMap을 사용하고 ArrayList는 contains 메서드 내부에서 모든 element들을 돌며 비교작업을 진행하기 때문에 당연히 HashSet의 contains메서드가 빠를 수 밖에 없었던 것이다.

[ 테스트 코드 ]

1. 100만개의 String을 생성하여 HashSet, ArrayList를 만든다.

2. 500번 반복문을 돌며 Set과 List의 contains메서드를 사용해 확인한다.

HashSet Test

@Test
public void testHashSetContainsPerformance() {
    Set<String> testSet = new HashSet<>();
    String baseStr = "hellotheworld";
    Random generator = new Random();

    long start = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        testSet.add(baseStr + i);
    }
    long end = System.currentTimeMillis();
    System.out.println("Setup Performance : " + (end - start));

    long start2 = System.currentTimeMillis();
    int matchingCount = 0;
    for (int j =0; j < 500; j++) {
        if (testSet.contains(baseStr + generator.nextInt(5000))) {
            matchingCount++;
        }
    }
    long end2 = System.currentTimeMillis();
    System.out.println("HashSet Contains Performance : " + (end2 - start2));
}

ArrayList Test

@Test
public void testArrayListContainsPerformance() {
    List<String> testList = new ArrayList<>();
    String baseStr = "hellotheworld";
    Random generator = new Random();

    long start = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        testList.add(baseStr + i);
    }
    long end = System.currentTimeMillis();
    System.out.println("Setup Performance : " + (end - start));

    long start2 = System.currentTimeMillis();
    int matchingCount = 0;
    for (int j =0; j < 500; j++) {
        if (testList.contains(baseStr + generator.nextInt(5000))) {
            matchingCount++;
        }
    }
    long end2 = System.currentTimeMillis();
    System.out.println("ArrayList Contains Performance : " + (end2 - start2));
}

[ 결과 (시간단위 : ns) ]

결과를 보게되면 실제 set, list에 데이터를 쌓을 때는 hashset이 약 2배 정도 오래 걸리는 것을 알 수 있다. 

(아마 내부적으로 해쉬함수를 돌려 넣기 때문일 것으로 추정)

하지만 contains메서드의 hashset은 거의 시간이 안걸린다고 볼 수 있는 반면에 list는 set에 비해서는 꽤나 걸리는 것으로 볼 수 있다. 

따라서 한 번 데이터를 초기화해놓고 get이나 contains메서드를 사용할 일이 많은 시스템이라면 list보다는 set으로 자료구조를 가져가는 편이 좋다고 할 수 있을 것 같다.

포스팅을 마치도록 하겠습니다. 감사합니다.

도움이 되셨다면 광고 한 번 클릭해주시는 센스^_^

참고 : https://www.baeldung.com/java-hashset-arraylist-contains-performance