이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.
혹시나 모르는 부분이 있으면 댓글로 질문해주세요.
긴 글을 읽기 싫어하는 분들을 위해 한 줄 요약합니다. 이것만 읽어도 실전에 어느 정도 유용합니다.
한 줄 요약 : Hash는 key 데이터를 저장하는 공간이며 이걸로 Hash Table을 만들 수 있고, Hash Table은 2가지 종류가 있는데 하나는 key만 저장되어 있는 자료 구조를 set이라고 부르며, 또 하나는 key:value 형식으로 저장되어 있는 자료 구조를 map이라고 부르며 각 key는 중복을 허용하지 않는 유일성을 가집니다.
해싱은 컴퓨터 공학(CS) 분야에서 다음과 같이 정의되어 있습니다.
"임의의 길이를 데이터를 고정된 길이의 데이터로 변환하는 해시(hash)를 매개변수로 하는 함수를 활용하여 통상적인 반복을 하지 아니 하고 특정 계산만으로 데이터를 찾아내는 탐색 방법"
뭔 말인지 이해를 못 한다면 그게 정상입니다.
해시를 비전공자 기준으로 설명하면 "데이터 잘 쑤셔넣기"입니다.
예를 들어 어떤 정수를 나머지 8 연산을 해서 크기가 8인 리스트에 쑤셔넣는 것이라고 보면 됩니다.
얼탱이가 없어 보이지만 이게 해시(hash)의 기초입니다.
예를 들어 10000라는 정수형 데이터가 존재합니다.
그러면 "임의의 길이를 가진 데이터이니 이것을 어떻게 고정된 길이의 데이터로 변환할 수 있을까"로 생각하면 머리가 아프니
"그냥 고정된 크기를 8로 정해서 8 나누고 난 뒤의 나머지를 hash로 설정해!"입니다.
즉, 해시 함수를 h(x) = x mod 8로 한다면 h(10000) = 0이며 이것이 바로 데이터 10000의 해시(hash)입니다.
여기서 데이터 10000은 해시 테이블(hash table)에서 key라고 부르게 되며 그 key에 값을 따로 1대1로 추가한다면 그게 바로 value가 되어 key:value 형식으로 저장하게 됩니다.(예시로 key를 10000, value를 "세종대왕"으로 지정하여 key:value 형식으로 저장할 수 있습니다.)
또한 해시들의 모음을 "hashes"라고 부릅니다.
그러면 정수 데이터들을 hashes로 변환해볼까요?
해시 함수 h(x) = x mod 8이라고 가정합니다.
예시를 Python 소스 코드로 구현하겠습니다.
import sys
input = sys.stdin.readline
def get_hashes(data:list, size:int) :
hashes:list = [None for _ in range(size)]
for item in data :
hashes[item % size] = item
return hashes
L:list = [1972, 1121]
result:list = get_hashes(L, 8)
print(*result)[결과]
None 1121 None None 1972 None None None
1972 % 8 = 4이므로 1972라는 key가 hash 4에 대입되고
1121 % 8 = 1이므로 1121라는 key가 hash 1에 대입됩니다.
그 뒤 "key 1972를 찾고 싶어!"라고 하면 h(x) = 1972 % 8 = 4로 해서 hash 4 부분에 있는 데이터를 읽으면 O(1) 속도로 읽을 수 있습니다.
여기에 value를 추가해서 (key, value)로 저장할 수도 있습니다.
import sys
input = sys.stdin.readline
def get_hashes(data:list, size:int) :
hashes:list = [None for _ in range(size)]
for key, value in data :
hashes[key % size] = (key, value)
return hashes
L:list = [(1972, "kim"), (1121, "orange")]
result:list = get_hashes(L, 8)
print(*result)[결과]
None (1121, 'orange') None None (1972, 'kim') None None None
hash 4에 (1972, 'kim')가 저장되고 hash 1에 (1121, 'orange')가 저장됩니다.
이렇게 하여 "key 1972에 저장된 값(value)을 알고 싶어!"라고 하면 h(x) = 1972 % 8 = 4로 해서 hash 4에 있는 데이터를 추출합니다.
그 다음에 (key, value)에서 저장된 값 "kim"을 읽어냅니다.
그러면 이렇게 데이터들을 hashes로 변환하면 인덱싱 하기 편해서 O(1) 시간 복잡도로 탐색하니 만사 okay일까요?
다음 예시를 확인합니다.
import sys
input = sys.stdin.readline
def get_hashes(data:list, size:int) :
hashes:list = [None for _ in range(size)]
for key, value in data :
hashes[key % size] = (key, value)
return hashes
L:list = [(19, "kim"), (72, "orange"), (11, "SIM"), (21, "young")]
result:list = get_hashes(L, 8)
print(*result)[결과]
(72, 'orange') None None (11, 'SIM') None (21, 'young') None None
(19, 'kim') 데이터가 사라졌습니다.
어디로 사라진 것일까요?
진행 과정을 표시하기 위해 소스 코드를 수정합니다.
import sys
input = sys.stdin.readline
def get_hashes(data:list, size:int) :
hashes:list = [None for _ in range(size)]
for key, value in data :
hashes[key % size] = (key, value)
print(hashes) # 여기서 중간 과정을 확인할 수 있습니다.
return hashes
L:list = [(19, "kim"), (72, "orange"), (11, "SIM"), (21, "young")]
result:list = get_hashes(L, 8)
print(f"최종 결과 : {result}")[결과]
[None, None, None, (19, 'kim'), None, None, None, None]
[(72, 'orange'), None, None, (19, 'kim'), None, None, None, None]
[(72, 'orange'), None, None, (11, 'SIM'), None, None, None, None]
[(72, 'orange'), None, None, (11, 'SIM'), None, (21, 'young'), None, None]
최종 결과 : [(72, 'orange'), None, None, (11, 'SIM'), None, (21, 'young'), None, None]
(11, 'SIM') 데이터를 hash로 변환하는 과정에서 h(19) = 3이고 h(11)도 3이라서 서로 같은 hash를 가지는 문제가 발생합니다.
이로 인해 서로 충돌하게 되어 기존 key는 삭제되고 새로운 key가 덮어씌워지게 됩니다.
그래서 (19, 'kim') 데이터가 소실되는 문제가 발생합니다.
이 문제를 해결할려면 어떻게 해야 할까요?
1. 그냥 쓰자
정말 문자 그대로 쓰는 방법입니다.
오래된 데이터를 무시하고 새로운 데이터를 덮어씌워도 되는 환경에서 쓰이는 방법입니다.
하지만 모든 데이터를 저장하면서 거의 O(1)의 시간 복잡도로 탐색하고 싶다면 이 방법은 사용하지 않는 것이 좋습니다.
2. hashes의 크기를 늘리자
모든 데이터를 100% 확률로 저장하는 것은 아니나 hashes의 크기를 늘려서 충돌 가능성을 낮춥니다.
위의 소스 코드에서 hashes의 크기를 8 -> 16으로 늘리면 어떻게 될까요?
import sys
input = sys.stdin.readline
def get_hashes(data:list, size:int) :
hashes:list = [None for _ in range(size)]
for key, value in data :
hashes[key % size] = (key, value)
return hashes
L:list = [(19, "kim"), (72, "orange"), (11, "SIM"), (21, "young")]
result:list = get_hashes(L, 16) # hashes의 크기를 8 -> 16으로 늘립니다.
print(*result)[결과]
None None None (19, 'kim') None (21, 'young') None None (72, 'orange') None None (11, 'SIM') None None None None
해시 함수 h(x)가 x mod 8이 아닌 x mod 16으로 변경됩니다.
그러면 h(19) = 3, h(11) = 11로 변경되고 서로 충돌하지 않게 되어 데이터 소실을 막을 가능성이 높아지게 됩니다.
3. 각 hash마다 set()을 추가하자
import sys
input = sys.stdin.readline
def get_hashes(data:list, size:int) :
hashes:list = [set() for _ in range(size)] # None에서 set()으로 변경합니다.
for key, value in data :
hashes[key % size].add((key, value))
return hashes
L:list = [(19, "kim"), (72, "orange"), (11, "SIM"), (21, "young")]
result:list = get_hashes(L, 8)
print(*result)이번에는 None 대신 set()으로 변경합니다.
그러면 어떻게 변경될까요?
[결과]
{(72, 'orange')} set() set() {(19, 'kim'), (11, 'SIM')} set() {(21, 'young')} set() set()
hash 3에서 두 데이터가 서로 같은 hash라도 엄연히 다른 데이터이므로 set 안에 둘 다 저장되어 있는 것을 확인할 수 있습니다.
나중에 key 19의 value를 읽고 싶다면 1차적으로 해시 함수를 적용하여 hash를 찾아내고 그 다음 해당 hash의 set에서 key 19에 해당하는 값 "kim"을 읽을 수 있습니다.
놀랍게도 해시 함수과 set은 둘 다 O(1) 시간 복잡도로 탐색이 되므로 모든 데이터를 다 저장하면서 O(1)의 시간 복잡도로 값을 읽을 수 있게 됩니다.
마지막으로 위 3가지 방식 중에서 3번째 방식이 Hash Table(체이닝 방식)과 거의 유사합니다.
Hash Table은 ArrayList + LinkedList로 이루어져 있으며 ArrayList에 hash들을 저장하고, 각 hash마다 LinkedList로 데이터들을 마치 체인을 거는 것처럼 데이터들을 추가하는 것입니다.
그러나 LinkedList는 탐색 과정에서 O(N) 시간 복잡도를 가지는 단점을 가지므로 여기에 레드 블랙 트리(매우 어려운 자료구조입니다)를 사용하여 탐색 과정을 O(log N)으로 최적화 하는 방법이 있습니다.
혹은 위 3가지 방식 중에서 2번째 방식처럼 그냥 하나의 ArrayList 안에 hash들을 다 때려 넣어서 충돌이 일어나면 hash를 무작정 바꾸면서 빈 방을 찾을 때까지 탐색합니다.
만약 빈 방을 찾으면 거기에 때려넣는 방식으로 hash를 저장합니다.
이 경우는 무조건 O(1) 시간 복잡도를 가지고 어느 정도 공간이 차지되면 ArrayList의 크기를 무작정 늘립니다.(대신 메모리 최적화는 좀 포기해야 합니다.)
여기서 HashMap(Python에서는 사전 dict)은 key:value 형식으로 저장된 자료 구조이고 HashSet(Python에서는 집합 set)은 key만 저장되는 자료 구조로 보시면 됩니다.
단, 모든 key는 중복 허용하지 않는 유일성을 가지고 있습니다.
'초간단 알고리즘 설명' 카테고리의 다른 글
| [알고리즘 설명][Python] 다이나믹 프로그래밍(dp, dynamic programming) (0) | 2026.06.17 |
|---|---|
| [알고리즘 설명][Python] 유클리드 호제법(euclidean algorithm) (0) | 2026.06.15 |
| [알고리즘 설명][Python] 브루트 포스 알고리즘(brute force) (0) | 2026.06.12 |
| [알고리즘 설명][Python] 소수 판정(prime test) (0) | 2026.06.11 |
| [알고리즘 설명][Python] 피타고라스 정리(pythagoras' theorem) (0) | 2026.06.10 |