해싱(Hashing)에 대한 퀴즈

버킷으로 구성된 기억공간

서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상

제산법(Division)

제곱법(Mid-Square)

폴딩법(Folding)

해싱은 해시 테이블을 사용하여 레코드를 저장하고 검색하는 방식입니다. 해시 함수를 사용하여 레코드 키에 대한 홈 주소를 계산하고 해당 기억장소에 레코드를 저장하거나 검색 작업을 수행합니다.

해시 테이블은 버킷들로 구성된 기억 공간입니다. 버킷은 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미합니다.

슬롯은 한 개의 레코드를 저장할 수 있는 공간으로, n개의 슬롯이 모여 하나의 버킷을 형성합니다.

충돌은 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상입니다.

Synonym은 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합입니다.

Overflow는 계산된 Home Address의 버킷 내에 저장할 기억공간이 없는 상태를 의미합니다.

해싱 함수는 레코드 키를 입력으로 받아 홈 주소를 계산하는 역할을 합니다.

해시 테이블의 크기는 충돌 현상의 발생 확률에 영향을 줍니다.

해시 함수는 레코드 키의 값을 해시 테이블 내의 홈 주소로 변환하는 역할을 합니다.

주기억장치에 구성할 경우 접근 시간이 빠르지만 용량이 제한되고 비용이 높을 수 있습니다. 보조기억장치에 구성할 경우 용량이 크고 비용이 낮지만 접근 시간이 느릴 수 있습니다.

레코드 키를 해시표의 크기보다 큰 수 중에서 가장 작은 소수로 나눈 나머지를 홈 주소로 삼는 방식입니다.

레코드 키 값을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식입니다.

레코드 키 값을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적논리합) 한 값을 홈 주소로 삼는 방식입니다.

키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고 이를 다시 주소 범위에 맞게 조정하는 방법입니다.

키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식입니다.

키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식입니다.

난수(Random Number)를 발생시켜 나온 값을 홈 주소로 삼는 방식입니다.

해시 테이블의 크기보다 큰 수 중에서 가장 작은 소수를 선택하면 충돌(Collision)을 최소화할 수 있기 때문입니다.

해시 함수에서는 서로 다른 레코드 키들이 같은 홈 주소를 가리킬 수 있기 때문에 충돌이 발생합니다.

해시 함수 선택 시 충돌 최소화, 해시 값의 균등 분포, 계산 효율성 등을 고려해야 합니다.