[Data Structure] Hashing

프로그래머스에서 문제를 풀다가 해쉬 개념과 관련된 문제를 풀었다. 해쉬 관련 문제 풀이를 블로그에 올렸으니 해쉬 테이블에 대해서도 블로깅해봐야 할 것 같아서 정리해보았다.

 

1. Hash란

Hash하는 것, 즉 Hahsing은 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식이다. 키 값을 비교하여 찾는 검색 방법이 아니다.

이 과정에서 쓰이는 함수와 테이블이 있다. 각각 Hash Function, Hash Table이라 불린다.

해쉬 함수(Hash Function)는 키 값을 원소 위치로 변환한다.

해쉬 테이블(Hash Table)은 해쉬 함수에 의해 계산된 주소 위치에 항목을 저장한 표다.

이와 같은 설명을 그림과 같이 표현하면 다음과 같다.

 

 

그림과 같이 키 값에 대해서 해쉬 함수를 계산한 후, 주소를 구해서 주소에 해당하는 해쉬 테이블의 값을 찾는다.

해쉬 테이블로 이동했을 때 찾는 항목이 있으면 검색 성공이고, 없으면 검색 실패다.

 

해싱(Hashing)의 예시는 다음과 같다.

 

• 도서관에서 책을 찾을 때

책을 찾을 때 책꽂이 처음부터 찾는게 아니라, 찾는 도서의 번호를 이용해서 책을 찾는다.

도서관의 책이 키(k)이고, 

도서관에서 발급되는 도서 번호가 해쉬 함수를 통해 발급받은 주소(h(k))가 된다.

도서 번호를 가지고 책꽂이(Hash Table)에서 책이 있는 위치를 찾는다.

도서 검색 시스템이 전산화되어있을 경우, 도서 검색 시스템에서 제목을 입력하여 책의 위치를 찾는 것도 해싱이다.

 

• 학번에 따른 강의실 자리 배정

학번을 입력하면 강의실 자리 번호를 임의로 생성하여 자리를 배정한다고 가정하자.

학번이 키 값이 되고,

강의실 자리 번호를 생성하는 것은 해쉬 함수를 사용하는 것과 같다.

자리 번호 생성기로 강의실 자리의 위치를 찾으므로, 실제 강의실 자리는 해쉬 테이블과 같다.

 

2. 해싱(Hashing) 관련 용어

2.1 동거자

키 값 중에서 많이 사용되는 값이 있고, 잘 사용되지 않는 값이 있을 수 있다. 그렇기 때문에 키 값마다 버킷을 만들어버리면, 메모리 낭비가 일어날 수 있다. 이러한 것을 방지하기 위해, 버킷 안에 여러 개의 키 값을 저장한다.

실제로는 서로 다른 키 값을 가지지만, 해쉬 함수를 사용했을 때 같은 주소 값이 나오는 키 값들을 한 버킷안에 다 넣는다.

이때 한 버킷 안에 저장돼 있는 키 값을 동거자(Synonym)라고 한다.

 

이렇게 버킷을 여러 슬롯으로 나누는 것은, 자리를 배정할 때 1인용 좌석이 아니라 다인용 좌석에 배정하는 것과 같다고 생각하면 된다.

 

2.2 충돌

키 값이 다른 경우인데, 해쉬 함수를 썼을 때 같은 버킷 주소로 배정받을 경우 충돌이 일어난다고 한다.

이러한 충돌을 동거자를 설명할 때 나온 버킷 개념을 사용하면 해결되겠지라고 생각할 수 있다.

물론 충돌이 일어난 키 값들을 한 버킷을 여러 슬롯으로 나누어 넣으면 되지만,

버킷에 비어 있는 슬롯이 없을 경우 문제가 된다.

버킷에 비어 있는 슬롯이 없는 상태를 포화 버킷 상태라고 한다.

 

포화 버킷 상태에서 같은 버킷을 지정받은 키 값이 일어나서 또 충돌이 난다면,

오버플로가 된다.

 

2.3 키 값 밀도와 적재 밀도

• 키 값 밀도 = 실제 사용 중인 키 값의 개수 / 사용 가능한 키 값의 개수
• 적재 밀도 = 실제 사용 중인 키 값의 개수 / 해쉬 테이블에 저장 가능한 전체 키 값의 개수
• 해쉬 테이블 = 버킷 개수 * 슬롯 개수 이므로 적재밀도는 이렇게도 나타낼 수 있다.
  • 적재 밀도 = 실제 사용 중인 키 값의 개수 / (버킷 개수 * 슬롯 개수)

 

3. 해쉬 함수(Hash Function)

해싱(Hashing)에서 가장 중요한 것은 키 값의 위치를 계산하는 해쉬 함수이다.

어떤 해쉬 함수를 사용하느냐에 따라 해싱 검색의 효율이 달라지기 때문이다.

 

효율이 좋은 해쉬 함수를 만들기 위한 조건은 다음과 같다.

• 해쉬 함수는 계산이 쉬워야 함 : 비교 검색 방법보다 해쉬 함수를 사용하여 검색하는 방법이 더 빨라야 해싱 검색을 사용하는 의미가 있음
• 해쉬 함수는 충돌이 적어야 함 : 충돌이 많다는 것은 같은 버킷에 많은 키 값이 들어갈 수 있다는 것이다. 이는 오버플로로 이어질 수 있으므로 오버플로가 발생할 수 있는 확률을 줄여야 함
  • 해쉬 테이블에 고르게 분포할 수 있도록 주소를 만들어야 함

 

4. 해싱(Hashing)에서 오버플로 해결하기

4.1 선형 개방 주소법

오버플로가 발생했을 때 그 다음에 빈 버킷이 없나 조사하는 방법이다.

그 다음 버킷에 빈 슬롯이 있다면 키 값을 저장하고 없으면 또 다음 버킷을 조사한다.

 

4.2 체이닝

각 버킷에 하나 이상의 키 값을 저장할 수 있도록 해쉬 테이블의 구조를 바꾸는 방법이다.

버킷 안의 슬롯을 동적으로 삽입, 삭제하기 위한 연결 리스트를 사용한다.

버킷은 1차원 배열이다.

버킷 안의 슬롯은 헤드 노드에 연결 리스트를 사용한다.

버킷 내에서 검색할 때는 버킷의 연결리스트를 선형 검색한다.

 

예시 그림은 다음과 같다.

이때 해쉬 함수는 h(k) = k mod 5 = k % 5 이다.

 

 

 

해싱은 실제로 많은 곳에서 쓰일 수 있을 것 같다.

대표적으로는 회원 비밀 번호 저장할 때 사용될 수도 있을 것 같다.

 

참조

• C로 배우는 쉬운 자료 구조, 이지영, 한빛아카데미(2016)