[CS][알고리즘] 해시 함수

해시 함수란?

• 데이터를 키로 변환하는 함수
• 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑

해싱 함수 종류

제산법(Division)

• 나머지 연산자(%)를 사용하여 테이블 주소를 계산

제곱법(Mid Square)

• 레코드 키 값을 제곱한 후, 결괏값의 중간 부분에 있는 몇 비트를 선택하여 해시 테이블의 홈 주소로 사용하는 방식

숫자 분석법(Digit Analysis)

• 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 선택해 홈 주소로 사용하는 방식

폴딩법(Folding)

• 레코드키 키를 여러 부분으로 나누고, 나눈 부분의 각 숫자를 더하거나 XOR 한 값을 홈 주소로 사용하는 방식

기수 변환법(Radix Conversion)

• 레코드키의 진법을 다른 진법으로 간주하고 키를 변환하여 홈 주소를 얻는 방식

무작위 방법(Random)

• 난수를 발생시켜 레코드 키의 홈 주소를 결정하는 방식

복잡도

• O(1) : 상수형 복잡도
• 자료 크기와 무관하게 항상 같은 속도로 작동
• 알고리즘 수행 시간이 입력 데이터 수와 관계없이 일정

고려할 점

• 계산과정의 단순화
• 충돌의 최소화
• 기억장소 낭비의 최소화
• 오버플로우의 최소화