해싱(Hashing)

해싱(Hashing)

• 해싱은 데이터를 해싱 함수에 의해 주소로 변환해 해당 주소 위치에 데이터를 저장하는 방식입니다.(key-value 방식)
• 데이터 검색시 빠르게 찾을 수 있는 장점이 있는 반면, 해시 테이블 용량 부족으로 오버플로우가 발생 가능합니다.

용어 정리

• 해시 함수 : 데이터를 키로 변환하는 함수
• 홈 주소 : 해시 함수로 변환된 키 값의 주소
• 해시 테이블 : 해시 함수가 키 값 변환시 참조하는 테이블
• 버킷 : 하나의 주소를 갖는 구역, 버킷의 크기는 레코드 몇개 들어갈 수 있는가를 의미
• 슬롯 : 하나의 데이터를 저장할 수 있는 공간, 하나의 버킷안에 여러개의 슬롯을 가짐
• 충돌 : 다른 데이터가 같은 키를 가지는 충돌 현상
• 동의어 : 동일한 홈 주소로 인하여 충돌이 일어난 레코드들의 집합
• 오버플로우 : 하나의 홈 주소의 버킷이 가득 차서 레코드를 저장할 슬롯이 없는 상태

해시 함수 종류

• 제산함수

 - 레코드 값을 소수로 나누어 나머지 값을 주소로 지정

 - ex) h(k) = k%7

• 중간제곱함수

 - 레코드 값을 제곱한 후에 중간 몇자리를 선택하여 주소로 지정

 - ex) k = 1024일 때, 1024*1024 = 1048576인데, 중간의 485가 주소로 지정

• 접지함수

 - 숫자로 된 키를 같은 크기로 분리 후, 각 부분들 서로 더해서 주소로 지정

 - 이동 접지 : k = 12320324111220일 때, 123+203+241+112+20= 699가 주소로 지정

 - 경계접지 : k = 12320324111220일 때, 123+302+241+211+20= 897이 주소로 지정

• 숫자분석함수

 - 각 숫자의 분포를 이용해 편향되지 않은 균등된 숫자를 선택해 주소로 지정

오버플로우 처리 방법

• 선형조사법 : 오버플로우가 발생 시 다음 버킷에 빈 슬롯이 있으면 저장하는 방법
• 이차조사법 : 선형조사법의 편향을 방지하기 위해 오버플로우 발생시 n^2의 +-씩으로 검사하여 저장하는 방법
• 재해싱 : 여러 개의 해시함수를 사용하는 방법
• 임의 조사법