Hashing

정의

- 해싱 함수를 이용하여 자료를 검색하는 방법.

- 데이터를 해시 테이블이라는 배열에 저장하고, 키 값과 해싱 함수를 이용한 결과값인 주소를 통해 데이터를 신속하게 찾는 방법.

- 키-주소 변환 방법

용어

• 해싱 함수 : 해시 테이블의 주소를 생성해 내는 함수
• 해시 테이블 : 해싱 함수에 의하여 참조되는 테이블
• 버킷(Bucket) : 하나의 주소를 갖는 파일의 한 구역
• 슬롯(Slot) : n개의 슬롯이 모여 하나의 버킷을 형성
• 충돌(Collision) : 서로 다른 2개 이상의 레코드가 같은 주소를 갖는 현상
• 시노임(Synonym) : 같은 주소를 갖는 레코드의 집합
• Overflow : 버킷 내에 메모리 공간이 없는 현상

해싱 함수

1. 기수(Radix) 법
   - 키 값을 다른 진법으로 변환.
   
   
2. 폴딩(Folding) 법
   - 키 값을 여러 부분으로 등분하고 각 부분을 + 하거나 XOR한 값으로 변환
   
   
3. 제산(Division) 법
   - 키 값을 어떤 정수 값으로 나누고 나머지값으로 변환
   
   
4. 중간제곱(Mid-square) 법
   - 키 값을 제곱하고 중간 n자리로 변환
   
   
5. 숫자분석법
   - 키 값에 의한 표를 만들고 각 숫자별로 빈도수를 표시하여 균등한 분포를 가지는 자릿수를 주소로 사용

Overflow 해결 방법

1. 개방 주소법
   - 해당 버킷에 이미 값이 있을 경우 빈 버킷을 찾아 저장
   
   
2. 폐쇄 주소법 (체인법)
   - 오버플로우된 레코드들을 해당 버킷에 연결하여 별도로 저장
   
   
3. 재해싱법
   - 새로운 해싱함수를 적용하여 다시