데이터베이스-해싱(Hashing)

1. 해싱(Hashing)의 개요

 1-1. 해싱(Hashing)의 정의

   - 자료검색을 위해 해시 함수를 활용하여 키값을 해당 항목의 정보로 직접 바꿔서 검색하는 방법.

   - 해싱함수: 임의의 길이를 가지는 메시지를 고정된 길이의 출력값으로 바꿔주는 함수

 

 1-2. 해싱(Hashing)의 특징

   - 고속성 키 값에 해당하는 주소로 직접 접근하므로 고속 처리 가능

   - 사상함수 “<키 값 → 주소>” 사상함수(Mapping Function)의 접근으로 레코드 검색

   - 단방향성 출력된 값을 역으로 추적이 불가능

 

2. 해싱(Hashing)의 개념도, 구성요소

 2-1.  해싱(Hashing)의 개념도

 

 2-2. 해싱(Hashing)의 구성요소

   1) 해싱함수 – 해시 테이블의 주소를 생성해 내는 함수(수식 계산법)

   2) 해쉬테이블 – 해시함수에 의해 참조되는 테이블

   3) 버킷 – 하나의 주소를 갖는 파일의 한구역

   4) 슬롯 – n 개의 슬롯이 모여서 버킷을 형성

   5) 동거자(synonym) – 같은 주소를 갖는 레코드들의 집합

  6) 충돌(Collision) – 서로 다른 2개이상의 레코드가 같은 주소를 갖는 현상

  7) 오버플로우(Overflow) – 버킷내의 슬롯공간(기억공간)이 없는 현상