해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정의한다. 해시 함수는 무궁무진한 응용 분야를 갖는데, 대표적으로 자료의 저장과 탐색에 쓰인다.
1. 문자열 -> 해시코드
M과 r은 서로소인 정수로 선택한다.
a 의 종류보다 큰 소수 r, 충분히 큰 소수 M 을 고르는 것이 충돌 방지에 좋다.
r = 31, M = 1234567891
overflow 방지를 위해
pow = (pow*r)%M
해시값 역시 한번씩 계산할때 마다 mod 연산을 해주도록 하자.
'Algorithem' 카테고리의 다른 글
| 트리 (0) | 2023.01.06 |
|---|---|
| 실시간으로 변하는 경우 heap으로 중앙값 찾기 (0) | 2023.01.06 |
| 트리의 지름 구하기 : 단 두번의 dfs 탐색 (0) | 2023.01.06 |
| 트리의 두번째 지름 : 지름 구하기 3번으로 (0) | 2023.01.06 |
| 수학 : 최대공약수와 최소공배수, 소수 구하기 (0) | 2023.01.06 |
