자료구조를 공부하다 보면 HashSet과 HashMap은 데이터를 평균 O(1)의 시간복잡도로 탐색한다고 배운다.
배열에서 데이터를 순서대로 찾으면 최악의 경우 모든 데이터를 확인해야 한다. 그런데 해시 자료구조는 데이터가 많아져도 어떻게 원하는 값을 빠르게 찾을 수 있을까?
이 글에서는 코드조선의 Hash Set과 Hash Map 강의를 바탕으로 해시 함수, 해시 충돌, 선형 탐사, HashSet과 HashMap의 차이를 정리한다. 강의에서는 C 언어로 단순화한 해시 자료구조를 직접 구현하면서 동작 원리를 설명한다.
1. 배열 탐색은 왜 느려질까?
다음과 같은 문자열 배열이 있다고 가정한다.
const char* names[] = {
"Kim",
"Lee",
"Park",
"Choi",
"Jung"
};배열에서 "Choi"를 찾으려면 앞에서부터 하나씩 비교해야 한다.
for (int i = 0; i < 5; i++) {
if (strcmp(names[i], "Choi") == 0) {
printf("찾았습니다.\n");
break;
}
}찾으려는 데이터가 배열의 마지막에 있거나 존재하지 않는다면 배열 전체를 확인해야 한다.
데이터가 N개라면 최악의 경우 N번 비교하므로 시간복잡도는 다음과 같다.
O(N)데이터가 10개일 때는 큰 문제가 아니다. 하지만 데이터가 수십만 개 이상이라면 매번 처음부터 확인하는 방식은 비효율적이다.
2. 해시 함수란 무엇인가?
해시 자료구조는 데이터를 처음부터 탐색하지 않는다. 대신 데이터가 저장될 위치를 계산한다.
이때 사용하는 것이 해시 함수이다.
데이터 → 해시 함수 → 해시값 → 배열 인덱스예를 들어 문자열을 숫자로 변환하는 단순한 해시 함수가 있다고 가정한다.
unsigned int hashString(const char* text) {
unsigned int hash = 0;
while (*text != '\0') {
hash += (unsigned char)*text;
text++;
}
return hash;
}문자열의 각 문자를 숫자로 바꿔 모두 더한 값을 반환한다.
그러나 해시값을 배열의 인덱스로 바로 사용할 수는 없다. 해시값이 배열 크기보다 클 수 있기 때문이다.
따라서 배열 크기로 나눈 나머지를 사용한다.
index = hashString(key) % CAPACITY;배열 크기가 7이고 해시값이 24라면 다음과 같이 계산한다.
24 % 7 = 3따라서 데이터는 배열의 3번 인덱스에 저장된다.
데이터를 찾을 때도 같은 해시 함수를 사용한다.
저장할 때: key → 해시 함수 → 3번 인덱스
찾을 때: key → 해시 함수 → 3번 인덱스처음부터 배열을 탐색하지 않고 계산된 위치로 바로 이동할 수 있는 것이다.
3. 해시 테이블의 크기를 소수로 정하는 이유
영상의 단순화된 구현에서는 해시 테이블의 크기로 7과 같은 소수를 사용한다.
#define CAPACITY 7해시 테이블의 인덱스는 보통 나머지 연산으로 계산한다.
index = hashValue % CAPACITY;배열의 크기가 특정 해시값 패턴과 공약수를 많이 가지면 데이터가 일부 인덱스에 집중될 수 있다.
예를 들어 해시값이 모두 짝수이고 배열의 크기도 짝수라면 특정 위치가 반복해서 선택될 가능성이 커진다.
소수 크기를 사용하면 이러한 규칙적인 패턴을 줄이는 데 도움이 된다. 특히 나머지 연산과 선형 탐사를 사용하는 단순한 해시 테이블에서 이해하기 쉬운 선택이다.
다만 실제 라이브러리가 반드시 소수 크기만 사용하는 것은 아니다. 구현 방식에 따라 2의 거듭제곱 크기를 사용하고 해시값의 비트를 별도로 섞기도 한다.
핵심은 테이블 크기 자체보다 데이터가 가능한 한 여러 인덱스에 고르게 분산되도록 만드는 것이다.
4. 서로 다른 데이터의 인덱스가 같다면?
해시 함수를 사용해도 모든 데이터가 서로 다른 인덱스를 가지는 것은 아니다.
예를 들어 다음과 같은 결과가 나올 수 있다.
hash("Kim") % 7 = 3
hash("Park") % 7 = 3서로 다른 두 문자열이 같은 인덱스 3을 얻게 된다.
이러한 현상을 해시 충돌이라고 한다.
Kim ─┐
├─→ 3번 인덱스
Park ─┘해시 충돌은 해시 함수가 잘못되었다는 의미가 아니다. 저장할 수 있는 데이터의 종류는 매우 많지만 배열의 인덱스 개수는 한정되어 있으므로 충돌을 완전히 피할 수는 없다.
따라서 해시 자료구조에는 충돌을 처리하는 방법이 반드시 필요하다.
5. 선형 탐사로 충돌 해결하기
영상의 단순화된 구현에서는 선형 탐사 방식으로 해시 충돌을 처리한다.
선형 탐사는 원래 위치가 이미 사용 중이라면 바로 다음 칸을 확인하는 방법이다.
다음과 같이 3번 인덱스에 데이터가 이미 저장되어 있다고 가정한다.
0 1 2 3 4 5 6
Kim새로운 데이터 "Park"의 인덱스도 3으로 계산되었다면 다음 칸을 확인한다.
3번 사용 중 → 4번 확인 → 비어 있음 → 4번에 저장결과는 다음과 같다.
0 1 2 3 4 5 6
Kim Park이를 코드로 표현하면 다음과 같은 형태가 된다.
int startIndex = hashString(key) % CAPACITY;
int index = startIndex;
do {
if (table[index] == NULL) {
table[index] = key;
return 1;
}
index = (index + 1) % CAPACITY;
} while (index != startIndex);
return 0;다음 인덱스를 계산할 때 다시 나머지 연산을 사용한다.
index = (index + 1) % CAPACITY;현재 인덱스가 마지막인 6이라면 다음 위치는 다음과 같다.
(6 + 1) % 7 = 0배열의 끝에 도달하면 다시 배열의 처음으로 돌아간다. 배열을 원형으로 탐색하는 것과 같은 효과가 발생한다.
처음 시작했던 인덱스로 다시 돌아왔다면 모든 칸을 확인했다는 의미이므로 탐색을 종료해야 한다.
6. HashSet이란 무엇인가?
HashSet은 중복되지 않는 데이터를 저장하는 자료구조이다.
{"Kim", "Lee", "Park"}같은 데이터를 다시 삽입해도 하나만 저장한다.
"Kim" 삽입 → 성공
"Lee" 삽입 → 성공
"Kim" 삽입 → 이미 존재하므로 실패HashSet에 필요한 대표적인 기능은 다음과 같다.
Insert(&set, "Kim");
Contains(&set, "Kim");
Delete(&set, "Kim");HashSet은 특정 데이터의 존재 여부가 중요할 때 사용한다.
예를 들면 다음과 같다.
- 방문한 사용자 ID를 저장한다.
- 중복된 이름이나 번호를 제거한다.
- 이미 처리한 데이터를 기록한다.
- 게임에서 획득한 아이템 종류를 관리한다.
- 특정 값이 목록에 포함되어 있는지 빠르게 검사한다.
HashSet에는 데이터 하나만 저장한다. 데이터와 연결된 추가 정보는 저장하지 않는다.
HashSet = {데이터, 데이터, 데이터}
7. 중복 데이터는 어떻게 확인할까?
새로운 데이터를 삽입할 때는 빈칸만 찾으면 되는 것이 아니다. 같은 데이터가 이미 저장되어 있는지도 검사해야 한다.
if (table[index] != NULL &&
strcmp(table[index], key) == 0) {
return 0;
}문자열의 해시값이 같다고 해서 반드시 같은 문자열인 것은 아니다. 서로 다른 문자열이 같은 해시값을 가질 수도 있기 때문이다.
따라서 일반적인 탐색 과정은 다음과 같다.
1. key의 해시값을 계산한다.
2. 시작 인덱스를 계산한다.
3. 해당 위치의 실제 데이터와 key를 비교한다.
4. 다르면 충돌 처리 규칙에 따라 다음 위치를 확인한다.
5. 같은 데이터를 찾거나 빈칸을 만나면 탐색을 종료한다.해시값은 데이터를 찾을 후보 위치를 결정한다. 최종적으로 같은 데이터인지 확인하려면 실제 값의 비교도 필요하다.
8. 선형 탐사에서 삭제할 때 주의할 점
선형 탐사를 사용하는 해시 테이블에서는 데이터를 삭제할 때 단순히 빈칸으로 만들면 문제가 발생할 수 있다.
다음과 같은 상태를 가정한다.
3번: Kim
4번: Park
5번: Lee세 데이터가 충돌로 인해 연속된 위치에 저장되었다고 한다.
이때 4번의 "Park"를 완전히 빈칸으로 만들면 다음 상태가 된다.
3번: Kim
4번: 비어 있음
5번: Lee이후 "Lee"를 탐색할 때 3번부터 확인한다고 가정한다.
3번 확인 → 다른 데이터
4번 확인 → 비어 있음탐색 알고리즘이 빈칸을 보고 종료하면 5번에 있는 "Lee"를 찾지 못한다.
따라서 선형 탐사 방식에서는 슬롯의 상태를 구분할 필요가 있다.
typedef enum {
EMPTY,
OCCUPIED,
DELETED
} SlotState;각 상태의 의미는 다음과 같다.
| EMPTY | 처음부터 데이터가 저장된 적이 없는 칸이다. |
| OCCUPIED | 현재 데이터가 저장된 칸이다. |
| DELETED | 데이터가 있었지만 삭제된 칸이다. |
탐색 중 EMPTY를 만나면 데이터가 없다고 판단할 수 있다. 하지만 DELETED를 만나면 뒤에 데이터가 있을 수 있으므로 계속 탐색해야 한다.
이러한 삭제 표시를 흔히 삭제 마커 또는 tombstone이라고 한다.
9. HashMap이란 무엇인가?
HashSet이 데이터의 존재 여부를 저장한다면, HashMap은 키와 값을 한 쌍으로 저장한다.
Key → Value예를 들어 게임의 몬스터 정보를 다음과 같이 저장할 수 있다.
"Slime" → 체력 30
"Goblin" → 체력 80
"Dragon" → 체력 1000여기에서 몬스터 이름은 Key, 체력은 Value이다.
typedef struct {
const char* key;
int value;
} Entry;HashMap은 키에 해시 함수를 적용해 저장 위치를 계산한다.
index = hashString(key) % CAPACITY;배열의 각 칸에는 키만 저장하는 것이 아니라 키와 값이 함께 저장된다.
인덱스 0: 비어 있음
인덱스 1: {"Slime", 30}
인덱스 2: 비어 있음
인덱스 3: {"Dragon", 1000}값을 가져올 때는 키를 전달한다.
int hp = Get(&monsterMap, "Dragon");HashMap은 다음과 같은 상황에 적합하다.
- 이름으로 전화번호를 찾는다.
- 사용자 ID로 사용자 정보를 찾는다.
- 상품 코드로 가격을 찾는다.
- 단어별 등장 횟수를 저장한다.
- 몬스터 이름으로 능력치를 찾는다.
- 파일 이름으로 파일 정보를 찾는다.
10. HashSet과 HashMap의 차이
두 자료구조 모두 해시 함수를 사용해 저장 위치를 계산한다. 가장 큰 차이는 무엇을 저장하느냐에 있다.
| 저장 형태 | 데이터 하나 | Key–Value 쌍 |
| 중복 | 같은 데이터 저장 불가 | 같은 Key 저장 불가 |
| 주요 목적 | 존재 여부 확인 | Key를 이용한 Value 탐색 |
| 삽입 예시 | add("Kim") | put("Kim", 95) |
| 탐색 결과 | 존재 여부 | Key와 연결된 Value |
| 활용 예시 | 중복 제거 | 이름별 점수 저장 |
HashSet은 다음 질문에 답한다.
"Kim"이 존재하는가?HashMap은 다음 질문에 답한다.
"Kim"과 연결된 값은 무엇인가?예를 들어 출석 여부만 확인한다면 HashSet이 적합하다.
출석한 학생 = {"Kim", "Lee", "Park"}학생별 점수까지 저장해야 한다면 HashMap이 적합하다.
학생별 점수 = {
"Kim": 90,
"Lee": 85,
"Park": 100
}
11. 해시 자료구조의 시간복잡도
해시 함수가 데이터를 여러 위치에 고르게 분산하고 충돌이 많지 않다면 삽입, 탐색, 삭제는 평균적으로 O(1)에 동작한다.
| 삽입 | O(1) | O(N) |
| 탐색 | O(1) | O(N) |
| 삭제 | O(1) | O(N) |
평균 시간복잡도가 O(1)인 이유는 해시 함수를 이용해 데이터가 있을 것으로 예상되는 위치로 바로 이동하기 때문이다.
하지만 모든 데이터의 해시값이 같은 인덱스로 몰리면 충돌이 계속 발생한다.
시작 위치 확인
→ 다음 칸 확인
→ 다음 칸 확인
→ 다음 칸 확인
→ ...최악의 경우 배열의 모든 칸을 확인해야 하므로 O(N)이 된다.
따라서 해시 자료구조에서 중요한 것은 단순히 해시 함수를 사용하는 것만이 아니다.
- 해시값을 고르게 분산해야 한다.
- 테이블이 지나치게 가득 차지 않도록 관리해야 한다.
- 충돌 처리 방법이 필요하다.
- 필요하면 테이블 크기를 늘리고 데이터를 다시 배치해야 한다.
12. 적재율이 높아지면 충돌도 증가한다
해시 테이블이 얼마나 차 있는지를 적재율이라고 한다.
적재율 = 저장된 데이터 수 / 전체 슬롯 수슬롯이 10개이고 데이터가 7개라면 적재율은 다음과 같다.
7 / 10 = 0.7테이블에 빈칸이 많으면 충돌이 발생하더라도 가까운 곳에서 빈칸을 찾을 수 있다.
반대로 테이블이 거의 가득 차면 빈칸을 찾기 위해 여러 칸을 이동해야 한다. 이 상태에서는 평균 O(1)이라는 장점을 유지하기 어렵다.
실제 해시 자료구조는 적재율이 특정 기준을 넘으면 더 큰 배열을 생성한 뒤 기존 데이터를 다시 저장한다. 이를 리사이징 또는 재해싱이라고 한다.
기존 테이블 생성
→ 적재율 증가
→ 더 큰 테이블 생성
→ 모든 데이터의 인덱스 재계산
→ 새 위치에 다시 저장리사이징 한 번에는 많은 작업이 필요하지만, 매번 발생하는 작업은 아니므로 전체 연산을 평균 내면 삽입은 일반적으로 상각 O(1)로 설명한다.
13. 좋은 해시 함수의 조건
좋은 해시 함수는 다음 조건을 만족해야 한다.
같은 입력에는 같은 결과를 반환해야 한다
hash("Kim") → 123
hash("Kim") → 123저장할 때와 찾을 때 결과가 달라지면 같은 위치로 이동할 수 없다.
서로 다른 데이터를 고르게 분산해야 한다
hash("Kim") → 1
hash("Lee") → 5
hash("Park") → 3모든 데이터가 같은 인덱스로 몰리지 않아야 한다.
계산 속도가 빨라야 한다
해시값을 계산하는 작업 자체가 지나치게 오래 걸리면 빠른 탐색이라는 장점이 사라진다.
데이터의 일부만 지나치게 의존하지 않아야 한다
예를 들어 문자열의 첫 글자만 사용하면 같은 글자로 시작하는 데이터가 한곳에 몰릴 수 있다.
Kim
Kang
Kwon학습용 구현에서는 문자 코드의 합처럼 단순한 함수를 사용할 수 있다. 하지만 실제 프로그램에서는 데이터 분산을 고려한 검증된 해시 함수나 언어의 표준 라이브러리를 사용하는 것이 안전하다.
14. 언제 무엇을 선택해야 할까?
데이터의 존재 여부만 필요하다면 HashSet을 선택한다.
이미 방문한 페이지인가?
이미 처리한 사용자 번호인가?
중복된 단어인가?키를 이용해 연결된 값을 찾아야 한다면 HashMap을 선택한다.
사용자 번호에 해당하는 이름은 무엇인가?
상품 코드에 해당하는 가격은 얼마인가?
단어가 몇 번 등장했는가?데이터의 순서를 유지해야 한다면 일반적인 HashSet이나 HashMap만으로는 부족할 수 있다. 사용하는 언어에서 순서를 보장하는 별도의 자료구조를 확인해야 한다.
데이터가 매우 적거나 단순히 한 번만 탐색한다면 배열이나 리스트가 더 간단할 수 있다. HashSet과 HashMap은 빠른 탐색이 반복적으로 필요한 상황에서 특히 유용하다.
마무리
HashSet과 HashMap이 빠른 이유는 데이터를 무작정 처음부터 찾지 않기 때문이다.
해시 함수를 사용해 데이터가 저장될 위치를 계산하고, 해당 위치로 바로 이동한다.
전체 동작은 다음과 같이 정리할 수 있다.
Key 입력
→ 해시 함수 실행
→ 해시값 생성
→ 나머지 연산으로 인덱스 계산
→ 해당 인덱스 확인
→ 충돌하면 다음 위치 탐색HashSet과 HashMap의 차이는 저장하는 데이터의 형태에 있다.
HashSet = 데이터의 존재 여부를 저장한다.
HashMap = Key와 연결된 Value를 저장한다.해시 함수가 데이터를 고르게 분산한다면 삽입, 탐색, 삭제는 평균 O(1)에 동작한다. 하지만 충돌이 많거나 테이블이 지나치게 가득 차면 최악의 경우 O(N)까지 느려질 수 있다.
따라서 해시 자료구조의 핵심은 단순히 해시값을 계산하는 것이 아니다.
좋은 해시 함수, 적절한 테이블 크기, 충돌 처리 방법을 함께 설계해야 빠른 탐색 성능을 얻을 수 있다.
'C언어 > 개념·이론' 카테고리의 다른 글
| 배열의 한계를 넘는 연결 리스트: 노드, 포인터, 삽입과 삭제 원리 (0) | 2026.07.24 |
|---|---|
| 재귀함수와 반복문의 시간복잡도, 그리고 출력 순서가 뒤집히는 이유 (0) | 2026.07.21 |