TIL - Hash, Hash Table, Hash Function, unordered_map

목록 보기

82/83

TIL

1. Hash

Hash는 어떤 데이터를 빠르게 찾거나 구분하기 위해, 그 데이터를 일정한 규칙으로 숫자 같은 값에 대응시키는 방식이다.

예를 들어 우리가 "철수"라는 문자열을 가지고 있다고 하자. 컴퓨터가 이 문자열을 이용해 데이터를 찾을 때 매번 모든 문자열을 하나씩 비교하면 느릴 수 있다. 그래서 "철수"라는 데이터를 어떤 계산 규칙에 넣어서 고유 숫자를 얻는다.

여기서 이 계산을 하는 규칙이 해시 함수(Hash Function)이고, 계산 결과로 나온 고유 숫자값이 해시 값(HashValue)이다.

원본 데이터 -> 해시함수 -> 해시 값

이런 관계를 유지한다. 따라서 "해시 = 해시값"은 아니다.
해시는 이런 변환과 활용 방식 전체를 가리키는 개념이고, 해시 함수와 해시 값은 그 안에 있는 구성 요소이다.

1-1. Hash의 필요성

왜 굳이 문자열을 숫자로 바꿀까? 문자 그 자체로 찾으면 결국 고유한 문자가 아닐까?

예를 들어 선수 이름이 100만 개 있고 "철수"를 찾는다고 하자 단순한 배열이라면 앞에서부터 비교할 수 있다.

"영희" -> 아님
"에덴" -> 아님
"범수" -> 아님
...
"철수" -> 찾음

최악의 경우 100만 개를 거의 다 일대일대응으로 확인해야 한다. 반면 철수를 어떤 숫자로 변환해서 그 숫자를 이용해 저장할 위치를 정해둔다면, 처음부터 전부 하나하나 찾을 필요가 없다.

"철수" -> 해시 함수 -> 583921 -> 저장할 위치 결정

나중에 철수를 다시 찾을 때도 똑같은 해시 함수를 사용한다.

"철수" -> 같은 해시 함수 -> 583921 -> 전에 정해둔 위치로 바로 이동

1-2. Hash Table과 unordered_map

이 아이디어를 실제 자료구조로 만든 것이 해시 테이블(Hash Table)이다.

Hash Table은 Key를 받아서 Hash Function을 적용하고, 그 결과를 이용해서 Key-Value 데이터를 저장할 위치를 결정한다.
예를 들어:

Key        Value

"mislav" → 2
"stanko" → 1
"ana"    → 1

// 여기서 mislav를 찾을 때

"mislav"
    ↓
해시 함수
    ↓
해시 값
    ↓
저장 위치 계산
    ↓
"mislav" → 2

이런 흐름이 생긴다. C++의 unordered_map이 바로 이 해시 테이블 계열의 컨테이너 이다.

unordered_map<string, int> Players;

여기서 string = Key, int = Value 이다. 그래서 Players["mislav"]라고 하면 unordered_map은 내부적으로 "mislav"를 그냥 배열 처음부터 찾아다니는 게 아니라, "mislav"를 해싱해서 저장 위치를 찾는다.

1-3. Hash와 Bucket

여기서 문제가 하나 생긴다. 해시 값은 굉장히 큰 숫자가 나올 수 있는데, 실제 메모리에 그런 개수의 칸을 만들어둘 수 는 없다. 그래서 Hash Table은 실제 데이터를 담을 버킷(Bucket)이라는 여러 칸을 만들어놓고, 해시 값을 이용해서 어느 버킷으로 갈지 결정한다.

예를 들어 버킷이 10개 있다고 가정하면:

hash("mislav") = 583921

583921을 이용해
0~9 중 하나의 bucket 결정

→ bucket 1

이런 과정이 생긴다.

1-4. Hash Collision

그런데 서로 다른 데이터가 같은 버킷으로 갈 수도 있다. 예를 들어:

"mislav" → bucket 3
"stanko" → bucket 3

이걸 해시 충돌(Hash Collision)이라고 한다. 여기서 중요한 점은 Hash Function이 서로 다른 데이터를 항상 서로 다른 위치로 보내주는 것은 아니다. Hash Table은 이런 충돌이 발생해도 두 Key를 구별해서 저장할 수 있는 추가 구조를 가지고 있다.

그래서 unordered_map의 탐색이 평균적으로 O(1)이라고 하지, 무조건 O(1)이라고 하지는 않는다. 충돌이 많아지면 한 버킷 안에서 추가 탐색이 필요해질 수 있기 때문이다.

1-5. 알고리즘 문제에서의 Hash

unordered_map<string, int> map;

for (const string& name : participant)
{
    map[name]++;
}

unordered_map을 이런 식으로 사용이 가능하다. 여기서 중요한 건 단순히 map[name]++라는 문법이 아니라 이름이 나오면 unordered_map이 해싱하여 해당 key가 저장된 위치를 찾고 그곳의 int 값에 접근 해 ++1을 했다는 것이다.

만약 동명이인이 한 명 더 나오면 똑같은 Key를 찾아 +1을 한다.