자료구조와 알고리즘

해시

begin-play 2026. 8. 31. 21:28

해시(Hash)

1. Hash란?

이번에는 Hash(해시)에 대해 학습했다.

해시는 데이터를 빠르게 저장하고 찾기 위한 방법이며, 특히 특정 데이터를 빠르게 탐색하는 상황에서 실전 활용도가 높은 자료구조이다.

해시(Hash)는 쉽게 말하면 어떤 데이터를 일정한 규칙을 통해 다른 값으로 변환하는 것이다.

예를 들어 문자열 "Apple"이라는 데이터를 어떤 계산을 통해 1234라는 숫자로 변환할 수 있다.

"Apple" → 1234

이처럼 데이터를 다른 값으로 변환하는 과정을 해싱(Hashing)이라고 한다.

해싱의 목적은 단순히 데이터를 다른 값으로 바꾸는 것이 아니라, 변환된 값을 이용해서 데이터를 빠르게 저장하고 찾는 것이다.

2. Hash Function

해시를 만들기 위해서는 Hash Function(해시 함수)이 필요하다.

해시 함수는 데이터를 입력받아서 Hash Value(해시 값)를 만들어내는 함수이다.

입력 데이터
    ↓
Hash Function
    ↓
Hash Value

예를 들어 다음과 같은 방식으로 동작할 수 있다.

"Apple"
   ↓
Hash Function
   ↓
1234

다른 데이터는 다른 해시 값으로 변환될 수 있다.

"Banana"
   ↓
Hash Function
   ↓
5678

좋은 해시 함수는 입력 데이터를 가능한 한 고르게 분산시키는 것이 중요하다.

예를 들어 해시 테이블의 크기가 10이라면 다음과 같이 여러 위치에 데이터가 골고루 분산되는 것이 좋다.

Apple  → 2
Banana → 7
Cat    → 4
Dog    → 9

반대로 다음처럼 특정 위치에 데이터가 몰리게 되면 좋지 않다.

Apple  → 2
Banana → 2
Cat    → 2
Dog    → 2

이렇게 되면 Collision(충돌)이 많이 발생하기 때문이다.

3. Hash Table

Hash Table(해시 테이블)은 해시를 이용해서 데이터를 저장하고 탐색하는 자료구조이다.

기본적인 동작 과정은 다음과 같다.

데이터
 ↓
Hash Function
 ↓
Hash Value
 ↓
Index
 ↓
Hash Table에 저장

예를 들어 "Apple"이라는 문자열을 해시 함수에 넣었더니 1234라는 값이 나왔다고 가정한다.

해시 테이블의 크기가 10이라면 다음과 같이 사용할 수 있다.

1234 % 10 = 4

그러면 4번 위치에 "Apple"을 저장할 수 있다.

Index

0
1
2
3
4 → Apple
5
6
7
8
9

나중에 "Apple"을 찾을 때도 같은 과정을 거친다.

"Apple"
   ↓
Hash Function
   ↓
1234
   ↓
1234 % 10
   ↓
4

따라서 4번 위치로 바로 접근해서 데이터를 찾을 수 있다.

이것이 해시 테이블이 빠른 이유이다.

4. Hash Table이 빠른 이유

일반적인 배열에서 특정 값을 찾는다고 가정한다.

[10, 25, 33, 41, 57, 62, 78]

57을 찾기 위해 처음부터 하나씩 확인한다면 다음과 같은 과정이 필요하다.

10 → X
25 → X
33 → X
41 → X
57 → 발견

이러한 방식은 선형 탐색이며 시간 복잡도는 O(N)이다.

하지만 해시 테이블에서는 데이터 자체를 이용해서 저장 위치를 계산할 수 있다.

57
 ↓
Hash Function
 ↓
Index 3

따라서 필요한 위치를 바로 계산해서 접근할 수 있다.

그래서 해시 테이블의 삽입, 탐색, 삭제는 평균적으로 O(1)의 시간 복잡도를 가진다.

일반적인 선형 탐색

데이터
 ↓
처음부터 하나씩 확인
 ↓
O(N)

반면 해시 테이블은 다음과 같다.

Hash Table

데이터
 ↓
Hash Function
 ↓
위치 계산
 ↓
바로 접근
 ↓
평균 O(1)

5. 해시 테이블이 항상 O(1)은 아니다

해시 테이블의 탐색이 O(1)이라고 할 때는 정확하게는 평균적인 경우를 의미한다.

항상 O(1)인 것은 아니다.

가장 중요한 이유가 바로 Collision(충돌)이다.

6. Collision

Collision(충돌)은 서로 다른 데이터가 같은 해시 테이블의 위치를 사용하게 되는 상황이다.

예를 들어 다음과 같은 결과가 나왔다고 가정한다.

Apple  → 4
Banana → 7
Cat    → 4

Apple과 Cat이 모두 4번 위치를 사용하려고 한다.

4 → Apple
4 → Cat

이것이 Collision이다.

해시 함수가 아무리 좋아도 Collision을 완전히 없애기는 어렵다.

데이터의 종류는 매우 많을 수 있지만 해시 테이블의 저장 공간에는 한계가 있기 때문이다.

따라서 해시 테이블에서는 Collision이 발생했을 때 어떻게 처리할 것인지가 중요하다.

대표적인 방법으로 다음 두 가지가 있다.

1. Chaining
2. Open Addressing

7. Chaining

Chaining은 충돌이 발생했을 때 같은 위치에 여러 데이터를 연결해서 저장하는 방법이다.

예를 들어 다음과 같은 상황을 생각할 수 있다.

Apple → 4
Cat   → 4

두 데이터가 모두 4번 위치를 사용하게 된다.

Chaining에서는 이를 연결해서 관리한다.

0
1
2
3
4 → Apple → Cat
5
6
7

한 위치에 여러 데이터를 저장할 수 있도록 별도의 연결 구조를 사용하는 방식이다.

예를 들어 4번 위치에 데이터가 다음과 같이 연결되어 있을 수 있다.

4 → Apple → Cat → Dog

Cat을 찾는 경우에는 먼저 Cat의 해시 값을 계산해서 4번 위치를 찾는다.

Cat
 ↓
Hash Function
 ↓
4

그다음 4번 위치에 연결되어 있는 데이터를 확인한다.

4 → Apple → Cat → Dog

8. Chaining의 장점과 단점

Chaining의 장점은 충돌이 발생했을 때 같은 위치에 데이터를 연결하면 되기 때문에 개념적으로 비교적 직관적이라는 점이다.

같은 위치에 들어오면
        ↓
연결해서 저장

또한 하나의 위치에 여러 데이터를 저장할 수 있기 때문에 해시 테이블의 공간을 비교적 유연하게 사용할 수 있다.

하지만 특정 위치에 데이터가 지나치게 많이 몰리면 문제가 발생한다.

4 → A → B → C → D → E → F

이처럼 하나의 위치에 많은 데이터가 연결되면 데이터를 찾기 위해 연결된 데이터를 여러 개 확인해야 한다.

극단적으로 모든 데이터가 하나의 위치에 몰린다면 탐색 성능이 O(N)까지 떨어질 수 있다.

9. Open Addressing

Open Addressing은 충돌이 발생했을 때 다른 빈 공간을 찾아서 데이터를 저장하는 방식이다.

예를 들어 다음과 같은 상황이 있다고 가정한다.

Apple → 4

이미 4번 위치에 "Apple"이 저장되어 있는데 "Cat"도 4번 위치를 사용해야 한다면 충돌이 발생한다.

Cat → 4

4번 위치가 이미 사용 중이기 때문에 다른 위치를 찾는다.

4 → 사용 중
5 → 빈 공간

그러면 5번 위치에 "Cat"을 저장한다.

0
1
2
3
4 → Apple
5 → Cat
6
7
8
9

Chaining처럼 같은 위치에 연결하는 것이 아니라 해시 테이블 내부의 다른 빈 공간을 찾아서 저장하는 것이다.

10. Open Addressing의 대표적인 방법

빈 공간을 찾는 방법에도 여러 가지가 있다.

대표적으로 다음과 같은 방법이 있다.

Linear Probing
Quadratic Probing
Double Hashing

그중 가장 단순한 방법이 Linear Probing이다.

11. Linear Probing

Linear Probing은 충돌이 발생하면 다음 칸을 순서대로 확인하는 방식이다.

예를 들어 4번 위치에 저장하려고 했는데 이미 사용 중이라면 다음과 같이 확인한다.

4 → 사용 중
5 → 사용 중
6 → 빈 공간

따라서 6번에 데이터를 저장한다.

개념적으로는 다음과 같다.

index + 1
index + 2
index + 3
...

순서로 빈 공간을 찾는 것이다.

12. Chaining과 Open Addressing 비교

두 방식 모두 Collision을 해결하기 위한 방법이지만 동작 방식이 다르다.

구분ChainingOpen Addressing

충돌 처리	같은 위치에 연결	다른 빈 위치 탐색
저장 방식	별도의 연결 구조 활용	테이블 내부에 저장
구현 개념	비교적 직관적	탐사 방식 필요
빈 공간 활용	상대적으로 유연	테이블 공간이 중요
대표적인 방법	Linked List 등	Linear Probing 등

핵심적으로 기억할 내용은 다음과 같다.

Chaining
충돌
 ↓
같은 위치에 여러 데이터 연결

Open Addressing
충돌
 ↓
다른 빈 위치 탐색

13. Hash Table의 시간 복잡도

해시 테이블에서 중요한 연산은 다음과 같다.

삽입
탐색
삭제

평균적인 경우에는 다음과 같다.

연산평균최악

삽입	O(1)	O(N)
탐색	O(1)	O(N)
삭제	O(1)	O(N)

따라서 해시 테이블은 평균적으로 매우 빠른 탐색이 필요한 상황에서 강력한 자료구조이다.

14. C++의 std::unordered_map

C++에서는 해시 테이블을 직접 구현하지 않아도 해시 기반 자료구조를 사용할 수 있다.

대표적으로

std::unordered_map

이 있다.

예를 들어 다음과 같이 선언할 수 있다.

#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> Scores;

여기서는 std::string을 Key로 사용하고 int를 Value로 사용한다.

즉 다음과 같은 형태로 데이터를 저장할 수 있다.

Key       Value

Player1 → 100
Player2 → 200
Player3 → 150

15. unordered_map의 구조

다음과 같이 데이터를 저장할 수 있다.

Scores["Player1"] = 100;
Scores["Player2"] = 200;
Scores["Player3"] = 150;

개념적으로 보면 다음과 같다.

Player1 → 100
Player2 → 200
Player3 → 150

여기서 Key가 데이터의 식별자 역할을 한다.

예를 들어 게임에서 다음과 같은 구조를 만들 수 있다.

PlayerID → Score

Player001 → 100
Player002 → 250
Player003 → 180

특정 PlayerID를 이용해서 해당 플레이어의 점수를 빠르게 찾을 수 있다.

16. unordered_map의 주요 기능

삽입

Scores["Player1"] = 100;

Player1이라는 Key에 100이라는 Value를 저장한다.

조회

int Score = Scores["Player1"];

Player1이라는 Key를 이용해서 값을 가져온다.

존재 여부 확인

if (Scores.contains("Player1"))
{
    // 존재함
}

contains()를 이용해서 해당 Key가 존재하는지 확인할 수 있다.

삭제

Scores.erase("Player1");

erase()를 이용해서 Player1을 삭제한다.

17. std::unordered_set

std::unordered_set도 해시 테이블을 기반으로 하는 자료구조이다.

하지만 unordered_map처럼 Key와 Value를 따로 저장하지 않는다.

std::unordered_set<int> Numbers;

다음과 같이 값을 저장한다.

Numbers.insert(10);
Numbers.insert(20);
Numbers.insert(30);

개념적으로는 다음과 같다.

10
20
30

가장 중요한 특징은 중복된 값을 저장하지 않는다는 것이다.

예를 들어:

Numbers.insert(10);
Numbers.insert(10);
Numbers.insert(10);

을 실행해도 10은 하나만 존재한다.

18. unordered_set을 사용하는 상황

unordered_set은 특히

특정 값이 존재하는가?

를 빠르게 확인하고 싶을 때 유용하다.

예를 들어 플레이어가 획득한 아이템을 관리한다고 가정할 수 있다.

Sword
Shield
Potion

특정 아이템을 가지고 있는지 확인할 때 다음과 같이 사용할 수 있다.

if (Items.contains("Sword"))
{
    // Sword를 가지고 있음
}

이처럼 존재 여부를 빠르게 확인하는 용도로 사용할 수 있다.

19. unordered_map과 unordered_set의 차이

둘 다 Hash Table 기반이라는 공통점이 있다.

하지만 저장하는 데이터의 형태가 다르다.

unordered_map

Key → Value

예:

PlayerID → Score

unordered_set

Value

예:

ItemID

따라서 다음과 같이 정리할 수 있다.

unordered_map
→ Key와 Value를 연결해서 저장

unordered_set
→ 값 자체만 저장하며 중복을 허용하지 않음

20. Tree 기반 자료구조

이제 Hash 기반 자료구조와 비교하기 위해 Tree 기반 자료구조를 살펴봤다.

C++의 대표적인 Tree 기반 자료구조가 다음과 같다.

std::map
std::set

일반적으로 균형 이진 탐색 트리 계열을 기반으로 구현되며, 대표적으로 Red-Black Tree가 사용된다.

트리의 구조를 단순하게 표현하면 다음과 같다.

        50
       /  \
     30    70
    / \    / \
   20 40  60 80

이처럼 데이터가 정렬된 형태로 구성된다.

21. std::map

std::map은 Key → Value 형태로 데이터를 저장하는 자료구조이다.

예를 들어:

std::map<int, std::string> Players;

Players[1] = "Alice";
Players[2] = "Bob";
Players[3] = "Charlie";

다음과 같은 형태로 저장된다.

1 → Alice
2 → Bob
3 → Charlie

std::map의 중요한 특징은 Key가 정렬된 상태로 관리된다는 것이다.

22. std::set

std::set은 값을 하나씩 저장하면서 중복을 허용하지 않고 정렬된 상태로 관리하는 자료구조이다.

예를 들어:

std::set<int> Numbers;

Numbers.insert(30);
Numbers.insert(10);
Numbers.insert(20);

입력 순서는 다음과 같다.

30
10
20

하지만 Tree 기반으로 정렬된 상태를 유지하기 때문에 개념적으로 다음과 같이 관리된다.

10
20
30

23. map/set과 unordered_map/unordered_set 비교

이번 학습에서 가장 중요한 비교 중 하나이다.

자료구조내부 구조정렬평균 탐색

unordered_map	Hash Table	X	O(1)
unordered_set	Hash Table	X	O(1)
map	Tree	O	O(log N)
set	Tree	O	O(log N)

즉,

unordered_map
unordered_set

은 Hash Table 기반이고,

map
set

은 Tree 기반이다.

24. Tree가 O(log N)인 이유

Tree가 균형 있게 구성되어 있다고 가정한다.

          50
        /    \
      30      70
     /  \    /  \
   20   40  60   80

80을 찾는다고 하면 다음과 같은 과정을 거친다.

모든 데이터를 처음부터 확인하는 것이 아니라 트리의 높이를 따라 내려가면서 탐색하기 때문에 균형 잡힌 Tree에서는 O(log N)의 시간 복잡도를 가진다.

25. Hash Table과 Tree의 가장 큰 차이

Hash Table과 Tree 모두 데이터를 빠르게 찾을 수 있지만, 데이터를 찾는 방식 자체가 다르다.

Hash Table

Key
 ↓
Hash Function
 ↓
위치 계산
 ↓
접근

평균적인 탐색 시간 복잡도:

O(1)

Tree

Key
 ↓
Root
 ↓
작으면 왼쪽
크면 오른쪽
 ↓
반복

균형 잡힌 Tree의 탐색 시간 복잡도:

O(log N)

26. Tree 기반 자료구조의 장점

Hash Table과 달리 Tree 기반 자료구조는 데이터를 정렬된 상태로 유지할 수 있다는 장점이 있다.

Hash Table은 일반적으로 데이터가 정렬된 상태로 저장된다는 보장이 없다.

예를 들어:

std::unordered_set<int> Numbers;

에 다음과 같이 데이터를 넣었다고 하더라도:

결과가 반드시 다음처럼 정렬되어 나오는 것은 아니다.

반면:

std::set<int> Numbers;

는 정렬된 상태를 유지한다.

27. 범위 검색에서는 Tree가 유리하다

Tree 기반 자료구조가 가지는 중요한 장점 중 하나가 범위 검색이다.

예를 들어 다음과 같은 데이터를 가지고 있다고 가정한다.

여기서

40 이상 80 이하

인 데이터를 찾고 싶다면 정렬된 Tree 구조를 활용하기 좋다.

반면 Hash Table은 데이터가 정렬되어 있지 않기 때문에

100 ~ 200 사이의 데이터

처럼 범위에 해당하는 데이터를 찾는 작업에는 적합하지 않다.

Hash Table은 기본적으로 특정 Key를 빠르게 찾는 것에 강하다.

28. Hash와 Tree를 언제 사용하는가?

Hash를 사용하기 좋은 상황

특정 Key를 이용해서 데이터를 빠르게 찾고 싶을 때 적합하다.

예를 들어:

PlayerID → PlayerData
ItemID → ItemData
MonsterID → MonsterData

와 같은 구조이다.

C++에서는 다음과 같은 자료구조를 사용할 수 있다.

std::unordered_map

Tree를 사용하기 좋은 상황

데이터를 정렬된 상태로 유지해야 하거나 범위 검색이 필요한 경우 적합하다.

예를 들어:

점수 순으로 정렬
ID 범위 검색
최솟값 / 최댓값 탐색
순서 기반 탐색

등의 상황이다.

C++에서는 다음과 같은 자료구조를 사용할 수 있다.

std::map
std::set

29. 상황별 비교

상황 A

PlayerID가 1234인 플레이어를 찾아라.

이 경우 Hash Table이 적합하다.

1234
 ↓
Hash Function
 ↓
위치
 ↓
Player Data

특정 Key를 빠르게 찾아야 하기 때문이다.

상황 B

PlayerID가 1000~2000 사이인 플레이어를 찾아라.

이 경우에는 Tree 기반 자료구조가 유리하다.

Key가 정렬되어 있기 때문에 특정 범위에 해당하는 데이터를 찾기 쉽기 때문이다.

30. Hash의 단점

Hash가 항상 좋은 자료구조인 것은 아니다.

1. Collision

서로 다른 데이터가 같은 위치를 사용할 수 있다.

A → 3
B → 3

따라서 Collision을 처리하는 방법이 필요하다.

Chaining
Open Addressing

등을 사용한다.

2. 정렬되지 않는다

Hash Table은 일반적으로 데이터를 정렬된 상태로 유지하지 않는다.

3. 범위 검색에 불리하다

100 ~ 200

과 같은 범위 검색에는 적합하지 않다.

4. 최악의 경우 O(N)

충돌이 심하게 발생하면 탐색 성능이 O(N)까지 떨어질 수 있다.

31. Tree의 단점

Tree도 장점만 있는 것은 아니다.

Hash Table의 평균 탐색이 O(1)인 것에 비해 균형 잡힌 Tree는 O(log N)이다.

Hash → 평균 O(1)
Tree → O(log N)

따라서 단순하게 특정 값을 빠르게 찾는 것이 목적이라면 Hash Table이 더 유리한 경우가 많다.

하지만 Tree는 다음과 같은 기능에서 강점을 가진다.

정렬
범위 검색
최솟값 / 최댓값
순서 기반 탐색

32. 전체 구조 정리

이번에 학습한 내용을 하나의 흐름으로 연결하면 다음과 같다.

Hash
 │
 └─ 데이터를 특정 값으로 변환하는 개념
      │
      ↓
Hash Function
 │
 └─ 데이터를 Hash Value로 변환
      │
      ↓
Hash Table
 │
 ├─ 데이터를 빠르게 저장
 └─ 데이터를 빠르게 탐색
      │
      └─ Collision 발생 가능
            │
            ├─ Chaining
            │
            └─ Open Addressing

그리고 C++에서는 다음과 같이 연결된다.

Hash Table
 │
 ├─ unordered_map
 └─ unordered_set

Tree 기반 자료구조는 다음과 같다.

Tree
 │
 ├─ map
 └─ set

33. 최종 비교표

특징 unordered_map unordered_set map set

기반	Hash Table	Hash Table	Tree	Tree
Key-Value	O	X	O	X
중복 Key/값	X	X	X	X
정렬	X	X	O	O
평균 탐색	O(1)	O(1)	O(log N)	O(log N)
범위 검색	불리함	불리함	유리함	유리함
특정 값 빠른 검색	매우 유리	매우 유리	유리	유리

34. 이번 학습에서 기억해야 할 핵심

이번 단계에서는 단순히

unordered_map = O(1)
map = O(log N)

이라고 외우는 것보다 왜 그런 차이가 발생하는지 이해하는 것이 중요하다고 생각했다.

해시 테이블의 핵심 흐름은 다음과 같다.

데이터
 ↓
Hash Function
 ↓
Hash Value
 ↓
Hash Table의 위치
 ↓
저장 / 탐색

그리고 서로 다른 데이터가 같은 위치에 들어가려고 하면 Collision이 발생한다.

서로 다른 데이터
       ↓
같은 위치
       ↓
Collision
       ↓
Chaining / Open Addressing

C++에서는 다음과 같이 정리할 수 있다.

unordered_map
→ Hash Table + Key / Value

unordered_set
→ Hash Table + 값만 저장 + 중복 허용 X

map
→ Tree + Key / Value + 정렬

set
→ Tree + 값만 저장 + 정렬

가장 중요한 비교는 다음과 같다.

Hash Table
→ 평균 O(1)
→ 특정 값의 빠른 탐색에 강함
→ 정렬되지 않음
→ 범위 검색에 불리함

Tree
→ O(log N)
→ 정렬된 상태 유지
→ 범위 검색에 유리함
→ 순서 기반 탐색에 유리함

따라서 자료구조를 선택할 때는 단순히 "O(1)이니까 Hash가 더 좋다"라고 생각하는 것이 아니라, 내가 필요한 연산이 무엇인지에 따라 자료구조를 선택해야 한다는 것을 학습했다.

예를 들어 특정 ID를 이용해 데이터를 빠르게 찾는 것이 목적이라면 Hash, 데이터를 정렬된 상태로 유지하거나 범위 검색이 필요하다면 Tree를 사용하는 식으로 판단할 수 있다.

'자료구조와 알고리즘' 카테고리의 다른 글

힙(Heap) / 우선순위 큐(Priority Queue) (0)	2026.09.04
트리(Tree) (0)	2026.09.01
정렬 알고리즘 (0)	2026.08.28
탐색 알고리즘 (0)	2026.08.27
재귀 (0)	2026.08.26

현재글해시

begin-play 님의 블로그

begin-play 님의 블로그 입니다.

Today :
Yesterday :

« 2026/09 »
일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

해시

해시(Hash)

1. Hash란?

2. Hash Function

3. Hash Table

4. Hash Table이 빠른 이유

5. 해시 테이블이 항상 O(1)은 아니다

6. Collision

7. Chaining

8. Chaining의 장점과 단점

9. Open Addressing

10. Open Addressing의 대표적인 방법

11. Linear Probing

12. Chaining과 Open Addressing 비교

13. Hash Table의 시간 복잡도

14. C++의 std::unordered_map

15. unordered_map의 구조

16. unordered_map의 주요 기능

삽입

조회

존재 여부 확인

삭제

17. std::unordered_set

18. unordered_set을 사용하는 상황

19. unordered_map과 unordered_set의 차이

unordered_map

unordered_set

20. Tree 기반 자료구조

21. std::map

22. std::set

23. map/set과 unordered_map/unordered_set 비교

24. Tree가 O(log N)인 이유

25. Hash Table과 Tree의 가장 큰 차이

Hash Table

Tree

26. Tree 기반 자료구조의 장점

27. 범위 검색에서는 Tree가 유리하다

28. Hash와 Tree를 언제 사용하는가?

Hash를 사용하기 좋은 상황

Tree를 사용하기 좋은 상황

29. 상황별 비교

상황 A

상황 B

30. Hash의 단점

1. Collision

2. 정렬되지 않는다

3. 범위 검색에 불리하다

4. 최악의 경우 O(N)

31. Tree의 단점

32. 전체 구조 정리

33. 최종 비교표

34. 이번 학습에서 기억해야 할 핵심

'자료구조와 알고리즘' 카테고리의 다른 글

'자료구조와 알고리즘'의 다른글

관련글

티스토리툴바