[ 해싱 기법 ]
▪ 데이터를 잘게 나누어 보관하고, 보관한 방법 대로 찾는 기법이다.
▪레코드(주소)
- 기본키를 가지고 있는 애트리뷰트를 이용하여 파일 내의 레코드를 찾아 낸다.
- 가능한 주소 공간 >> 실제 주소 공간 > 레코드의 수
- 논리적-물리적 독립성을 가진다.
- 키 값들은 주소 공간에 독립적이고 키 값은 그대로 두고 해쉬 함수만 조정이 가능
▪ 해싱에서의 레코드 검색 방법
- 키를 가지고 -> 주소를 찾아가 -> 레코드에 접근 해서 -> data를 얻는다.
- 순차 파일은 레코드 수가 많으면 수에 비례해서 탐색 시간이 많이 걸린다.
- 해싱은 반드시 그런 것 만은 아니다
▪ 해쉬 구조 설계시 고려해야 하는 사항들
- 버켓 크기 : 파일에서 같은 주소에 포함 될 수 있는 레코드 수
- 적재율 : 저장된 파일의 레코드 수, 버켓의 총 용량
- 해싱 함수 : 주소 생성을 위한 변환 절차
- 오버플로 해결 기법 : 버켓의 오버플로우
[ 해싱 파일 ]
▪ 해싱을 기반으로 조직된 파일을 해시 파일 또는 직접 파일이라고 한다.
▪ 해싱을 사용하면 특정 탐색 조건을 만족하는 레코드들을 매우 빠르게 접근 할 수 있다. 이런 파일 조직을 해시 파일이라고 한다. 탐색 조건은 해시 필드라고 하는 단일 필드에 대한 동등 조건이어야 한다.
▪ 해시 함수 또는 난수화 함수라고 하는 함수 h는 레코드의 해시 필드값에 적용하여 레코드를 저장하고 있 는 디스크 블록의 주소를 산출한다.
▪ 대부분의 레코드에 대해 한번의 블록 접근으로 원하는 레코드를 검색하는 매우 효율적인 방식이다.
▪ 대부분의 경우에 파일의 키 필드가 해시 필드로 사용되는데, 이 경우에 해시키라고 부른다.
▪ 해싱을 사용하면 특정 탐색 조건을 만족하는 레코드들을 매우 빠르게 접근할 수 있다. 이런 파일 조직을 해시 파일이라 한다.
▪ 한 프로그램에서 어던 필드값을 사용하여 레코드들의 그룹을 베타적으로 접근하고자 할 때, 내부 탐색 구조로서 해싱을 사용한다.
[ 내부 해싱 ]
▪ 내부 파일에서 해싱은 일반적으로 레코들의 배열을 이용하여 해시 테이블로 구현된다.
▪ 대부분의 해시 함수는 서로 다른 해시 필드값을 항상 서로 다른 주소로 사상하지는 못한다는 문제점을 가지고 있다. 그 이유는 해시 필드 공간(해시 필드가 취할 수 있는 가능한 값들의 개수)이 주소 공간(레 코드들에 대해 사용가능한 주소 개수)보다 매우 크기 때문이다.
▪ 해시 함수란 해시 필드 공간을 주소 공간으로 사상시키는 함수이다.
▪ 삽입하려는 레코드의 해시 필드 값이 이미 다른 레코드가 점유하고 있는 주소로 해싱될 때 충돌이 발생한 다. 이런 경우 새로운 레코드에 대한 해시 주소를 이미 다른 레코드가 사용하고 있으므로 새로운 레코드 를 다른 위치에 삽입해야 한다. 이렇게 다른 위치를 찾는 과정을 충돌 해결이라고 한다.
▪ 빈 공간이 많이 남지 않도록 하면서 충돌을 최소화하도록 레코드들을 주소 공간에 균등하게 분산시키는 것이 우수한 해시 함수의 목적이다.
▪ 해시 테이블을 70%~90% 정도 사용하도록 유지할 때 충돌 횟수도 줄이고, 공간낭비도 줄일 수 있다.
▪ 충돌 해결 기법
- 개방 주소 지정 : 해시 주소가 가리키고 있는 위치부터 시작하여 빈 위치를 찾을 때까지 순차적으로 그 이후의 위치들을 조사한다.
- 체인 : 충돌이 발생하면, 사용하지 않는 오버플로 영역에 새로운 레코드를 저장하고 다른 레코드가 이미 점유하고 있는 해시 주소 영역의 포인터에 오버플로 영역의 주소를 지정하여 충돌을 해 결한다.
- 다중 해싱 : 충돌이 발생하지 않을 때까지 여러 개의 해시 함수를 적용한다. 충돌 시 필요하면 개방 주소 지정 방법을 사용한다.
댓글이나 공감 남겨주는 사람 착한사람