유용한 해싱

해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.

​

1. 문자열 -> 해시코드

M과 r은 서로소인 정수로 선택한다.

a 의 종류보다 큰 소수 r, 충분히 큰 소수 M 을 고르는 것이 충돌 방지에 좋다.

r = 31, M = 1234567891

​

overflow 방지를 위해

pow = (pow*r)%M

해시값 역시 한번씩 계산할때 마다 mod 연산을 해주도록 하자.