■ 해슁 (hashing)
주어진 키 값을 이용하여 레코드가 저장될 위치를 계산하고 계산된 주소로 직접 테이블을 참조하는 key-to-address 형태로 해당 레코드를 탐색하거나 삽입 삭제 등의 연산을 수행하는 것.

 

| 해쉬의 개요 | 해슁 개념해쉬 함수와 충돌 해소 |

 

해쉬(Hash)의 개요

■ 용어 해설
    - 해쉬 함수 : 키 값을 0 ~ (Table_Size-1)로 변환하는 함수
    - 해쉬 테이블 : 키 값을 저장하게 될 고정 된 크기의 배열
    - 테이블 사이즈 : 소수 (prime number)이어야 한다.

■ 해쉬 함수의 개념
    - 해쉬 테이블에 키 값을 주소로 변환하는 데 사용되는 함수
    - 빠르고 서로 다른 키 값이 같은 주소로 산출되지 않아야 함.
    - 나눗셈법, 중간제곱법, 폴딩법, 기수변환법, 자릿수 분석법 등
    - 키의 분포를 모르는 경우 나눗셈법이 가장 좋다.
    - 키 값은 string인 경우가 많음, ASCII 코드 사용 정수로 변환

■ 해쉬 함수의 종류
    - 나눗셈법 : H(X) = X mod Table_Size, X = 키 값
    - 중간제곱법 : 키 값을 제곱하여 일부 중간 값을 취함.
                          K = 7632, K2 = 58247424, 주소 : 2474