해시 함수(Hash function)

해시 함수는 말 그대로 입력을 변환하는 함수다. 목적은 임의의 데이터를 정해진 크기의 데이터로 바꾸는 것이다. 어떤 크기의 값을 넣어도 정해진 크기로 바뀌니 데이터 관리에 유리한 면이 있다. 하지만 정보의 크기를 한정하는 함수이기 때문에 정보 손실은 불가피하고 이것 때문에 이 함수는 단방향 함수다. 해시 함수인 결과(해시 값)만을 가지고 원래 값이 무엇이었는지는 확실히 알 수 없다.

 

본문에서는 자료구조로서의 해시 함수를 다룬다.

 

1. 키(Key)와 해시(Hash)

키는 해시 함수에 입력되는 기존 값을, 해시는 그 결과 값을 말한다.

 

이름(3글자)을 키로 받아 각 글자의 획수로 바꿔보자. 

 

 

이 방법으로 이름이 거의 대부분 3자리의 숫자로 반환된다. 이 과정에서 이름은 키, 반환된 3자리 숫자는 해시이다.

 

수많은 이름들을 3자리의 숫자로 바꿀 수 있으니 간편하다. 만약 수 천명이 모이는 행사장에 내가 참가자에게 명찰을 나누어 줘야 한다고 해보자. 물론 가나다 순으로 정리할 수도 있겠으나 김씨가 20%인 우리나라에서 김민수씨의 명찰을 찾기란 쉽지 않다. 아마도 앞에서부터 차례로 훑어보며 김갑수, 김남길, 김도, 김민수 이렇게 찾아갈 것이다. 하지만 누구의 이름을 어디에 보관했는지 바로 알 수 있다면 하나하나 비교하며 값의 선후관계(크기)를 따지지 않아도 된다. 키 값을 해시 함수로 돌려 얻은 해시 값을 인덱스로 사용하면 찾고자 하는 값을 받았을 때 해시 함수만 알고 있다면 인덱스를 바로 얻을 수 있다.

 

2. 해시 충돌(Hash Collision)

그런데 여기서 문제가 생긴다. '김민수'씨의 명찰은 '554' 인덱스에 저장되어 있어야 한다. 554 인덱스를 확인해보니 '김민수'씨가 아닌 '정상수'씨의 명찰이 있다. '정상수' 역시 해시 함수를 거치면 554로 변환되기 때문이다. 해시 함수는 분명 고정 길이 해시 값을 얻을 수 있다는 점에서 편리하지만 거의 항상 하나의 해시 값으로 대응되는 키가 2개 이상 존재한다.

 

'이제동'의 해시 값은 255이다. 그런데 새롭게 추가할 '이영호'의 해시 값도 255다. 이렇게 서로 다른 키의 해시 값이 같은 경우를 해시 충돌이라고 한다. 해시 충돌이 일어났을 때 아무 조치가 없다면 당연히 기존의 키가 사라지거나 새로운 키에 해시를 할당할 수 없다. 해시 충돌을 해결할 수 있는 방법은 크게 두 가지가 있다.

 

2-1. 개별 체이닝(Separate Chaining)

해시 충돌이 일어나면 새로운 키를 똑같은 해시 안에 이어 붙여버린다. 255 인덱스 안에 '이제동'이 있지만 뒤이어 '이영호'를 추가하는 것이다. 이후에 '장길쭉윤철'이 추가된다면 558 인덱스의 '김윤환' 뒤에 붙는다.

 

이렇게 만들어진 자료구조는 바로 해시 테이블(Hashtable)이다. 해시 충돌을 해결할 다른 방법들이 나타나면서 해시 테이블은 여러 형태를 띄게 되었지만 원래 이 방법이 해시 테이블을 구성하는 원리였다.

 

2-2. 오픈 어드레싱(Open Addressing)

개별 체이닝보다 결과적으로 깔끔해지는 처리 방법이다. 충돌이 발생하면 비어있는 공간을 탐사(Probing)한다. 하나의 인덱스에 하나의 값만 저장하기로 한 것이므로 전체 해시가 가득 찼다면 더 이상 새로운 키에 해시를 할당해줄 수 없다. 게다가 충돌이 일어났을 때, 탐사의 결과로 얻은 해시는 해시 함수로 얻는 해시와 다르기 때문에 키가 저장된 위치를 한방에 알 수 없다는 문제가 있다. 그런데 이게 구현이 간단하고 꽤 성능이 좋은 편이라고(나무위키) 한다. C++, JAVA는 개별 체이닝, 파이썬은 오픈 어드레싱을 채택했다고 한다.

 

3. 기타

해시 함수를 돌리고 해시를 얻는 과정에 너무 많은 비용이 든다면 데이터 관리에서의 이점이 없다. 특별한 이유가 없다면 해시 함수는 복잡하지 않은 것이 좋은 것 같다.

해시 함수가 복잡하고 해시 값이 매우 길고 무작위적이라면 암호로 쓸 수 있다. 암호를 위한 해시는 입력값의 변화에 따라 해시 값이 매우 크게 달라진다. 그리고 해시 값으로 키 값을 추적하기 어려워야 하며 해시 충돌이 일어나서는 안 된다.

 

4. 연습 문제

10815번: 숫자 카드

 

해시 함수를 f(x) = x라고 두어도 된다. 무엇보다 해시 충돌 없는 최고의 해시 함수!

 

14425번: 문자열 집합