Kotlin/코틀린 해시(Hash) 완벽 가이드 – 개념, 면접 포인트 정리
✨ 개요
해시(Hash)는 임의 길이의 입력 → 고정 길이의 값(해시값) 으로 매핑하는 기술입니다.
빠른 조회(해시테이블), 데이터 무결성(체크섬), 보안(비밀번호 해싱/디지털서명), 분산시스템(일관 해싱) 등 소프트웨어 전 영역에서 핵심이에요.
1. 요약
- 해시함수: 입력을 일정 길이로 압축하는 결정적 함수
- 좋은 해시: 분포가 균등, 작은 입력 변화에도 큰 해시 변화(어발랜치), 충돌(서로 다른 입력이 같은 해시) 최소
- 해시테이블:
O(1)기대 조회/삽입, 충돌 해결이 성능 핵심 - 암호학적 해시(SHA-2/3 등): 역상/2차역상/충돌 내성 요구
- 비밀번호는 빠른 해시 금지 → bcrypt/scrypt/Argon2 같은 느리고 메모리 집약적인 해시 사용
- 분산: 일관(Consistent) 해싱으로 노드 증감 시 재배치 최소화
2 해시의 정확한 정의
- 해시 함수 (H): 임의 길이 입력 (x) → 고정 길이 출력 (h = H(x))
- 특성
- 결정성: 같은 입력 → 항상 같은 출력
- 균등성: 가능한 출력 공간에 고르게 분포
- 어발랜치(Avalanche): 입력 1비트만 바뀌어도 출력이 무작위 수준으로 변함
- 효율성: 빠르게 계산 가능
충돌(Collision)은 원천적으로 존재(비둘기집 원리). 목표는 충돌을 드물고 예측 불가하게 만드는 것.
3 해시함수의 종류
- 일반(비암호학적) 해시: Murmur3, xxHash, FNV 등
- 목적: 속도/균등성 (해시테이블, 파일 파티셔닝)
- 암호학적 해시: SHA-256/512, SHA-3, BLAKE2/3
- 목적: 보안 성질(역상·2차역상·충돌내성) + 안정된 분포
- 메시지 인증/키드 해시: HMAC-SHA256 (키 기반 무결성)
- 비밀번호 해시: bcrypt, scrypt, Argon2(느리고 메모리 집약적)
4. 해시테이블 동작 원리 (핵심)
- 버킷 인덱싱:
index = H(key) mod capacity - 충돌 해결
- 체이닝(Chaining): 같은 인덱스에 연결리스트/트리로 쌓음 (Java 8+: 일정 길이 넘으면 트리화)
- 개방주소(Open Addressing): 빈 칸을 찾을 때까지 선형/제곱/이중 해싱으로 탐사
- 부하율(Load Factor):
size / capacity가 임계치(예: 0.75) 넘으면 리사이즈 + 리해시 - 시간복잡도
- 평균: 조회/삽입/삭제 O(1)
- 최악: O(n) (충돌 집중/적대 입력) → 좋은 해시 + 적절한 용량/부하율 관리가 필수
Java/Kotlin:
equals()가 같다면 반드시hashCode()도 같아야 함. 둘 중 하나만 오버라이드하면 HashMap/HashSet 오동작.
5. 암호학적 해시: 왜 중요한가?
- 역상 내성(Preimage): (h)만으로 (x) 찾기 어려움
- 2차 역상 내성(Second Preimage): 같은 해시가 되도록 다른 (x’) 찾기 어려움
- 충돌 내성(Collision): 임의의 (x \neq x’)로 (H(x)=H(x’)) 찾기 어려움
- 활용: 디지털 서명, 블록체인, 무결성 검증, 콘텐츠 주소화(CID)
6. 비밀번호 해싱 – 절대 SHA-256 단독 사용 금지
- 공격자는 GPU/ASIC으로 초고속 대입 가능 → 빠른 해시는 즉시 뚫림
- 권장:
bcrypt/scrypt/Argon2id(메모리·연산 비용 튜닝 가능) - Salt: 사용자별 무작위값으로 레인보우 테이블 무력화
- Pepper: 서버 별도 비밀키(애플리케이션 레벨)로 추가 방어
- 키 스트레칭: 반복/메모리 비용을 키워 속도를 의도적으로 느리게
7. 실무 체크리스트
- 해시테이블 키 타입은 불변성 확보 &
equals/hashCode계약 준수 - 충돌 해결 전략 + 부하율 관리(기본 0.75 전후)
- 입력 분포가 편향되면 도메인 특화 해시(예: SipHash) 검토(DoS 완화)
- 파일·전송 무결성: 빠른 체크섬(XXH3) → 중요 경로엔 SHA-256 등 신뢰 가능한 해시로 이중 확인
- 비밀번호: bcrypt/scrypt/Argon2 + Salt/Pepper + 비용 파라미터 주기적 상향
8. 면접 포인트 정리(Q → A)
Q1. 해시테이블 시간복잡도와 최악 상황은?
- A. 평균 O(1)/최악 O(n). 해시 충돌이 몰리거나 부하율이 너무 높을 때. 체이닝 vs 개방주소의 차이도 설명.
Q2. 좋은 해시함수의 조건?
- A. 결정성, 균등 분포, 낮은 충돌, 어발랜치 효과, 빠른 계산. 암호학적 용도면 역상·2차역상·충돌 내성 추가.
Q3. equals()와 hashCode()의 계약?
- A. a == b ⇒ a.hashCode() == b.hashCode(). 둘 다 동시에 재정의해야 HashMap/HashSet이 정상 동작.
Q4. 비밀번호에 SHA-256 같은 빠른 해시를 쓰면 안 되는 이유?
- A. GPU 병렬 대입이 너무 빠름. 대신 bcrypt/scrypt/Argon2처럼 느리고 메모리 의존적인 함수 사용 + Salt/Pepper.
Q5. 일관(Consistent) 해싱이 뭐고 왜 쓰나?
- A. 노드/키를 모두 해시 링에 배치해 노드 증감 시 재배치 최소화. 분산 캐시/샤딩에서 안정적인 키 분배가 목적.
Q6. 생일 역설을 해시 충돌 관점에서 설명?
- A. 출력 공간이 2의 𝑏 제곱일 때 1.2 x 루트 (2의 b제곱) 개 샘플만 모여도 충돌 확률이 50%에 근접. 비트 수가 충분히 커야 현실 충돌이 희박.
Q7. 개방주소법에서 클러스터링을 완화하는 방법?
- A. 선형 탐사 대신 제곱 탐사/이중 해싱 적용, 적절한 부하율 유지, 재해싱.