해싱 개념


소개

해시 파일 구성 방법은 해시 함수를 사용하여 주소가 생성 된 데이터 블록에 데이터를 저장하는 방법입니다. 이러한 레코드가 저장되는 메모리 위치를 데이터 블록 또는 데이터 버킷이라고합니다. 이 데이터 버킷은 하나 이상의 레코드를 저장할 수 있습니다.

해시 함수는 열 값을 사용하여 주소를 생성 할 수 있습니다. 대부분의 경우 해시 함수는 기본 키를 사용하여 데이터 블록의 주소 인 해시 인덱스를 생성합니다. 해시 함수는 복잡한 수학 함수에 대한 간단한 수학 함수가 될 수 있습니다. 기본 키 자체를 데이터 블록의 주소로 간주 할 수도 있습니다. 즉, 각 행은 주소가 기본 키와 동일한 데이터 블록에 저장됩니다. 이것은 데이터베이스에서 해시 함수가 얼마나 간단한지를 의미합니다.

위 다이어그램은 기본 키 값과 동일한 데이터 블록 주소를 나타냅니다. 이 해시 함수는 mod, sin, cos, exponential 등과 같은 간단한 수학 함수일 수도 있습니다. 데이터 블록의 주소를 결정하기 위해 mod (5)로 해시 함수가 있다고 상상해보십시오. 그렇다면 위의 경우는 어떻게됩니까? 기본 키에 mod (5)를 적용하고 각각 3,3,1,4 및 2를 생성하고 레코드는 해당 데이터 블록 주소에 저장됩니다.

위의 두 다이어그램에서 해시 함수가 작동하는 방식이 명확 해졌습니다.

해시 파일 구성에는 두 가지 유형이 있습니다. 정적인동적 해싱.

정적 해싱

이 해싱 방법에서 결과 데이터 버킷 주소는 항상 동일합니다. 즉, mod (103) 해시 함수를 사용하여 EMP_ID = 5에 대한 주소를 생성하려는 경우 항상 동일한 버킷 주소 3이 생성됩니다. 여기서 버킷 주소는 변경되지 않습니다. 따라서이 정적 해싱에 대한 메모리의 데이터 버킷 수는 전체적으로 일정하게 유지됩니다. 이 예에서는 데이터를 저장하는 데 사용되는 메모리에 XNUMX 개의 데이터 버킷이 있습니다.

기록 검색

해시 기능을 사용하여 해시 키에 대한 데이터 버킷 주소가 생성됩니다. 그런 다음 해당 위치에서 레코드가 검색됩니다. 즉; ID 104에 대한 전체 레코드를 검색하고 ID에 대한 해시 함수가 mod (5)이면 생성 된 주소는 4가됩니다. 그러면 주소 4에 직접 도달하여 ID 104에 대한 전체 레코드를 검색합니다. 여기서 ID 해시 키 역할을합니다.

레코드 삽입

새 레코드를 테이블에 삽입해야 할 때 해시 키를 기반으로 새 레코드에 대한 주소를 생성합니다. 주소가 생성되면 레코드가 해당 위치에 저장됩니다.

기록 삭제

해시 함수를 사용하여 먼저 삭제할 레코드를 가져옵니다. 그런 다음 메모리에서 해당 주소에 대한 레코드를 제거합니다.

레코드 업데이트

업데이트 표시된 데이터 레코드는 정적 해시 기능을 사용하여 검색 한 다음 해당 주소의 레코드가 업데이트됩니다.

 

파일에 일부 레코드를 삽입해야한다고 가정합니다. 그러나 해시 함수에 의해 생성 된 데이터 버킷 주소가 꽉 찼거나 해당 주소에 데이터가 이미 있습니다. 데이터를 어떻게 삽입합니까? 정적 해싱의 이러한 상황을 버킷 오버플로. 이것은이 방법의 중요한 상황 / 결점 중 하나입니다. 이 경우 데이터를 어디에 저장합니까? 우리는 데이터를 잃을 수 없습니다. 이 상황을 극복하기위한 다양한 방법이 있습니다. 가장 일반적으로 사용되는 방법은 다음과 같습니다.

닫힌 해싱

이 방법에서는 동일한 주소를 가진 새 데이터 버킷을 도입하고 전체 데이터 버킷 이후에 연결합니다. 이러한 버킷 오버플로를 극복하는 방법을 폐쇄 형 해싱 또는 오버플로 체인.

새 레코드 R2를 테이블에 삽입해야한다고 생각하십시오. 정적 해시 함수는 데이터 버킷 주소를 'AACDBF'로 생성합니다. 그러나이 버킷은 새 데이터를 저장하기에 가득 찼습니다. 이 경우 수행되는 작업은 'AACDBF'데이터 버킷 끝에 새 데이터 버킷이 추가되고 여기에 연결됩니다. 그런 다음 새 레코드 R2가 새 버킷에 삽입됩니다. 따라서 정적 해싱 주소를 유지합니다. 가득 차면 새 데이터 버킷을 원하는만큼 추가 할 수 있습니다.

해싱 열기

이 방법에서는 사용 가능한 다음 데이터 블록을 사용하여 이전 레코드를 덮어 쓰는 대신 새 레코드를 입력합니다. 이 방법을 Open Hashing 또는 선형 프로빙.

아래 예에서 R2는 삽입해야하는 새 레코드입니다. 그러나 해시 함수는 주소를 237로 생성합니다. 그러나 이미 가득 찼습니다. 따라서 시스템은 사용 가능한 다음 데이터 버킷 인 238을 검색하고 여기에 R2를 할당합니다.

선형 프로빙에서 이전 버킷과 새 버킷의 차이는 일반적으로 고정되며 대부분의 경우 1입니다.

XNUMX 차 프로빙

이것은 선형 프로빙과 유사합니다. 그러나 여기서 이전 버킷과 새 버킷의 차이는 선형입니다. XNUMX 차 함수를 사용하여 새 버킷 주소를 결정합니다.

이중 해싱

이것은 또한 선형 프로빙의 또 다른 방법입니다. 여기서 차이는 선형 프로빙과 같이 고정되지만이 고정 된 차이는 다른 해시 함수를 사용하여 계산됩니다. 따라서 이름은 이중 해싱입니다.

동적 해싱

이 해싱 방법은 정적 해싱의 문제인 버킷 오버플로를 극복하는 데 사용됩니다. 이 해싱 방법에서 데이터 버킷은 레코드가 증가하거나 감소함에 따라 증가하거나 감소합니다. 이 해싱 방법을 확장 가능한 해싱 방법이라고도합니다. 이 방법을 이해하는 예를 살펴 보겠습니다.

테이블에 R1, R2 및 R4의 세 개의 레코드가 있다고 가정하십시오. 이러한 레코드는 각각 주소 100100, 010110 및 110110을 생성합니다. 이 저장 방법은이 주소의 일부만 고려합니다. 특히 데이터를 저장할 첫 번째 비트 만 고려합니다. 따라서 주소 0과 1에서 세 개를로드하려고합니다.

여기서 R3는 어떻게 되나요? R3에는 버킷 공간이 없습니다. 버킷은 R3를 수용하기 위해 동적으로 커야합니다. 따라서 주소를 2 비트가 아닌 1 비트로 변경 한 다음 기존 데이터를 2 비트 주소로 업데이트합니다. 그런 다음 R3를 수용하려고합니다.

이제 R1과 R2의 주소가 새 주소를 반영하도록 변경되고 R3도 삽입 된 것을 볼 수 있습니다. 데이터 크기가 증가하면 기존 버킷에 삽입을 시도합니다. 사용 가능한 버킷이 없으면 더 큰 주소를 고려하여 비트 수가 증가하므로 버킷이 증가합니다. 레코드를 삭제하고 더 적은 버킷에 데이터를 저장할 수 있으면 버킷 크기가 줄어 듭니다. 위에서 본 것과 반대입니다. 이것이 동적 해싱이 작동하는 방식입니다. 처음에는 해시 함수에 의해 생성 된 부분 인덱스 / 주소 만 데이터를 저장하는 것으로 간주됩니다. 데이터 수가 증가하고 더 많은 버킷이 필요하면 인덱스의 더 많은 부분이 데이터 저장을 고려합니다.

동적 해싱의 장점

  • 시스템에서 데이터가 증가해도 성능이 저하되지 않습니다. 단순히 데이터를 수용하기 위해 메모리 크기를 증가시킵니다.
  • 데이터와 함께 늘어나고 줄어들 기 때문에 메모리가 잘 활용됩니다. 사용되지 않은 메모리가 거짓말하지 않습니다.
  • 데이터가 자주 증가하고 축소되는 동적 데이터베이스에 적합합니다.

 

동적 해싱의 단점

  • 데이터 크기가 증가하면 버킷 크기도 증가합니다. 이러한 주소는 버킷 주소 테이블에 유지됩니다. 이는 버킷이 커지거나 작아지면서 데이터 주소가 계속 변경되기 때문입니다. 데이터가 엄청나게 증가하면이 버킷 주소 테이블을 유지하는 것이 지루해집니다.
  • 이 경우에도 버킷 오버플로 상황이 발생합니다. 그러나 정적 해싱보다이 상황에 도달하는 데 시간이 거의 걸리지 않을 수 있습니다.

정렬 된 인덱싱과 해싱 비교

정렬 된 인덱싱

해싱

메모리의 주소는 키 값으로 정렬됩니다. 이 키 값은 기본 키 또는 테이블의 다른 열일 수 있습니다.주소는 키 값에 해시 함수를 사용하여 생성됩니다. 이 키 값은 기본 키 또는 테이블의 다른 열일 수 있습니다.
이 방법의 성능은 파일의 데이터가 증가함에 따라 저하됩니다. 데이터를 정렬 된 형태로 저장하므로 삽입 / 삭제 / 업데이트 작업이있을 때 레코드를 정렬하기위한 추가 노력이 필요합니다. 이로 인해 성능이 저하됩니다.데이터 추가 및 삭제가 잦은 경우 동적 해싱 성능이 좋습니다. 그러나 데이터베이스가 매우 크면 유지 관리 비용이 많이 듭니다.

정적 해싱은 레코드 크기 ID가 이전에 알려진 소규모 데이터베이스에 적합합니다. 데이터가 증가하면 버킷 오버플로와 같은 심각한 문제가 발생합니다.

삭제 / 업데이트 작업으로 인해 사용되지 않은 데이터 블록이 있습니다. 이러한 데이터 블록은 재사용을 위해 해제되지 않습니다. 따라서주기적인 메모리 유지 관리가 필요합니다. 그렇지 않으면 메모리가 낭비되고 성능도 저하됩니다. 또한 메모리를 유지하는 데 비용이 많이 듭니다.정적 및 동적 해싱 모두에서 메모리가 잘 관리됩니다. 버킷 오버플로도 정적 해싱에서 더 잘 처리됩니다. 데이터 블록은 동적 해싱에서 축소 및 증가하도록 설계되었습니다.

그러나 데이터베이스가 엄청나게 증가하면 동적 해싱에서 버킷 주소 테이블을 유지 관리하는 오버 헤드가 있습니다.

데이터 범위 검색에 선호됩니다. 즉, 특정 범위에 대한 검색 데이터가있을 때이 방법이 가장 적합합니다.이 방법은 검색 키를 기반으로 특정 레코드를 검색하는 데 적합합니다. 그러나 해시 기능이 검색 키에 없으면 더 나은 성능을 발휘하지 못합니다.