해싱

해싱(Hashing)은 데이터를 저장하고 검색하기 위한 자료구조 중 하나로, 매우 빠른 검색 속도를 제공합니다. 해싱은 키(Key)와 값(Value)으로 이루어진 데이터를 해시 함수(Hash Function)를 통해 고정된 길이의 해시 값(Hash Value)으로 변환한 뒤 이 해시 값을 주소(Address)로 사용하여 바로 값(Value)에 접근할 수 있게하는 방법입니다.

보통 일반적으로 순차적으로 데이터를 찾을 때는 O(N) 시간복잡도가 걸리고, 이진 탐색으로 이용하면 O(logN) 시간복잡도가 걸립니다. 하지만 해싱을 이용하면 O(1) 시간복잡도로 데이터를 찾을 수 있습니다.

정적해싱

정적 해싱(Static Hashing)은 고정 크기의 해시 테이블에 데이터를 저장하는 해싱 기법입니다. 해시 테이블은 버킷이라는 고정된 크기의 저장 단위를 갖습니다. 정적 해싱은 버킷의 개수(bucket address)가 고정되어 있는 해싱 방법입니다.

(한 버킷이 디스크의 한 블록에 해당합니다. )

각각의 버킷은 하나 이상의 데이터(entry)를 저장할 수 있습니다. 이러한 데이터는 검색 키(search-key) 값에 의해 식별됩니다. 따라서 검색 키 값을 해시 함수(hash function)를 통해 버킷 주소(bucket address)로 변환하여 버킷에 저장합니다.

이때 데이터의 검색 키 값을 해시 함수를 통해 버킷 주로로 매핑될 때 다른 검색 키여도 같은 버킷 주소로 매핑될 수 있스빈다. 그래서 조회할 때 해당 버킷을 순차적으로(sequential) 검사해야 합니다.
-> 이 부분이 성능의 병목이 된다. 해시를 사용하는 이유는 조회 성능이 O(1)이여서인데, 해시 충돌로 인해 선형적으로 탐색해야하기 때문..

버킷 오버플로우

버킷 오버플로우란, 한 버킷에 저장될 수 있는 데이터(entry)의 개수를 초과하여 추가적인 데이터가 저장될 때 발생하는 현상입니다. 버킷 오버플로우는 버킷의 개수가 부족하거나 해시 함수가 키(key) 값의 분포를 고르게 만들지 못하는 경우 발생할 수 있습니다. 또한 같은 검색 키 값을 갖는 데이터가 여러 개 존재할 경우에도 버킷 오버플로우가 발생할 수 있습니다.

버킷 오버플로우는 검색 키에 비해 버킷 주소가 현저히 적기 때문에 그 가능성은 줄일 수 있어도 아예 제거할 수는 없습니다. 따라서 오버플로우 버킷(overflow buckets)을 사용해 버킷 오버플로우를 처리합니다.

오버플로우 버킷

버킷 오버플로우가 발생하면 새로운 버킷을 만들어 연결리스트로 오버플로우 버킷을 만들어 관리합니다.

위 사진은 폐쇠 해싱(closed addressing, closed hashing,chain)을 이용해 문제를 해결한 것으로 동일 버킷에 들어갈 데이터를 오버플로우 버킷을 만들고 연결 리스토로 연결하여 해결합니다. 주로 체이닝(chaining)을 이용합니다.

cf) 개방 주소 지정(open addressing, open hashing)은 오버플로우된 데이터를 저장할 공간을 해시 테이블 내에서 찾아 해결합니다. 개방 주소법은 오버플로우 버킷 대신 버킷 내부의 다른 위치를 사용하여 데이터를 저장합니다. 이러한 방법은 오버플로우 버킷에 의존하지 않으므로 공간적인 이점이 있습니다. 그러나 데이터의 저장 위치를 찾기 위해 일반 버킷을 순회하면서 비어있는 위치를 찾아야 하기 때문에 검색 작업이 더 복잡해집니다. 또한 데이터의 개수가 많아질수록 충돌이 발생할 확률이 높아지므로 개방 주소법은 데이터베이스 애플리케이션에는 적합하지 않습니다.
EX) 선형 조사(Linear probing) , 제곱 조사(Quadratic Probing),이중 해싱(double Hashing) 등

동적 해싱

정적 해싱 문제점

정적 해싱에서는 버킷의 개수가 고정되어 있어서, 데이터베이스가 성장하거나 축소할 경우에 문제가 발생할 수 있습니다. 예를 들어 초기 버킷의 수가 너무 적으면 , 파일이 커지에 따라 오버플로우 버킷이 많아져 성능이 떨어질 수 있습니다. 반대로 상대적으로 많은 버킷이 할당 되면, 상당 부분의 공간이 낭비 될 것입니다. 또한 삭제 연산이 많이 발생했을 때도 공간이 낭비 될 것입니다.
이를 해결하기 위해, 주기적으로 새로운 해시 함수를 이용해서 파일을 재구성(re-organization)할 수 있지만 이는 상당히 비용(cost)가 많이 들어가게 됩니다.

동적 해싱

따라서 동적 해싱이 사용되는데, 이는 데이터베이스의 크기에 따라 버킷의 개수를 동적으로 조정할 수 있는 방식입니다.

• 데이터의 증감에 따라 버킷의 개수를 동적으로 변화시킬 수 있다.
• 로직이 복잡하다
• 데이터가 증가해도 검색의 성능이 유지된다.
• 연결이나 링크(link)를 사용하지 않기 때문에 접근 시간을 일정하게 유지할 수 있다.

대표적으로 Linear Hashing , Extendable Hashing이 있다.

해시 인덱스와 해시 파일 구조

해시 인덱스(hash index)에서는 버킷에 저장된 포인터를 이용하여 포인터가 가리키는 곳을 따라가면 레코드를 찾을 수 있고, 해시 파일 구조(hash file-organization)에서는 포인터 대신에 레코드를 저장하고 있는 구조로 레코드를 직접 참조할 수 있습니다.