해싱 기법 (2)

[ 디스크 파일을 위한 외부 해싱 ]

▪ 디스크 장치의 특성에 맞게 목표 주소 공간을 버켓들로 구성하고 각 버켓에는 다수의 레코드를 유지한다.

▪ 버켓은 디스크 블록 한 개나 연속적인 블록들의 묶음으로 이루어진다. 해시 함수에서는 버켓에 디스크 블 록 한 개나 연속적인 블록들의 묶음으로 이루어진다.

▪ 해시 함수에서는 버켓에 절대 블록 주소를 할당하는 대신에 해시 키가 K인 레코드를 해시 함수 i=h(K)에 의해 결정된 버켓 i에 저장한다.

▪ 버켓이 가득차고 삽입할 새로운 레코드가 이 버켓으로 해시될 경우 충돌이 발생한다. 충돌된 레코드는 오버플로 버켓에 저장하고 각 버켓에서 오버플로된 레코드들은 연결 리스트로 구성한다.

▪ 단점

  - 실제 레코드 수가 버켓 공간에 비해 작으면 많은 공간이 사용되지 않은 채로 남아 있을 것이고 매우 크 면 자주 충돌이 발생하고 오버플로 레코드들에 대한 연결리크트의 길이가 늘어나므로 레코드들을 검색 하는 속도가 느려진다.

  - 해시 키에 따른 순차적 접근은 매우 비효율적이며 레코드의 정렬이 요구된다.

 

[ 동적 및 확장 해싱 파일 ]

▪ 정적 해싱은 해시 주소 공간이 고정되어 파일을 동적으로 확장하고 축소하는 것이 어렵다. 이 문제를 해 결하는 기법으로는 확장 가능 해싱, 선형 해싱이 있다.

▪ 이런 해싱 기법들은 해시 함수 적용 결과가 음이 아닌 정수이고 이를 이진수로 표현할 수 있다는 이점을 활용한다. 해시 함수 적용 결과인 이진수 표현을 기반으로 접근 구조를 구성한다. 2진수 표현을 레코드에 대한 해시값이라 한다.

▪ 이진수 표현을 레코드에 대한 해시값이라 한다. 이진수 표현은 비트열로 구성된다. 레코드 해시 값에서 선행하는 비트들의 값을 기반으로 레코드들을 버켓들에 분배한다.

▪ 확장 가능 해싱

  - 확장 가능 해싱에서는 2 d개의 버켓 주소 배열을 가지는 디렉토리를 유지하는데, 여기서 d는 디렉토리 의 전역 깊이이다. 해시값의 처음 d개의 비트에 해당하는 정수값이 디렉토리 엔트리를 결정하기 위한 배열의 인덱스로 사용된다.

  - 디렉토리 엔트리 내의 주소는 해당 레코드를 저장하고 있는 버켓 주소를 나타낸다. 그러나 2 d개의 디 렉토리 엔트리가 서로 다른 버켓을 유지할 필요는 없다.

  - 처음 2 d개의 비트가 동일한 해시값을 갖는 여러 디렉토리 엔트리로 해시되는 모든 레코드를 하나의 버 켓에 저장할 수 잇으면 여러 디렉토리 엔트리에 같은 버켓 주소를 유지한다. 각 버켓에 저장하는 지역 깊이 d’는 버켓 내의 레코드가 기반으로 하는 비트수를 나타낸다.

  - 어떤 레코드를 삭제한 후, 모든 버켓에 대해 d>d’인 경우 디렉토리 배열내의 엔트리 수는 절반이 되 다.

  - 대부분의 레코드 검색은 두 개의 블록 접근(디렉토리에 대한 블록 접근, 버켓에 대한 블록 접근)을 필 요로 한다.

 

댓글이나 공감 남겨주는 사람 착한사람