해시 함수와 해시 테이블 자료구조란 무엇일까?

해시 함수(Hash function)

해시 함수는 임의 길이의 데이터를 고정된 길이의 데이터로 바꿔주는 함수이다. 

해시 함수에 의해 얻어지는 값은 해시 값 또는 해시라고 부른다.

위키백과에 게재되어 있는 해시 함수의 정의다. 간단히 말하면 특정 값을 넣었을 때, 내가 원하는 범위의 값이 나오게 만드는 함수라고 말 할 수 있다.

간단히 그림으로 표현하자면 다음과 같이 표현할 수 있다.

 

 해시 함수의 용어로는 충돌(Collision)과 클러스터(Cluster)가 있다.

 

 충돌은 다른 값을 넣었을 때 같은 해시 값이 나오는 경우를 말한다. 클러스터는 해시 값에 의해 저장된 값들이 특정 구역에 몰리는 현상을 말한다.

 그럼 이런 해시 함수는 왜 존재하는 걸까? 해시 함수는 주로 보안, 오류 검사, 자료구조 등 활용 용도는 매우 많지만 이 게시글에서는 자료 구조로써의 활용법만 알아 보도록 하겠다.

 자료구조로써의 해시 함수는 해시 테이블이라는 자료구조를 구현하는데 이용된다.

해시 테이블 (Hash Table)

 해시 테이블은 입력 값의 해시 값을 Index로 이용하는 자료구조이다. 주로 입력값의 빠른 탐색을 위해 이용되는데, 간단하게 그림으로 표현하면 다음과 같다.

 여기서의 해시 함수는 값을 9로 나눈 나머지가 되는데, 이와 같은 방법은 가장 기초적인 것으로 충돌이 일어날 확률이 크다. 이 예제에서는 길이 9의 배열에 데이터를 넣고 싶은 조건이기 때문에 해시 값이 0이상 8이하의 정수로 나와야 하고, 그래서 mod 연산을 이용해 값을 구하게 된 것이다. 이것이 바로 고정 길이 데이터를 출력으로 낸다는 방법이다.

 

 만약 여기서 값 21이 들어온다면 mod 9 의 결과값은 3이되고, 값 21은 이미 12가 들어있는 index 3에 들어가면서 충돌이 일어나게 된다.

 이 경우 Index 3에 링크드 리스트 등을 구현해 다음 노드를 추가하거나 약속된 방법으로 다른 위치에 추가하면 되지만 (3칸 옆으로 이동해서 저장한다던지) 이 경우 추가적인 비교연산이 일어나면서 빠르게 값을 탐색해야 하는 해시 테이블의 성능이 떨어지게 된다. 그러므로 해시 테이블에서의 해시함수의 충돌은 가능하면 적을수록 좋다.

 문자열에 대한 해시 함수도 존재하는데 주어진 문자열의 각 문자를 정수로 변환시켜서 각각 특정 연산을 거친 다음, 연산을 거친 모든 값을 더하는 방식으로 구현될 수 있다.

 

 졸업과제를 수행할 때 djb2 해시를 이용하였었는데, 이 함수가 꽤나 좋은 성능을 낸다고 한다.

- 분리 연결법과 개방 주소법 (Separate Chaining and Open Addressing)

 해시 테이블 자료구조에서 충돌이 일어났을 때 데이터를 어디에 넣을 지 처리하는 방법이다.

 분리 연결법은 위에서 말한 것 처럼 해당 Index에 링크드 리스트와 같은 자료구조를 연결시켜 추가하는 방법이다.

 개방 주소법은 비어있는 Index를 찾아 데이터를 입력하는 방법이다. 개방 주소법 같은경우 다른 Index로 가는 포인터를 하나씩 가지고 있는다던가, 선형으로 1씩 늘리면서 빈공간을 사용하는 방법 등이 있다.

 

참고해볼만한 자료

 문자열 해시함수에 대한 사이트

 http://www.cse.yorku.ca/~oz/hash.html

 https://stackoverflow.com/questions/7666509/hash-function-for-string/45641002#45641002

 http://www.partow.net/programming/hashfunctions/#DJBHashFunction