[자료구조] 맵(Map), 셋(Set), 해시테이블(Hash Table)
✒️ 0. 들어가기 전
이 글에서는 주로 키-값 쌍을 저장하거나 고유한 값을 저장하는 데 사용되는 자료구조들에 대해 설명한다.
해시테이블의 구현 방식과 맵, 셋의 활용 사례를 포함하여 배워보자!
✒️ 1. Map (맵)
Map은 고유한 키를 기반으로 값(Value)을 저장하는 키-값(Key-Value) 쌍의 자료구조이다.
삽입 시 자동으로 정렬되며, 이는 레드-블랙 트리(Red-Black Tree)를 사용해 구현된다.
Map의 주요 특징은 고
유한 키를 기반으로 하며, 중복 키를 허용하지 않는다는 점이다.
💡 시간복잡도
- 참조(Access): O(log n)
- 탐색(Search): O(log n)
- 삽입/삭제(Insertion/Deletion): O(log n)
💡 특징
Map은 키를 기준으로 자동 정렬되기 때문에, 키의 삽입 순서에 상관없이 오름차순으로 정렬된다.
이를 통해 키-값 쌍을 효율적으로 탐색할 수 있다.
예를 들어, "아무개": 1, "김땡땡": 2와 같이 문자열 키와 정수 값을 저장할 때 유용하다.
💡 주요 메서드
- insert({key, value}): Map에 키-값 쌍을 삽입
- [key] = value: 대괄호 연산자를 통해 키에 값을 할당
- [key]: 대괄호 연산자를 통해 해당 키의 값을 참조합니다. 없을 경우 초기값이 할당
- size(): Map의 요소 개수를 반환
- erase(key): 특정 키를 삭제
- find(key): 특정 키를 검색해 이터레이터를 반환합니다. 못 찾으면 mp.end() 반환
- clear(): Map의 모든 요소를 삭제
✒️ 2. Set (셋)
Set은 고유한 요소만을 저장하는 자료구조로, 중복을 허용하지 않는다.
Map과 유사하게 자동 정렬되며, 메서드도 Map과 유사하다.
주로 중복을 방지하고 고유한 값을 관리할 때 사용된다.
💡 시간복잡도
- 참조(Access): O(log n)
- 탐색(Search): O(log n)
- 삽입/삭제(Insertion/Deletion): O(log n)
✒️ 3. Hash Table (해시 테이블)
Hash Table은 해시 함수를 이용해 데이터를 저장하는 자료구조이다.
키(Key)를 해시 함수로 변환하여 해시 값을 얻고, 이를 통해 고정된 크기의 배열에 값을 저장한다.
이는 데이터 검색을 매우 빠르게 해준다.
💡 해시, 해싱, 해시 함수 ??
용어에 대해 한 번 정리해보자.
- 해시(Hash): 데이터를 고정된 길이의 값으로 매핑한 결과.
- 해싱(Hashing): 데이터를 해시 값으로 변환하는 과정.
- 해시 함수(Hash Function): 데이터를 해시 값으로 변환하는 함수.
💡 예시
let a = [1, 2, 42, 4, 12, 14, 17, 13, 37]
const hashf = num => num % 20
a = a.map(e => hashf(e))
console.log(a)
/* [
1, 2, 2, 4,12, 14, 17, 13, 17
] */
앞의 코드를 보면 해시함수가 “%20” 임을 볼 수 있는데 보통 해시테이블의 해시함수는 % 연산자가 들어가는 경우가 많다.
이를 통해 유한한값의 키를 만들수가 있다.
💡 시간복잡도
- 평균 시간 복잡도: O(1)
참조, 탐색, 삽입/삭제 모두 O(1)의 시간 복잡도를 가진다.
- 최악의 시간 복잡도: O(n)
해시 충돌이 발생하면 O(n)의 시간 복잡도가 소요될 수 있다.
💡 해시 테이블 충돌 해결
해시테이블을 보면 같은 해시값이 나타나는 것을 볼 수 있다.
이 때문에 충돌문제(hash collision)가 발생한다.
테이블이 아무리 커도 거의 무조건 충돌한다.
이를 어떻게 해결해야 할까? (짧게만 어떤 방법이 있는지만 알아보자.)
체이닝(Chaining): 충돌이 발생하면 연결 리스트에 데이터를 추가하여 해결한다.
개방 주소법(Open Addressing): 충돌 시 다른 위치에 데이터를 삽입한다. (선형 탐색, 제곱 탐색, 이중 해싱)
📝 면접 예상 질문
Q. Map과 Set의 차이점은 무엇인가요?
A. Map은 고유한 키-값 쌍을 저장하는 자료구조이며, 각 키는 하나의 값과 매핑됩니다. 반면 Set은 고유한 값을 저장하며, 중복된 요소를 허용하지 않는다는 점에서 차이가 있습니다. Map은 키-값 쌍으로 이루어져 있고, Set은 키만 있는 형태라고 볼 수 있습니다.
Q. Hash Table과 Map의 차이점은 무엇인가요?
A. Hash Table은 해시 함수를 이용해 데이터를 저장하는 자료구조로, 평균적으로 O(1)의 시간 복잡도를 가집니다. 반면, Map은 이진 탐색 트리(레드-블랙 트리)를 사용해 데이터를 저장하고 자동으로 정렬하며, 시간 복잡도는 O(log n)입니다. Hash Table은 순서가 없지만, Map은 키가 정렬된 상태로 저장됩니다.
Q. 왜 Hash Table의 평균 시간 복잡도는 O(1)인가요?
A. Hash Table은 데이터를 해시 함수로 변환해 고정된 크기의 배열 인덱스로 접근하기 때문에 평균적으로 O(1)의 시간 복잡도를 가집니다. 이로 인해 검색, 삽입, 삭제 작업이 배열 인덱스를 이용하는 것처럼 빠르게 수행될 수 있습니다.
Q. Hash Table의 최악 시간 복잡도는 왜 O(n)인가요?
A. Hash Table에서 해시 충돌이 빈번하게 발생하면, 동일한 해시 값을 가진 모든 요소를 탐색해야 합니다. 이 경우 해시 테이블의 각 버켓이 연결 리스트로 구현되어 있다면 최악의 경우 모든 요소를 탐색해야 하므로 시간 복잡도는 O(n)이 될 수 있습니다.
Q. 그렇다면, Hash Table에서 해시 충돌(Hash Collision)이 발생했을 때 어떻게 해결할 수 있나요?
A. 해시 충돌을 해결하는 방법으로는 **체이닝(Chaining)**과 **개방 주소법(Open Addressing)**이 있습니다. 체이닝은 충돌 시 연결 리스트에 데이터를 추가하는 방식이고, 개방 주소법은 다른 버켓을 찾아 데이터를 삽입하는 방식입니다. 개방 주소법에는 선형 탐색, 제곱 탐색, 이중 해싱 등의 기법이 있습니다.