공갱의유용한자료실

3장. Hashing(3) (1) 충돌 해결 기법의 개요 ① 충돌(collision)이란? 󢐠충돌(collision) : 어떠한 레코드를 파일에 저장하기 위해 주소를 계산하여 넣으려고 하는데, 이미 그 자리에 다른 레코드가 저장되어 있는 경우 → 그 레코드를 저장하기 위한 다른 곳을 결정 → 레코드를 검색할 때 자신의 홈 어드레스에 있지 않으므로, 옮겨 간 위치를 찾을 수 있도록 해야 한다. ② 충돌 해결 방법의 종류 󢐠개방주소법(open addressing) ▹ 오버플로된 레코드가 저장될 위치를 결정하는 규칙을 정의하여 이 규칙에 따라 레코드를 저장하고 검색하는 방법 󢐠체인법(chaining) ▹ 오버플로 된 레코드가 저장된 위치를 포인터로 연결하는 방법 (2) 개방주소법(Open addressing)..

2. 직접파일의 설계 요소 주소를 지정하여 원하는 레코드를 직접접근 할 수 있도록 하려면 레코드의 주소를 결정하는 것뿐만 아니라 앞 절에서 언급한 충돌 문제 등을 고려하여 효율적으로 데이터를 액세스할 수 있도록 하기 위한 몇 가지 설계 요소가 필요합니다. 여기에서는 직접파일을 구현하기 위해서 설계해야 할 내용은 어떤 것들이 있는지 생각해 봅시다 ⑴ 충돌과 직접파일의 성능 충돌이 발생하면 레코드를 홈 어드레스에 넣지 못하므로 그 주소의 기억공간에서 오버플로가 발생하게 된다. 이 경우 저장하지 못한 레코드를 다른 대체 저장 위치에 저장해야 한다. 이 과정에서 파일 액세스 횟수가 증가한다. 그러므로 오버플로를 최대한 줄이는 것이 필요하다. ① 주소공간의 균일한 활용 → 주소를 계산하는 함수의 결과가 일부 주소..

1. Hashing(1) 1. 직접파일의 개념 직접파일은 레코드의 주소를 이용하여 원하는 레코드를 직접접근 하는 파일입니다. 여기에서는 우선 어떻게 주소를 결정할 수 있고, 그 과정에서 발생할 수 있는 문제점은 무엇인지 생각해 봅시다. ⑴ 키를 이용하여 레코드를 액세스하는 방법 ① 함수 계산에 의한 방법 → 키를 정해진 함수에 입력하여 주소를 계산한다. ② 인덱스를 사용하는 방 → 인덱스 내에서 액세스하려는 키 값에 대한 항목을 검색하여 액세스할 데이터 파일의 주소를 찾는다. → 인덱스 : 키 값과 해당 키 값을 갖는 레코드가 저장된 주소를 모아 놓은 자료구조 ※ 함수 계산 방법은 인덱스를 사용하는 방법과는 달리 레코드의 주소를 구하기 위해 별도의 파일을 액세스 하지 않는 이점이 있어 직접파일은 함수 계..