코드의 속도를 결정하는 내부 원리 (HashSet, 시간 복잡도)
프로그래밍을 하다 보면 '어떻게' 구현하는가만큼 '왜' 그렇게 동작하는지 이해하는 것이 중요하다는 것을 깨닫게 된다. 특히 대용량 데이터를 다룰 때, 자료구조의 내부 동작 방식과 알고리즘의 효율성에 대한 이해는 코드의 성능을 극적으로 좌우한다.
데이터의 중복을 효율적으로 제거하는 HashSet과 알고리즘의 성능을 평가하는 척도인 시간 복잡도 O(n), O(log n)는 그 중요성을 잘 보여주는 대표적인 예시다.
1. HashSet은 어떻게 중복을 허용하지 않는가?
List와 달리 Set은 데이터의 중복을 허용하지 않는다. 그중에서도 HashSet은 중복 여부를 매우 빠르게 판단하는데, 그 비결은 hashCode()와 equals() 메서드를 활용하는 내부 메커니즘에 있다.
A. 내부 동작 방식 - hashCode()와 equals()
HashSet은 내부적으로 데이터를 HashMap의 키(key)로 저장하여 관리한다. 새로운 데이터를 추가하는 과정은 다음과 같다.
-
hashCode()로 저장 위치 계산: 객체를 추가하면, 먼저 해당 객체의hashCode()메서드를 호출하여 고유한 정수 값(해시 코드)을 얻는다. 이 해시 코드를 통해 데이터가 저장될 내부 배열의 위치(bucket)를 즉시 계산한다. 이는 모든 데이터와 비교하지 않고 저장될 위치를 한 번에 찾아가는 과정이다. -
equals()로 최종 중복 확인: 만약hashCode()로 계산한 위치에 이미 다른 데이터가 존재한다면(해시 충돌), 그때 비로소equals()메서드를 호출한다.equals()는 두 객체의 내용이 실제로 동일한지 비교하여 최종적으로 중복 여부를 판단한다. 여기서true가 반환되면,HashSet은 이미 동일한 데이터가 존재한다고 판단하고 새 데이터의 추가를 거부한다.
Set<String> fruitSet = new HashSet<>();
fruitSet.add("Apple"); // 1. "Apple".hashCode() -> 위치 계산 후 저장
fruitSet.add("Banana"); // 2. "Banana".hashCode() -> 위치 계산 후 저장
fruitSet.add("Apple"); // 3. "Apple".hashCode() -> 기존 "Apple"과 같은 위치 발견
// 4. "Apple".equals(기존 "Apple") -> true 반환, 추가하지 않음이처럼 HashSet은 모든 데이터를 순차적으로 비교하는 대신, hashCode()를 통해 비교 대상을 최소화하고, 불가피한 경우에만 equals()로 정밀하게 비교한다. 이 방식 덕분에 데이터의 양이 아무리 많아져도 평균적으로 O(1), 즉 거의 일정한 속도로 데이터의 존재 여부를 확인할 수 있다.
언제 사용할까?
- 데이터의 중복을 제거해야 할 때
- 데이터의 저장 순서가 중요하지 않을 때
- 특정 데이터의 존재 여부를 빠르게 확인해야 할 때
2. 효율성의 척도: O(n) vs O(log n)
시간 복잡도는 데이터 크기(n)가 증가할 때 연산 횟수가 어떻게 변하는지를 나타내는 지표다. O(n)과 O(log n)은 가장 기본적인 개념이지만, 성능에서 극명한 차이를 보인다.
A. O(n)- 선형 탐색 (Linear Time)
데이터의 크기(n)와 연산 횟수가 정비례하는 방식이다.
- 예를 들어, 책장에서 원하는 책을 찾기 위해 첫 번째 칸부터 마지막 칸까지 하나씩 순서대로 확인하는 것과 같다. 운이 나쁘면 모든 책장을 다 확인해야 한다.
- 성능 같은 경우 데이터가 10배 늘어나면, 연산 횟수도 10배로 늘어난다. 직관적이지만 비효율적일 수 있다.
B. O(log n): 이진 탐색 (Logarithmic Time)
한 번의 연산마다 탐색 범위가 절반으로 줄어드는 방식이다. 이 방식은 데이터가 정렬되어 있다는 조건이 필수적이다.
- 전화번호부에서 특정 이름을 찾을 때, 앞에서부터 찾는 것이 아니라 가운데를 펼쳐서 찾으려는 이름이 앞부분에 있는지 뒷부분에 있는지 확인한다. 그리고 해당 부분에서 다시 가운데를 펼치는 과정을 반복한다. 매번 찾아야 할 범위가 절반씩 줄어든다.
- 데이터가 100만 개에서 200만 개로 2배 늘어나도, 필요한 연산은 단 1회만 추가된다. 이처럼 데이터가 폭발적으로 증가해도 연산 횟수는 매우 더디게 증가한다.
데이터 1백만 개일 때의 성능 차이
데이터의 크기(n)가 1,000,000개라고 가정했을 때, 최악의 경우 필요한 연산 횟수는 다음과 같다.
- O(n) - 약 1,000,000번의 연산이 필요하다.
- O(log n) - 단 약 20번의 연산이면 충분하다. (2^20 ≈ 1,048,576)
1백만 번과 20번. 실행 횟수가 압도적으로 많이 차이난다. 효율적인 알고리즘의 중요성을 명확히 알 수 있다.
결론
단순히 코드를 '작동'하게 만드는 것을 넘어, 그 코드가 '어떻게' 그리고 '얼마나 효율적으로' 작동하는지 이해하는 것은 개발자의 중요한 역량이다. 자료구조의 내부 동작 원리를 파악하고 시간 복잡도를 분석하는 습관은, 결국 더 빠르고 안정적인 소프트웨어를 만드는 단단한 기초가 될 것이다.
