해시(hash)란 무엇인가?
해시는 키(key)를 받아서 고정된 크기의 숫자(또는 인덱스)로 바꿔주는 함수(또는 과정)예요. 또는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 쉽게 말하면, 어떤 물건(키)을 우체통(인덱스) 번호로 바로 연결해 주는 주소 계산기 같아요.
해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.
!!! 파이썬의 딕셔너리?
키로 데이터를 저장하고 찾을 수 있는 방법이었죠!
딕셔너리를 해쉬 테이블이라고 부르기도 합니다.
딕셔너리, 해쉬 테이블! 같다고 보시면 됩니다.
두 가지 중요한 맥락
- 데이터 구조(해시 테이블, Hash Table)에서의 해시: 빠른 검색/삽입을 위해 키를 배열의 인덱스로 바꾸는 데 사용.
- 암호학적 해시(Cryptographic hash): 보안·무결성 확인을 위해 파일/비밀번호 등을 고정 길이의 '요약값'으로 바꾸는 함수(예: SHA-256).
- 둘은 목적과 속성이 다르지만 기본 아이디어(임의 길이 입력 → 고정 길이 출력)는 같아요.
해쉬 함수(Hash Function)
임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수이다
-
해쉬 테이블(Hash Table)은 "키" 와 "데이터"를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조입니다.
-
해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수입니다.
-
해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장합니다.
-
그렇기 때문에 즉각적으로 데이터를 찾고, 추가할 수 있는 것 입니다.
-
만약, 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어난다면?
-
체이닝과 개방 주소법 방법으로 해결할 수 있습니다!
해시 함수의 성질 (데이터 구조 관점)
- 결정적(Deterministic): 같은 입력은 항상 같은 출력.
- 빠름: 짧은 시간 안에 계산 가능해야 함.
- 균등 분포(Uniform): 가능한 인덱스에 골고루 분포시키면 충돌이 적음.
- 출력 범위가 한정: 보통 테이블 크기 M에 맞춰 hash(key) % M로 인덱스 결정.
충돌(Collision) — 피할 수 없는 문제
-
서로 다른 두 키가 같은 인덱스로 나오는 상황. 예: hash("cat") % 10 == hash("tac") % 10
-
충돌 해결법:
Separate chaining (체이닝): 각 인덱스에 리스트를 두어 충돌된 항목들을 그 리스트에 저장.
Open addressing (개방주소법): 빈 슬롯을 찾아 다른 인덱스에 저장(예: 선형 탐사 linear probing, 제곱 탐사 quadratic probing, double hashing). -
로드 팩터(α = n / M): 원소 수 n 대비 테이블 크기 M. 보통 α가 커지면 성능 저하 → 리사이징(크기 증가)로 해결.
시간 복잡도
- 평균적으로 검색/삽입/삭제 모두 O(1) (상수 시간).
- 하지만 최악의 경우(모두 같은 슬롯에 몰릴 때)는 O(n). => 좋은 해시 함수, 적절한 테이블 크기/리사이징이 중요.
간단한 숫자 예제
간단한 해시 함수: 각 문자 ASCII 코드 합을 10으로 나눈 나머지 (sum(ord(c) for c in s) % 10)
-
"cat": c(99)+a(97)+t(116)=312 → 312 % 10 = 2
-
"tac": t(116)+a(97)+c(99)=312 → 312 % 10 = 2 → 충돌 발생
-
"dog": d(100)+o(111)+g(103)=314 → 314 % 10 = 4
이 예제에서 "cat"과 "tac"가 같은 인덱스(2)로 가므로 충돌 해결이 필요해요.
간단한 파이썬 코드 예시 (체이닝 방식 해시 테이블)
class SimpleHashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)] # 각 슬롯에 리스트(체인)
def _hash(self, key):
# 아주 단순한 해시: 문자열의 문자값 합을 size로 나눈 나머지
return sum(ord(c) for c in key) % self.size
def insert(self, key, value):
idx = self._hash(key)
# 같은 키가 있으면 갱신, 없으면 추가
for i, (k, v) in enumerate(self.table[idx]):
if k == key:
self.table[idx][i] = (key, value)
return
self.table[idx].append((key, value))
def get(self, key):
idx = self._hash(key)
for k, v in self.table[idx]:
if k == key:
return v
return None
def remove(self, key):
idx = self._hash(key)
self.table[idx] = [(k,v) for (k,v) in self.table[idx] if k != key]
_ hash가 인덱스를 만들고, table[idx]가 그 인덱스의 체인(list)을 나타내요.
- 실무에선 Python의 dict처럼 이미 잘 최적화된 구현을 사용합니다.
암호학적 해시(간단 비교)
-
목적: 보안(변조 감지, 비밀번호 검증 등).
-
특징:
- 출력 길이가 고정(예: SHA-256은 256비트).
- 역산 불가능성(Pre-image resistance): 해시값만 보고 원래 입력을 찾기 어렵다.
- 충돌 저항성(Collision resistance): 서로 다른 입력이 같은 해시를 만드는 건 매우 어려워야 함.
- Avalanche 효과: 입력을 조금만 바꿔도 해시 전체가 크게 바뀜. -
주의: 단순 해시만으로 비밀번호 저장하면 안 돼요 — 반드시 salt를 붙이고 bcrypt/argon2 같은 느린(비용이 큰) 해시 함수를 사용.
실제 사용처 (예시)
- 프로그래밍 언어의 HashMap/dict/unordered_map (빠른 키-값 저장).
- 집합(set) 구현 — 중복 제거.
- 파일 무결성 확인(예: SHA-256 checksum).
- 비밀번호 저장(올바른 방식: salt + 적절한 해시 알고리즘).
- 캐시 키, 데이터베이스 인덱싱, 분산 시스템의 consistent hashing(고급 주제).
주의할 점 (핵심 포인트)
- 해시 ≠ 암호화: 해시는 복원 불가능한 요약, 암호화는 복호화 가능.
- 충돌은 항상 일어날 수 있다: 완벽히 피할 수 없다 → 충돌 처리 설계를 해야 함.
- 비밀번호 저장시 주의: 절대 단순 SHA256만 쓰지 말고 salt + bcrypt/argon2 사용.
- 테이블 크기와 로드 팩터 관리: 너무 작으면 충돌 많아지고 성능 저하.
- 언어 내장 자료구조 사용 권장: 직접 구현하는 건 학습용으로 좋지만, 실무에선 검증된 라이브러리 사용이 안전.
정리(요약)
- 해시는 키 → 정수 인덱스로 바꾸는 함수.
- 해시 테이블은 평균적으로 O(1)로 빠르게 작동하지만 충돌·리사이징 관리를 해야 함.
- 암호학적 해시는 보안·무결성용이며 별도의 성질(역산 불가능 등)을 가짐.
