해싱(Hashing) 정리

해싱의 기본 개념

해싱(Hashing)은 임의의 길이를 가진 데이터를 해시 함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업을 말합니다1. 해시 함수는 데이터의 효율적인 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수로, 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value)이라고 합니다2.

해시 테이블은 키(Key)와 데이터 값(Value) 쌍을 저장하는 자료구조로, 각 키를 해시 함수를 통해 특정 위치(index)로 변환하여 빠르게 값에 접근할 수 있도록 합니다1. 색인(Index)에 해시값을 사용하므로 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있으며3, 평균 시간복잡도가 O(1)로 매우 빠릅니다4.

해싱의 분류

1. 정적 해싱(Static Hashing)

정적 해싱은 버킷의 개수가 고정된 해싱 기법으로, 현재 파일의 크기를 고려하여 해시 함수를 결정합니다5. 해시 테이블의 크기가 고정되어 있기 때문에 데이터 양의 변화에 유연하지 못하며6, 구현이 쉽고 간단하다는 장점이 있지만 데이터의 증가에 따라 검색성능이 떨어진다는 단점이 있습니다7.

정적 해싱의 주요 기법에는 다음과 같은 것들이 있습니다7:

제산법(Division): 나머지 연산자를 이용하여 버킷 주소를 계산하는 방법
중간 제곱법(Mid-Square): 키 값을 제곱한 후 중간 부분을 사용하는 방법

2. 동적 해싱(Dynamic Hashing)

동적 해싱은 데이터 증감에 따라 해시함수가 동적으로 변환되는 방법으로, 버킷의 수를 고정시키지 않고 필요할 때 늘리거나 줄입니다8. 동적 해싱은 확장성 해싱이라고도 하며, 재조정을 한 번 할 때마다 오직 충돌(오버플로)이 일어난 버킷 안의 엔트리들만 재조정하고, 동적으로 해시 테이블의 크기를 변화시키면서 전체적으로 성능을 높여줍니다9 10.

동적 해싱의 특징은 다음과 같습니다8:

버킷의 재구조화가 한 번에 하나의 버킷에서만 일어나므로 상대적으로 적은 오버헤드 발생
현재 필요치 않은 버킷을 절약할 수 있음
해시 테이블 대신에 트라이(Trie) 자료구조를 이용

3. 확장성 해싱(Extendible Hashing)

확장성 해싱은 동적 해싱의 일종으로 디렉터리와 버킷의 2단계 구조를 가집니다11. 해시 테이블은 초기에 작은 크기로 시작하고 필요에 따라 동적으로 확장되며, 각 버킷은 고유한 주소를 가지고 있고 주소의 일부는 해시 함수를 사용하여 계산됩니다11.

확장성 해싱의 구성 요소는 다음과 같습니다8:

디렉터리: 정수값 d(디렉터리 깊이, 전역 깊이)를 포함하는 헤더와 버킷들을 지시하는 2^d개의 포인터로 구성
버킷: 각 버킷은 지역깊이 p를 표시하며, 레코드들을 실제로 저장하는 공간
모조키(pseudokey): 확장성 해싱 함수를 통해 레코드의 키를 일정 길이의 비트스트링으로 변환한 것

4. 선형 해싱(Linear Hashing)

선형 해싱은 동적 해싱 기법 중 하나로 공간을 레코드의 양에 맞게 자동으로 조절되게 하여 공간적 효율성을 증대시킵니다12. 확장 가능 해싱과 비교하여 디렉터리 없이 split이 가능하여 공간적으로 더 효율적입니다12.

선형 해싱의 동작 방식은 다음과 같습니다12:

초기에 M개의 버킷을 가정 (0~M-1)
초기 해시 함수는 h_i(k) = K mod M
record overflow가 발생하면 충돌이 발생한 버킷을 분할(split)

충돌 해결 기법

1. 체이닝(Chaining)

체이닝은 충돌이 발생했을 때 동일한 버킷에 저장하는데 이를 연결리스트 형태로 저장하는 방법입니다1. 각 버킷이 연결 리스트를 포함하도록 하여, 충돌이 발생할 경우 리스트에 추가로 데이터를 저장합니다4.

체이닝의 장점과 단점은 다음과 같습니다4:

장점: 한정된 저장소를 효율적으로 사용, 해시 함수 선택 시 충돌을 걱정하지 않아도 됨
단점: 한 Hash에 자료들이 계속 연결되면 검색 효율 저하, 외부 저장 공간 사용

2. 개방 주소법(Open Addressing)

개방 주소법은 해시 충돌이 발생할 경우 비어있는 해시를 찾아 데이터를 저장하는 방법입니다4. 충돌이 일어난 항목을 저장할 공간을 해시 테이블 내에서 찾아 해결합니다8.

개방 주소법의 주요 기법들은 다음과 같습니다8:

선형 탐사(Linear Probing): 다음 해시(+1)나 n개(+n)를 건너뛰어 비어있는 해시에 데이터 저장
제곱 탐사(Quadratic Probing): 충돌이 일어난 해시의 제곱수만큼 이동
이중 해싱(Double Hashing): 두 번째 해시함수를 사용하여 다음 순서를 결정13

3. 뻐꾸기 해싱(Cuckoo Hashing)

뻐꾸기 해싱은 2개의 해시 함수와 2개의 해시 테이블을 사용하는 방법입니다14 15. 뻐꾸기가 다른 새의 둥지에서 알을 낳고 기존 새끼를 밀어내는 습성을 모방한 해싱 방법입니다14.

뻐꾸기 해싱의 특징은 다음과 같습니다15:

모든 원소는 두 해시 테이블 중 하나에 있을 수 있음
원소가 나중에 다른 위치로 이동할 수 있음
룩업 연산의 시간 복잡도는 항상 O(1)
순환(Cycle) 발생 시 재해싱이 필요

특수 해싱 기법

1. 비트맵 인덱스(Bitmap Index)

비트맵 인덱스는 탐색키의 중복 비율이 높은 컬럼을 대상으로 하는 질의를 효율적으로 처리하기 위한 고안된 특수한 형태의 인덱스입니다16. 데이터에 해당하는 0, 1로 구성된 비트맵을 구성하고 있고, 비트맵의 조합에 의해서 데이터를 매핑하는 방식의 인덱스입니다17.

비트맵 인덱스의 특징은 다음과 같습니다17 18:

키 값을 가질 수 있는 각 값에 대해 하나의 비트맵을 구성
데이터 분포도가 나쁜 컬럼에 적합
비트 연산으로 OR연산, NULL값 비교 등이 가능
다중 조건을 만족하는 데이터 검색 시에 유리

2. 다차원 인덱스 구조

다차원 인덱스 구조는 2차원 이상의 데이터를 효율적으로 검색할 수 있도록 설계된 데이터 구조입니다19. 전통적인 1차원 인덱싱 기법으로 처리하기 어려운 공간 데이터나 복잡한 다차원 쿼리를 최적화하는 데 사용됩니다19.

주요 다차원 인덱스 구조는 다음과 같습니다19 20:

R-Tree: 공간 데이터를 저장하는 계층적 트리 구조
Quad-Tree: 2차원 공간을 4개의 균등한 영역으로 재귀적으로 분할
KD-Tree: K차원 공간에서 데이터를 분할하여 저장하는 트리 기반 인덱스
Grid Index: 공간을 균등한 그리드 셀로 나누어 저장

3. 로컬리티 센시티브 해싱(LSH)

로컬리티 센시티브 해싱은 해시 함수를 이용해 근접한 데이터 포인트를 같은 버킷에 할당하여 유사도 검색을 최적화하는 기법입니다19. 대규모 데이터에서 빠른 근접 검색을 위해 사용되며, 추천 시스템 및 머신러닝 분야에서 활용됩니다19.

해싱의 성능 최적화

부하율(Load Factor)

부하율은 해시 테이블의 성능을 결정하는 중요한 요소로, 전체 버킷에서 사용중인 버킷의 비율을 의미합니다7. 일반적으로 부하율은 70~80%가 적당하며7, 뻐꾸기 해싱의 경우 높은 성능을 보장하려면 부하율이 0.5보다 작게끔 설정해야 합니다15.

재해싱(Rehashing)

모든 해싱 방식은 해시테이블에 비어있는 원소가 적을수록 삽입에 실패하거나 해시 성능이 급격히 저하되는 현상이 발생합니다14. 재해싱은 해시테이블을 확장시키고 새로운 해시함수를 사용하여 모든 키들을 새로운 해시테이블에 다시 저장하여 성능을 향상시키는 기법입니다14.

재해싱이 수행되는 조건은 다음과 같습니다14:

적재율이 0.75를 초과할 경우 해시테이블의 크기를 2배로 확장
적재율이 0.25보다 작을 경우 해시테이블의 크기를 반으로 축소

해싱의 활용 분야

해싱은 다양한 분야에서 광범위하게 활용되고 있습니다21:

1. 보안 분야

데이터의 위변조를 막기 위한 전자서명
보안 알고리즘에 사용
암호 해싱을 통한 패스워드 보안

2. 데이터베이스 시스템

기억 공간에 저장된 정보를 빠르게 검색
해시 테이블을 이용한 인덱싱
대용량 데이터 관리 및 검색

3. 분산 시스템

Consistent Hashing을 통한 분산 캐싱22
변화하는 웹서버들의 수들 사이에서 요청 분산22
분산 해시 테이블(DHT) 디자인

4. 공간 데이터 처리

지리정보시스템(GIS)에서의 공간 데이터 인덱싱19
이미지 및 영상 검색에서의 특징 벡터 인덱싱19
IoT 데이터의 실시간 검색 및 패턴 분석19

해싱은 데이터의 효율적인 저장과 빠른 검색을 위한 핵심 기술로, 정적 해싱부터 동적 해싱, 그리고 다양한 특수 기법들까지 발전해왔습니다. 각 기법들은 고유한 장단점을 가지고 있으며, 데이터의 특성과 사용 목적에 따라 적절한 해싱 기법을 선택하는 것이 중요합니다.