해시, 해시함수, 해시테이블

해시(HASH)

해싱란 간단히 말해 임의로 일정한 규칙을 정해 'A->B' 변형 시키는 것을 말한다. 항상 고정된 길이의 값으로 만들며 변형된 결과 값 B는 해시 값, 또는 해시코드라고 한다. 그리고 이렇게 변형 시키는 알고리즘을 구현한 함수를 해시함수라고 칭한다. 정말 쉽다. 그리고 해시함수 안의 알고리즘은 구현하기 나름이다. 누구나 구현할 수 있지만 해싱의 비효율을 불러일으키는 충돌을 줄이는 해시함수를 누구나 구현하기란 쉽지 않다. 여기서 중요한 특징이 있다. 같은 해시함수(알고리즘 유지)를 거친다면 특정 인풋 값에 대한 아웃풋은 항상 일정하다는 것이다. 지금 간단한 해시함수 하나를 구현하려한다. 

해시함수를 간단히 다음과 같이 정의하겠다. 3으로 나눈 나머지가 색인(Index)가 되기 때문에 그에 맞게 데이터가 저장될 해시테이블의 크기로 정해야할 것이다.

int H(int input) : return input % 3;

인풋 값(정수)를 받아 항상 3에 대한 mod연산한 값을 아웃풋으로 만들어주는 알고리즘을 갖고있다. 예를 들면 다음과 같다.

121(인풋) -> 해시 함수(인풋 mod 3) -> 1(아웃풋)

얻어진 아웃풋(1) 값을 키나 주소로 하여 데이터를 저장 or 참조할 위치를 찾아가서 처리할 수 있다. 흔히 이런 시스템을 이용할 때 사용하는 자료구조를 해시테이블이라고한다. 여기까진 간단한 정의와 일반적인 사용방법이라고 할 수 있는데, 해쉬함수를 이용하는데 한계점이 있다. 해시함수를 어떻게 구현하느냐에따라 다르겠지만 서로 다른 인풋값으로 같은 아웃풋을 만들어 낼 수 있는 상황이 존재한다. 즉 같은 메모리를 참조하게 될 수 있다는 말인데, 이때 같은 곳을 두 번 참조하여 값을 저장한다고 가정하면 충돌문제가 생길 것이다. 저장하는 것도, 참조하는 것도 말이다. 이를 해결하기 위한 방법이 있다. 크게 두가지로 '분리연결법'과 '주소개방법'을 사용한다. 아래에서 이해할 수 있을 정도로만 간단히 설명하겠다.

분리 연결법(chaining)

분리 연결법이란 같은 1차적으로 같은 주소가 참조되었을 때, 그 주소에 연결리스트를 만들어 연결하고 순차적으로 데이터를 저장하는 것이다. 우선 각 해쉬 값에 대응되는 공간을 버킷이라고 하겠다. 연결리스트를 사용하기 때문에 같은 버킷이 가리키는 연결리스트가 길어질수록 탐색과 삭제 연산을 하기 위한 시간이 많이 소모될 것이다. 정확히는 순차탐색을 필요로 하기 때문인데 한 버킷에 모든 데이터가 들어간다면 일반 배열을 사용하는 방법과 비교하여 보안적인 측면을 제외하고는 거의 이득을 취할 수 있는 점이 별로 없을 것이다. 즉 같은 버킷에 저장되는 데이터가 많을수록, 충돌은 자주 일어날 수록 비효율 적이라는 것을 생각해 볼 수 있다.

개방 주소법(open addressing)

주소개방법이란 참조하려는 해시테이블의 특정 주소가 이미 사용되고 있을 때 다른 공간을 찾는 것이다. 아주 간단하게 바로 다음 인덱스의 공간을 검사하여 비어있으면 넣는 방식으로 구현할 수도 있고, 두칸씩 건너뛸 수도 있다. 한 칸인지 두 칸인지가 중요한 것은 아니다. 일반적으로 한칸씩 넘어가는 방법을 선형탐사, 제곱단위로 넘어가는 것을 제곱탐사라고 한다. 하지만 체이닝과 마찬가지로 충돌이 많다면 그만큼 비효율적이게 데이터를 삽입하고 탐색하고 삭제하게 되므로 여러 방법을 생각해 볼 필요가 있다.

궁금한 점이나 함께 더 깊은 얘기를 나누기 위해 댓글을 남겨주신다면 필히 답변하겠습니다.