← 질문 목록
#363깊이 0
좋은 해시 함수가 갖춰야 할 조건은 무엇인가?
자료구조 · 알고리즘
좋은 해시 함수는 키를 고르게 분산하고 계산 속도가 빨라야 한다. 충돌을 줄여 해시 테이블의 O(1) 성능을 유지하는 핵심이기 때문이다.
좋은 해시 함수의 조건
O(1) 성능을 유지하는 기준
균일성
키를 모든 버킷에 고르게 배치한다
결정론
같은 입력에는 항상 같은 값이 나온다
고속 연산
해시 계산 자체의 비용이 낮아야 한다
입력값이 같으면 항상 같은 해시값을 내야 한다. 이 결정론적 특성이 없으면 저장한 데이터를 다시 찾을 수 없다.
키를 버킷에 고르게 나눠 담는 균일성이 핵심이다. 특정 버킷에 키가 쏠리면 충돌이 늘어 탐색 성능이 O(N)으로 떨어진다.
계산 자체가 빨라야 한다. 암호학적 해시처럼 복잡하면 탐색 시간이 늘어난다. 해시 테이블에는 MurmurHash나 SipHash처럼 가볍고 고른 함수를 주로 쓴다.