[자료구조]Hash 공부: 해싱, 충돌, 충돌 해결

1. 룩업 Lookup(조회)

 

 룩업은 다음과 같은 작업을 의미합니다. 

• 특정 원소가 컨테이너에 있는지 확인
• 컨테이너에서 특정 키(key)에 해당하는 값(value)을 찾음

 

 

2. Why Hash?

 

 선형 검색은 O(N)의 시간 복잡도를 갖습니다. 만약 데이터의 개수가 매우 많아질 경우 선형 검색은 성능면에서 매우 느리겠죠?

 

 더 나은 방법으로 BST(이진검색트리)와 같은 속성을 갖도록 높이 균형 트리에 데이터를 저장하는 것입니다. 이 경우 시간 복잡도가 O(log N)으로 줄어 선형 검색보다는 훨씬 빨라집니다. 

 

 하지만 이 방법 역시 데이터의 개수가 매우 많아질수록 시간이 매우 오래 걸립니다. 

 

 이러한 상황에서 더욱 효율적인 방법으로 해시(hash)를 사용합니다.

 

 해시는 자료의 크기에 상관없이 모든 키의 데이터 값을 산술 연산에 의해 한 번에 바로 접근할 수 있는 기법으로, O(1)의 탐색 시간을 보장하는 자료구조 및 알고리즘입니다. 

 

 

 

3. 해싱(hashing) : 해시 함수(hash function) + 해시 값(hash value) + 해시 테이블(hash table)

 

 해싱은 각각의 데이터를 가급적 고유한 숫자 값으로 표현하고, 나중에 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나 해당 숫자에 대응하는 원본 데이터를 추출하는 작업입니다. 

 

 이때 주어진 데이터로부터 고유한 숫자 값을 계산(맵핑)하는 함수를 해시 함수(hash function)라고 합니다. 

 

 가장 간단한 해시 함수는 정수(x)를 받아 정해진 정수(n)으로 나눈 나머지를 반환하는 모듈로 함수(modulo function)입니다. (-> x%n)

 

 이처럼 해시 함수에 의해 반환되는 숫자 값을 해시 값(hash value)이라고 합니다. 

 

 해시 테이블(hash table)은 해시 값을 index로 사용하여 데이터를 저장하는 테이블 입니다. 해시 테이블을 이용하여 룩업 작업을 수행할 수 있습니다. 

 

 

 

4. 충돌 Collision

 

 충돌이란 해시 함수가 서로 다른 키에 대해 같은 해시 값을 반환함으로써, 다수의 키가 같은 값을 갖게 되는 현상을 말합니다. 

 

 예를 들어 해시 함수로써 모듈로 함수를 사용할 때 modulo(x)는 x%n을 반환한다고 합시다. 

 

 n이 7일 때, x로 9와 16이 주어지면 같은 값 2를 반환하게 됩니다. 이때 충돌이 발생한다고 말합니다. 

 

 

 

 

 

5. 충돌 해결

 

 (1) 체이닝 Chaining

 

 체이닝은 두 값을 모두 저장할 수 있는 여러 방법 중 하나입니다. 해시 테이블의 특정 위치에서 하나의 키를 저장하는 것이 아닌 하나의 연결 리스트를 저장합니다. 

 

 

부하율(load factor)은 해시 테이블에서 각각의 리스트에 저장되는 키의 평균 개수를 나타냅니다. 

 

부하율 = (전체 키의 개수) / (해시 테이블 크기) 

 

 

[장점]

 만약 키 개수가 해시 테이블 크기와 같다면 부하율은 1입니다. 이는 매우 이상적인 상태로, 모든 연산이 O(1)에 가깝게 작동하고 모든 메모리 공간을 적절하게 활용합니다. 

 

[단점] 

•  삽입의 시간 복잡도는 O(1)이지만 룩업과 삭제 연산에 경우, 선형 검색을 수행하는 것과 동일하므로 O(N)의 시간 복잡도를 갖게 됩니다. 
• 부하율이 1보다 작으면 메모리 낭비가 됩니다. 
• 부하율이 1보다 크면 검색, 삭제 등의 연산이 느리게 동작할 수 있습니다. 

 

 

 

 (2) 열린 주소 지정 Open addressing 

 

 이 방법은 체이닝처럼 해시 테이블에 추가적인 리스트를 붙여서 데이터를 저장하는 방식이 아니라 모든 원소를 테이블 내부에 저장하는 방식입니다. 

 

 그러므로 해시 테이블의 크기가 반드시 데이터 개수보다 커야 합니다. 

 

 핵심은 특정 해시 값에 해당하는 위치가 이미 사용되고 있다면 테이블의 다른 비어 있는 위치를 탐색하는 것입니다. 

 

• 선형 탐색

 선형 탐색은 가장 간단한 탐색 방법으로, 특정 해시 값에서 충돌이 발생하면 해당 위치에서 하나씩 다음 위치로 이동하면서 비어 있는 위치를 찾으면 원소를 삽입합니다. 

 

 hash(x) -> hash(x+1) -> hash(x+2) -> ... (비어 있는 위치 찾을 때까지)

 

 

 [단점]

 

 만약 동일한 해시 값을 갖는 원소가 여러 개 들어온다면 해시 테이블에 특정 위치에 서로 인접한 군집 형태로 값이 채워지게 됩니다. 

 

 이렇게 되면 원소 검색을 할 때, 해당 군집의 시작 위치부터 마지막 위치까지 선형 검색을 해야 합니다. 

 

 이처럼 데이터가 특정 위치에 군집화(clustering)되는 경우에 문제가 발생하여 검색 속도가 급격하게 느려질 수 있습니다. 

 

• 이차함수 탐색

 이차함수 탐색은 이차 방정식을 사용하여 탐색을 수행하는 방법입니다. 이등 폭을 이차함수로 형태로 증가시켜 데이터 군집이 나타날 확률이 상대적으로 줄어들게 됩니다. 

 

 hash(x) -> hash(x+1^2) -> hash(x+2^2) -> ... (비어 있는 위치 찾을 때까지)

 

 

 

 

 선형탐색과 이차함수 탐색 모두 원소 위치가 기존에 삽입되어 있는 다른 원소들에 의해 영향을 받습니다. 

 

 이때 기존에 저장되어 있던 원소는 새로 삽입하는 원소와 서로 다른 해시 값을 가질수도 있습니다. 

 

 즉 특정 해시 값을 갖는 키가 오직 하나만 존재한다 하더라도 충돌이 발생할 수 있습니다. 

 

 

 

 

 

 (3) 뻐꾸기 해싱 cuckoo hashing

 

 뻐꾸기 해싱은 완벽한 해싱 기법 중의 하나로, 구현만 제대로 한다면 O(1)의 시간복잡도를 만족합니다. 열린 주소 지정 방법과 마찬가지로 전체 해시 테이블 크기 이상의 원소를 저장할 수 없습니다. 

 

 뻐꾸기 해싱은 두 개의 해시 테이블을 사용하고, 각각의 해시 테이블은 서로 다른 해시 함수를 가집니다.

 

 원소가 두 해시 테이블 중 어디든 저장될 수 있으며 나중에 다른 위치로 이동할 수 있습니다. 

 

 룩업의 경우, 두 해시 테이블만 확인하면 되므로 시간복잡도는 항상 O(1)입니다. 

 

 반면 삽입 연산에 경우 좀 더 오래 걸릴 수 있습니다. 

 

Table1에 A 삽입 연산 -> Table1에서 해당 위치에 원소가 있는지 확인 -> 해당 위치에 B 존재 -> 해당 위치에 A 저장 -> Table2에 B 삽입 연산 -> Table2에서 해당 위치에 원소가 있는지 확인 -> 해당 위치에 C 존재 -> 해당 위치에 B 저장 -> ...

 

 

 이러한 과정에서 만약 순환(cycle)이 발생한다면 무한 루프에 빠질 수 있습니다. 

 

 일단 순환이 발생하면 새로운 해시 함수를 이용하여 재해싱을 수행해야 합니다. 

 

 하지만 적절한 해시 함수를 사용하면 높은 확률로 O(1)의 성능을 갖는 해시 테이블을 구성할 수 있습니다. (부하율 0.5 이하)

 

 

출처: https://mblogthumb-phinf.pstatic.net/MjAxODA2MTdfMjQx/MDAxNTI5MTY4NzU5Njg3.e6l4oEqCzVw2C3SIE0-uWMwc3TuTqjnZzW94_4mLFnIg.I9i4lY6ewBaxNTBy-yQS-354GmzPQLMaMpL26AL7qnUg.PNG.beaqon/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7_2018-06-17_%EC%98%A4%EC%A0%84_2.05.45.png?type=w800