[자료구조] 해시(Hash)란? - (1) 개념, 충돌, 예시, 알고리즘

얼마 전 있었던 백엔드 직무 면접에서

 

기초 질문을 받았는데 대답을 잘 못했다.

 

 

생각해보면 해시에 대해 자세히 공부해 본 적이 없던 것 같다.

 

 

이번 기회에 나무위키와 위키백과의 글을

 

참고로 공부하여 작성하였다.

 

---

 

해시 - 정의

위키백과에서는 "해시 함수에 의해 얻어지는 값"을

 

해시(해시 값, 해시 코드, 해시 섬, 체크섬)라고 정의하고 있다.

 

 

해시 함수 - 정의

그렇다면 해시 함수(Hash Function)란?

 

 

임의의 길이를 갖는 임의의 데이터를

 

고정된 길이의 데이터(해시 값)로 매핑하는 함수를 말한다.

 

 

아래 그림으로 한눈에 이해 가능할 듯싶다.

 

출처) https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

 

 

해시 함수 - 특성

해시 함수는 보통 그리 복잡하지 않은 알고리즘으로 구현된다.

 

 

따라서 상대적으로 CPU, 메모리 등의

 

시스템 자원을 덜 소모하는 특성이 있다.

 

 

그리고 같은 입력값에 대해서는 값은 출력 값이 보장되고,

 

이 출력 값은 가능한 한 고른 범위에 균일하게 분포하는 특성이 있다.

 

 

특수 목적용으로 해시값을 생성하는 원본과 별도의 값을 입력받아서 

 

같은 입력에 대해 다른 출력 값을 가지게 하는 해시 함수도 존재한다.

 

 

ex) 'abc'(입력값) + '!@#'(별도의 값) -> '1234'(해시 값)

 

 

해시 함수 - 충돌

해시 함수는 보통 입력값의 범위보다

 

출력 값의 범위가 좁은 경우가 많다.

 

 

그래서 입력값이 달라져도 드물게 동일한 출력 값이 나오는 경우가 있다.

 

 

이러한 경우를 '충돌'한다고 하는데,

 

해시 함수는 원칙적으로 이런 어쩔 수 없는 충돌을 제외하고는

 

의도적으로 충돌을 계산해낼 수 없어야 한다.

 

 

그래서 해시 함수의 질(quality)은 이러한 해시 충돌 확률로 결정된다.

 

 

해시 충돌의 확률이 높을수록

 

서로 다른 데이터를 구별하기 어려워지고

 

검색하는 비용이 증가하게 된다.

 

비둘기 집의 원리

컴공생이라면 많이 들어본 비둘기 집의 원리가

 

해시 함수의 충돌과 깊은 관련이 있다.

 

 

비둘기 집의 원리는 간단하게 말해서

 

N개의 상자에 N+1개의 물건을 넣은 경우,

 

최소한 한 상자에는 물건이 반드시 두 개 이상 들어있다는 원리이다.

 

 

보통 비둘기와 비둘기집의 형태로 비유되어 쓰이기 때문에,

 

비둘기 집의 원리라고 불린다.

 

 

증명이나 확장 등의 더 깊은 내용을 알아보고 싶다면

 

여기로 가면 된다.

 

생일 문제

'갑자기 웬 생일 문제?'라고 생각할 수 있겠지만,

 

비둘기 집 원리와 관련이 있기 때문에

 

결국 해시 충돌과도 관련이 있어 설명한다.

 

 

생일 문제(Birthday problem)는 

 

여러 사람이 임의로 모였을 때,

 

그중 생일이 같은 두 명이 존재할 확률을 구하는 문제이다.

 

 

2월 29일을 고려하면, 생일의 가짓수는 366개이다.

 

 

만약 366명 이상의 사람이 모인다면,

 

비둘기 집 원리에 따라 생일이 같은 두 명이 반드시 존재한다.

 

 

얼핏 생각해 보면 366명 이상이 모여야

 

그 중 두 명이 생일이 같은 경우가 있을 것이라 생각하기 쉽지만,

 

실제로는 아니다.

 

 

여러 수식을 통해 계산해보면,

 

23명 이상이 모일 경우 그 중 두 명이 생일이 같은 확률은 50%를 넘고,

 

57명이 모이면 99%를 넘어가며,

 

100명이 모이면 거의 1에 가까워진다.

 

 

(이러한 확률 계산 방법은 여기에서 확인할 수 있다.)

 

 

따라서 해시 충돌이 일어나는 두 입력값을 찾는 것 역시,

 

모든 입력값을 계산하지 않아도

 

충분히 높은 확률로 해시 충돌을 찾을 수 있음을 알 수 있다.

 

 

해시 함수 - 예시

위에서 알아본 해시 함수 특성들에 의해

 

다양한 목적으로 설계된 해시 함수가 존재하며

 

다음과 같은 다양한 분야에서 매우 유용하게 사용된다.

 

 

- 자료구조 : 해시 테이블(또는 해시 맵), 해시 셋(set), 블룸 필터(Bloom Filter)

 

- 캐시

 

- 중복 레코드 검색 (DB, 테이블)

 

- 유사 레코드 검색 (DB, 테이블)

 

- 유사 부분 문자열 검색

 

- 기하학적 해시

 

- 변조 탐지 / 에러 검출

 

 

여기서 특히 '해시 테이블'은 

 

입력 값이 해시 함수를 통과하여 나온 해시 값을 인덱스로 사용하는

 

효율적인 검색 방식을 가진 자료구조이다.

 

 

이와 관련해서는 다음 글에서 좀 더 자세히 살펴볼 예정이다.

 

 

하여튼, 근래에 나오는 프로그래밍 언어들은

 

기본 라이브러리에 해시 함수가 포함되어 있는 경우가 많아서

 

굳이 구현할 필요 없이 바로 해시 값을 추출해서 사용 가능하다.

 

 

다만 좀 오래된 언어들은 확장 라이브러리를 설치하거나 직접 구현해야 하는데,

 

파이썬의 경우에도 사전(Dictionary)에 클래스(Class)를 넣으려면

 

해시 함수를 구현해야 한다.

 

 

이때, 해시와 함께 비교 함수(cmp)도 구현해야 하며

 

만약 해시 함수가 구현되어 있지 않다면,

 

그 객체의 주소 값을 해시 값으로 대체한다.

 

 

해시 - 알고리즘

이러한 해시 함수에 사용되는 알고리즘으로는

 

Message-Digest Algorithm(MD)과

 

Secure Hash Algorithm(SHA) 등이 있다.

 

 

각 알고리즘은 심각한 해시 충돌 문제 등으로 인해

 

해시 함수를 개선하며,

 

발표된 순서대로 MDn, SHA-n 식으로 넘버링된다.

 

 

다만 SHA-2는 예외로,

 

SHA-256, SHA-512와 함께

 

SHA-2족(SHA-2 family)이라고 부른다.

 

 

2014년 기준으로 최신 버전은 MD6, SHA-3이나

 

보통은 본인이 사용하는 프로그래밍 언어에서 제공하는

 

라이브러리에 포함된 기본 해시 함수를 사용하게 된다.

 

 

그중 대부분은 MD5나 SHA-1을 기반으로

 

구현된 사례가 많다고 한다.

 

---

 

다음 글에서는 해시 테이블에서

 

해시 값이 충돌하는 경우,

 

어떻게 처리하는지에 대해 알아본다.

 

 

끝!