아스키함수, Hash함수 / 15829

오늘의 백준

15829 해시함수

 

 

개념

 

 

1. Chr , Ord 아스키함수

 

- ord('a')함수는 'a'의 아스키값인 97을 반환해준다.

- chr('a')함수는 해당 아스키값을 a문자열로 반환해준다.

 

 

 

 

2. 해시함수

 

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

 

- 해당 해시함수식은 해시충돌(중복)을 최대한 방지하도록 고안된 식이다.

 

- 해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다

 

- 여기서 마지막에 M의 나머지로 해시를 구함으로써, 해시값이 너무 커지는 것을 방지하고 범위를 제한할 수 있다.

-> 위 식에서 'r'은 M과 서로소인 숫자로 정하는 것이 일반적이다.  r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891로 설정.

 

 

# https://www.acmicpc.net/problem/15829
# 해시 함수

# 개념
# chr 함수와 ord 함수를 사용하여 아스키 값을 문자로 변환 : ord('A')는 'A'의 아스키 값(65)을 반환 / chr(A)는 해당 아스키값 '65'를 다시 문자열 A로 변환
# 이러한 해시함수식은 해시충돌(중복)을 방지한다.
# 최종 해시 값을 큰 소수 m으로 나누어 나머지를 취함으로써, 해시 값의 범위를 제한합니다. 이를 통해 값이 너무 커지는 것을 방지하고, 값의 균일한 분포를 유지합니다.

num =  input()
sentence = str(input())
t = 0
m = 1234567891
for idx, i in enumerate(sentence):
    a =  ord(i) - 96   # 96 = ord('a')-1
    t += a * (31**idx) # 해시함수식

print(t%m)