위클리페이퍼03: 알고리즘과 자료 구조

Q1. HashSet의 내부 동작 방식과 중복 제거 메커니즘을 설명하고, HashSet이 효율적인 중복 체크를 할 수 있는 이유를 설명해주세요.

Q1-1. HashSet과 내부 동작 방식

HashSet은 중복을 허용하지 않는 Set의 구현체고, 내부적으로 HashMap을 사용해 구현되어 있습니다.
입력된 원소를 HashMap의 Key로 사용하고, Value에는 의미 없는 더미 객체를 저장합니다.

Q1-2. 중복 제거 메커니즘

원소가 추가될 때

• 먼저, hashCode()를 사용해 해시값을 계산하고,
• 이 해시값을 기반으로 입력된 원소가 저장될 버킷을 찾습니다.
  • 여기서 버킷(Bucket)은 해시 테이블 안에서 데이터를 담는 칸
• 만약 해당 버킷에 기존에 저장된 원소가 존재한다면 equals() 메서드를 이용해 동일한 원소인지 비교합니다.
• equals()의 결과가 true면 같은 원소가 이미 존재한다고 판단하고 새롭게 추가하지 않습니다.

Q1-3. 효율적으로 중복 체크가 가능한 이유

모든 원소를 처음부터 순회하는 방법보다, HashSet은 생성된 해시값을 기반으로 저장될 버킷을 빠르게 찾아갈 수 있습니다. 전체 원소를 확인할 필요 없이 해당 버킷의 원소만 확인하면 되기 때문에 평균 O(1)의 시간복잡도를 가질 수 있습니다.

다만 해시 충돌이 많이 발생한다면 같은 버킷 안에서 여러 원소를 비교해야 하기 때문에 항상 O(1)인 것은 아닙니다.

Q1-4. 추가 정보

hashCode()와 equals()의 역할

객체 obj가 들어왔다고 가정해보면 (set.add(obj);)
obj.hashCode() 값을 이용해 해시값을 계산하고, 이 해시값을 기반으로 HashMap 내부에 어느 버킷을 확인해야 할지 결정합니다.

하지만 서로 다른 두 객체라도 같은 해시값을 가질 수 있는 해시 충돌(Hash Collision)이 발생할 수 있습니다.
그래서 같은 버킷에 이미 원소가 존재한다면 equals()를 이용해 실제로 동일한 원소인지 확인합니다.
만약 equals()의 결과가 true라면 “이미 존재하는 원소”라고 판단해서 입력된 원소를 추가하지 않습니다.

Q2. O(n)과 O(log n)의 성능 차이를 실생활 예시를 들어 설명하고, 데이터의 크기가 1백만 개일 때 각각 대략 몇 번의 연산이 필요한지 비교해주세요.

Q2-1. O(n)

O(n)은 데이터의 크기 n이 증가하는 만큼 필요한 연산 횟수도 비례해서 증가하는 시간 복잡도입니다.

예를 들면 전화번호부에서 특정 사람의 이름을 찾는데 첫 페이지부터 한 명씩 순서대로 확인하는 것이 있습니다. 찾으려는 사람이 어디에 있는지 바로 확인할 수 없기 때문에 처음부터 순차적으로 확인해야 하고, 데이터가 많아질수록 확인해야 하는 횟수도 함께 증가합니다.

Q2-2. O(log n)

O(log n)은 한 번의 연산마다 탐색해야 하는 데이터의 범위를 일정 비율로 줄여나가는 시간 복잡도입니다.

예를 들어 이름순으로 정렬된 전화번호부에서 특정 사람을 찾는다고 가정해 보겠습니다. 전화번호부의 중간 부분을 먼저 확인하고, 찾고 있는 이름이 중간 부분에서 확인한 이름보다 앞에 있다면 앞쪽 절반을 확인하고, 뒤에 있다면 뒤쪽 절반만 확인합니다.

이 과정을 반복하면 한 번 확인할 때마다 탐색 범위가 절반으로 줄어듭니다.

Q2-3. 데이터가 100만 개일 때 비교를 해본다면

O(n) 방식으로 탐색한다면 원하는 값을 찾기 위해서 순차적으로 탐색해야 하기 때문에 평균적으로 약 50만 번 비교해야 합니다.

• 1~100만 번째까지 데이터가 존재한다면 평균 비교 횟수는 (1 + 1,000,000) / 2 = 500,000.5가 계산됨(등차수열 평균 이용)

O(log n) 방식으로 탐색한다면 원하는 값을 찾기 위해서 탐색 범위를 절반씩 좁히기 때문에 약 20번 비교해야 합니다.

• 2^20 = 1,048,576이기 때문에 약 20번 비교로 100만 개의 데이터 범위를 좁힐 수 있음