해싱(Hashing) 이란?

오늘은 해싱의 개념에 대해서만 정리해보고자 한다

 

 

해싱(hashing) 이란?

선형 탐색이나 이진 탐색은 모두 키를 저장된 키 값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근한다. 이런 방법들은 최대 가능한 시간 복잡도가 O(logn)에 그친다. 이정도만 되어도 괜찮은 응용도 있지만, 어떤 응용에서는 더 빠른 탐색 알고리즘을 요구한다. 해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 

 

• 해시 테이블(hash table) : 이렇게 키에 대한 연산에 의해 직접 접근이 가능한 구조
• 해싱(Hashing) : 해시 테이블을 이용한 탐색

 

 

출처:https://www.fun-coding.org/DS&AL1-6.html

 

 

더 효율적인 알고리즘은 없을까? 예를들어 O(1)의 시간안에 탐색할 수 있는건 없을까?

해싱은 O(1)의 시간안에 탐색을 끝마칠 수도 있다.  해싱은 보통 "사전(dictionary)"이라는 자료 구조를 구현할 때에 최상의 선택이 된다. 

 

 

 

추상 자료형 사전

사전의 개념

사전(dictionary)은 (키, 값)쌍의 집합이다. 사전은 키와 관련된 값을 동시에 저장하는 자료구조이다. (키, 값)쌍을 저장할 수도 있고 (키, 값)쌍을 삭제할 수도 있으며 키를 가지고 값을 검색할 수 있따. 사전은 맵(map)이나 테이블(table)라 불림

 

• 키(key) : 사전의 단어처럼 항목과 항목을 구별시켜주는 것
• 값(value) : 단어의 설명에 해당한다.

 

해싱의 구조

만약 어떤 회사의 직원이 100명이라면 직원들은 0에서 99까지의 아이디를 부여받는다. 탐색을 하려면 단순히 크기가 100인 배열을 만들면 된다. 자료를 저장하거나 탐색하려면 직원의 아이디를 키(배열의 인덱스)로 생각하고 단지 배열의 특정 요소를 일거나 쓰면 된다. 이런 연산의 시간 복잡도는 O(1)이다. 

 

그러나 현실적으로는 탐색 키들이 문자열이거나 매우 큰 숫자이기 때문에 탐색 키를 직접 배열의 인덱스로 사용하기에는 무리가 있으므로 각 탐색 키를 작은 정수로 사상(mapping)시키는 어떤 함수가 필요하다. 해싱에서는 자료를 저장하는데 배열을 사용한다. 배열은 단점도 있지만 만약 원하는 항목이 들어 있는 위치를 알고 있다면 매우 빠르게 자료를 삽입하거나 꺼낼 수 있다. 

 

• 해싱 : 어떤 항목의 키만을 가지고 바로 항목이 들어 있는 배열의 인덱스를 결정하는 기법

• 해시 함수 : 키를 입력으로 받아 해시 주소(hash address)를 생성하고 이 해시 주소를 해시 테이블(hash table)의 인덱스로 사용 

이 배열의 인데스 위취에 자료를 저장할 수도 있고 거기에 저장된 자료를 꺼낼수도 있다. 

 

 

 

출처 : https://mattlee.tistory.com/62

 

 

키값 k를 입력받아 해시 함수 h(k)로 연산한 결과인 해시 주소 h(k)를 인덱스로 사용하여 해시 테이블에 있는 항목에 접근한다. 해시 테이블 ht는 M개의 버킷(bucket)으로 이루어지는 테이블로서 ht[0], ht[1], ..... , ht[M-1]의 원소를 가진다.

 

 

출처 : https://mattlee.tistory.com/62

 

위의 그림에서 볼 수 있듯이 하나의 버킷은 s개의 슬롯(slot)을 가질 수 있으며 하나의 슬록에는 하나의 항목이 저장됨

해시 테이블에 존재하는 버킷의 수가 M이므로 해시함수 h는 모든 키에 대하여 0<=h(x)<=M-1의 범위의 값을 제공해야 한다. 대부분의 경우 해시 테이블의 버킷 수는 모든 키의 경우의 수보다 매우 작으므로 여러 개의 서로 다른 키가 해시함수에 의해 같은 해시 주소로 사상(mapping)되는 경우가 자주 발생한다. 

 

서로 다른 두개의 키 k1과 k2에 대하여 h(k1) = h(k2)인 경우를 충돌(collision)이라고 한다. 

만약 충돌이 발생하면 같은 버킷에 있는 다른 슬롯에 항목을 저장하게 된다. 충돌이 자주 발생하면 버킷 내부에서의 순차 탐색 시간이 길어져서 탐색 성능이 저하될 수 있으므로 해시 함수를 수정하거나 해시 테이블의 크기를 적절히 조절해줘야 한다. 이러한 충돌이 버킷에 할당된 슬롯 수보다 많이 발생하게 되면 버킷에 더 이상 항목을 저장할 수 없게되는

오버플로우(overflow)가 발생하게 된다. 

 

 

 

이상적인 해싱

아까 위의 회사원의 예시를 들었던 것처럼 해시 테이블의 충분한 공간만 가지고 있으면 각각의 버킷에는 하나의 슬롯만 존재해도 되기 때문에 자료를 저장하는데 필요한 시간이 O(1)임을 알 수 있다. 즉 해시 함수를 계산하는 시간만 필요하다.

 

 

 

따라서 이러한 이상적인 경우에 해싱은 매우 빠르게 자료를 저장하고 탐색할 수 있다.

 

 

 

실제의 해싱

실제로는 해시 테이블의 크기가 제한되어 있으므로 하나의 키당 해시테이블에서 하나의 공간을 할당할 수가 없다.

보통의 경우에 키는 매우 많고, 해시 테이블의 크기는 상당한 제약을 받는 것이 일반적인 상황이다. 만약 주민번호의 경우라면 주민번호는 13자리의 십진수이므로 하나의 공간에 저장하려면 엄청난 공간이 필요하다.

 

따라서 우리는 더 작은 해시 테이블을 사용하는 해시 함수를 생각해보자. 

간단하면서도 강력한 방법은 키를 해시테이블의 크기로 나누어서 그 나머지를 해시 테이블의 주소로 하는 것이다.

정수 i를 해시 테이블 크기 M으로 나누어서 나머지를 취하면 0에서 M-1까지의 숫자가 생성된다. 이 값은 해시 테이블을 위한 유효한 인덱스가 된다.

 

h(k) = k mod M

 

위의 해시 함수는 완벽한 해시함수가 아니다. 따라서 두개 이상의 키가 동일한 해시 테이블의 공간으로 사상될 수 있다. 예를 들어 테이블의 크기를 31이라고 하면 h(01023) 와 h(01054)가 같은 주소로 매핑된다. 이러한 상황을 충돌이라 한다.

해싱에서는 이러한 충돌을 해결하는 일이 무엇보다도 중요하다 

 

 

 

위의 상황에서는 동일한 키가 하나의 buckets을 경쟁하는 상황을 충돌이라고 한다.

 

 

위와 같은 상황에서 buckets이 가득 차 있을 때 또 다른 키가 들어오려고 할 때의 상황을 오버플로우 라고 한다.

따라서 실제의 해싱에서는 충돌과 오버플로우가 빈번하게 발생하므로 시간복잡도는 이상적인 경우의 O(1)보다는 떨어지게 된다. 

 

이렇게 크게 해싱의 개념에 대해서 알아보았다.