[Java] HashSet과 boolean[]의 방문 처리 성능 비교

[프로그래머스] 숫자 변환하기, java

얼마 전 문제를 풀다가 발생한 궁금증입니다. HashSet의 contains(), boolean[]의 index를 이용한 접근 둘 다 O(1)의 시간 복잡도를 가지는 것으로 알고있는데, 과연 뭐가 더 빠를까?

 

같은 문제의 풀이에 방문처리로 사용해 본 HashSet의 contains(), boolean[]의 index를 이용한 접근은 다음과 같이 유의미한 시간의 차이를 보여주었습니다.

 

1. HashSet의 contains()

BFS, HashSet을 이용한 풀이

2. boolean[]의 index 접근

boolean[]의 index 접근

 

(실행한 코드는 최상단의 문제 풀이 링크에서 확인할 수 있습니다.)

 

이렇듯 같은 시간 복잡도를 가진 탐색이 왜 다른 시간소요를 보이는지 궁금해서 찾아보게 원인을 찾아보게 되었습니다.

---

원인 분석

1. 탐색 방식

두 가지의 탐색은 접근 방식에서 차이를 보입니다.

 

먼저 boolean[]의 경우입니다.

boolean[] visited = new boolean[y+1];

 

위와 같은 visited 배열이 있을 때, visited[a]에 접근하는 것은 a라는 인덱스를 이용하여 값에 접근하는 것 이기 때문에 메모리 접근이 매우 빠릅니다.

---

 

HashSet의 contains()의 경우입니다. HashSet은 다음과 같이 HashMap을 모체로 사용하며 비어있는 Object 객체를 value로 가지고, Key만을 사용하는 방식으로 사용됩니다.

HashSet의 구조?

 

그리고 contains() 또한 HashMap<>의 containsKey() 함수를 사용하게 됩니다.

contains는 conatinsKey

 

HashMap의 containsKey()는 다시 또 HashMap 내부의 getNode() 함수를 가지고 key를 찾아내게 되는데,

 

드디어 실제로 Key값을 찾아내는 코드를 볼 수 있게 되었습니다.

 

사실 실제로 이 코드를 딱 보았을 때, 쉽게 이해가 되지는 않았지만, 이리저리 찾아보아 getNode()의 과정을 대략 이해할 수 있었습니다. 과정은 다음과 같습니다.

 

1. HashMap은 입력 받은 key를 hash()함수와 &연산 등을 통해 배열의 인덱스를 찾습니다.

2. 해당 인덱스의 첫번째 노드가 원하는 key인지 확인하고, 맞을 경우 반환합니다. ( O(1) )

3. 아닐 경우 해시 충돌이 발생한 것으로 확인할 수 있습니다. 그래서 이를 위해 준비한 방식을 통해 연결되는 다음 노드들을 확인하여 key를 찾아냅니다.

 

사실 글을 쓰는 이 시점에도 완벽하게 이해를 하지는 못한 상태입니다. 하지만 여기서 알 수 있는 것은 원하는 Key 값을 찾아내기 위해 꽤나 많은 과정이 필요로 하게 되고, 해시 충돌이 발생하게 된다면, 추가로 더 많은 시간이 소요되게 됩니다.

 

2. 캐시 친화성 (Cache-friendliness)

CPU 캐시 메모리(Cache locality)는 프로그램의 실행 속도에 큰 영향을 끼칩니다.

 

- 배열(boolean[])은 메모리 상에서 연속적인 공간을 차지하므로 CPU 캐시(Locality of Reference)에 의해 빠르게 접근할 수 있습니다.

 

- HashSet<Integer>는 해시 테이블 구조로 인해 메모리 상에서 원소가 연속적으로 배치되지 않습니다. 즉, 캐시 미스(Cache miss)가 발생할 확률이 높아지고, 결국 추가적인 메모리 접근 비용이 발생하게 됩니다.

 

이 외에도 메모리를 사용하는 방식에서도 배열의 경우 미리 할당된 크기만큼만 메모리를 차지한다면, HashSet의 경우 동적으로 크기가 조정이 되며 추가적인 메모리를 사용하게 될 수도 있다는 차이가 있습니다.

 

결론

1. 실제 탐색하는 과정에서 차이 발생.

2. 캐시 친화성에 따른 차이 발생.

3. 메모리 할당 비용 또한 차이가 발생하게 됨.

 

따라서 가능한 경우에는 boolean[] 배열을 사용하는 것이 성능면에서 더 유리하다고 볼 수 있습니다.

 

 

개념적으로 알고 있었던, 시간 복잡도이지만 실제 테스트를 통해 차이가 발생할 수 있음을 알았습니다. 그리고 그 원인을 알아보는 과정에서 배운 점도 많이 있는 것 같습니다. 이러한 호기심을 계속해서 가져보도록 하겠습니다.