[데이터베이스] 21. 해싱(Hashing), 해싱 함수(Hash Function), 해시 테이블(Hash Table)

1. 해싱(Hashing) 

• 해시 테이블을 이용한 탐색을 말한다.
• Hash Table 이라는 기억공간을 할당하고, 해시 함수를 이용하여 레코드 키에 대한 Hash Table 내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식이다.
• DAM(직접접근방식, ) 파일을 구성할 때 해싱이 사용되며 접근 속도는 빠르지만 기억 공간이 많이 요구된다.
• 여러가지 검색 방식 중 속도가 가장 빠르다.
• 삽입, 삭제 작업의 빈도가 많을 때 유리한 방식이다.
• 키-주소 변환 방법이라고도 한다.

2. 해시 함수(Hash Function)

• 데이터의 효율적인 관리를 위해 길고 복잡한 문자열을 간단한 문자열로 맵핑하는 알고리즘으로 키 값을 해시 값(인덱스)로 변환한다.

3. 해시 테이블(Hash Table)

• 해시 함수를 통해 얻은 해시 값을 인덱스, 주소로 삼아 데이터의 값을 키와 함께 저장하는 자료구조를 해시 테이블이라고 한다.
• 키 값의 연산에 의해 직접 접근이 가능한 구조이다.
• 레코드를 1개 이상 보관할 수 있는 Home Bucket 들로 구성한 기억 공간이다.
• 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수도 있다.

• 버킷(Bucket) : 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미한다.
• 슬롯(Slot) : 1개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성한다.
• 충돌 현상(Collision) : 서로 다른 2개 이상의 레코드가 같은 주소를 가지는 현상.
• Synonym : 같은 Home Address를 갖는 레코드들의 집합이다.
• Overflow : 계산된 Home Address의 버킷 내에 저장할 기억 공간이 없는 상태로, 버킷을 구성하는 슬롯이 여러 개일 때는 Collision은 발생해도 Overflow는 발생하지 않을 수 있다.