[👾코드잇] 위클리 페이퍼(4)

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

HashSet은 자바의 컬렉션 프레임워크 중 하나로, 중복을 허용하지 않는 데이터 집합을 저장할 때 사용한다. HashMap을 기반으로 동작하고, 해시 기반 구조이기 때문에 빠른 검색과 중복제거가 가능하다. 

 

HashSet의 내부 동작 방식

HashSet에 원소를 추가하면 HashMap의 put(key, value)메서드를 호출한다.

여기서 key는 내가 추가한 객체이고, value는 모두 동일한 상수 객체이다. 일단 hashmap은 put(k , v) 구조여서 value를 무시할 수 없기 때문에 걍 "이 key가 존재한다"는 표시용으로 아무 객체나 넣어주는 걸로 생각하면 된다! 즉 value는 더미같은 것이다.

 

HashSet의 중복 제거 메커니즘

핵심은 hashCode()와 equals()

1. 원소를 추가하고 내부적으로 put(e, PRESENT)가 실행된다.

2. 객체 e의 hashCode()를 호출하여 적절한 슬롯을 찾는다. 이때 만약 해당 슬롯에 객체가 존재한다면, 그 객체들과 equals()로 비교한다.

3. 비교 후 true인 객체가 있다면 중복된 것으로 간주하여 추가하지 않는다.

4. 그렇지 않으면 해당 버킷에 추가한다.

 

➡️ 이런 과정이 효율적인 이유

해시기반 탐색이라서 그렇다. 

HashSet은 평균적으로 O(1) 시간 복잡도로 검색, 추가, 제거할 수 있는데 이는 해시 함수를 통해서 빠르게 위치를 찾을 수 있기 때문이다. 

 

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

둘 다 알고리즘 성능을 나타내는 시간 복잡도 개념이다. 데이터가 많아질 수록 둘의 차이는 기하급수적으로 커진다.

 

O(n)

-데이터의 개수만큼 순차적으로 처리하는 것

-선형 증가이므로 성능은 비교적 느리다.

-필요한 물건을 찾기 위해서 매대의 처음부터 끝까지 일일이 찾는 것과 같다.

➡️ 만약 물건이 1백만 개 있다면 물건을 찾기 위해 1백만 개의 물건을 모두 확인해야 할 수도 있다.

 

O(log n)

-데이터를 절반씩 나누면서 처리하는 것

-로그 증가이므로 성능이 비교적 빠르다.

-이름 순으로 정렬된 전화번호부에서 이진탐색을 하는 경우와 같다. 중간 페이지를 펼쳐 이름을 확인하고, 찾는 이름이 그 페이지보다 앞에 있을지 뒤에 있을지를 판단하여 범위를 절반으로 좁혀가며 탐색하는 방법이다.

➡️ 이렇게 하면 대략 1백만명 중에서는 20번의 시도 정도만으로도 찾을 수 있다.

 

 

끗