#  백준BOJ/Python : 15829번 : Hashing(해시 함수)

- Author: @laetipark
- Published: 2024-01-04
- Updated: 2024-01-04
- Source: http://blex.me/@laetipark/%EB%B0%B1%EC%A4%80bojpython-15829%EB%B2%88-hashing%ED%95%B4%EC%8B%9C-%ED%95%A8%EC%88%98
- Tags: python, algorithm, 구현, 백준, 문자열, boj, baekjoon, 해싱

---

[15829번 : Hashing 원본](https://www.acmicpc.net/problem/15829)

### 알고리즘 분류
- 구현
- 문자열
- 해싱

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

이 문제에서는 여러분이 앞으로 유용하게 쓸 수 있는 해시 함수를 하나 가르쳐주고자 한다. 먼저, 편의상 입력으로 들어오는 문자열에는 영문 소문자(a, b, ..., z)로만 구성되어있다고 가정하자. 영어에는 총 26개의 알파벳이 존재하므로 a에는 1, b에는 2, c에는 3, ..., z에는 26으로 고유한 번호를 부여할 수 있다. 결과적으로 우리는 하나의 문자열을 수열로 변환할 수 있다. 예를 들어서 문자열 "abba"은 수열 1, 2, 2, 1로 나타낼 수 있다.

해시 값을 계산하기 위해서 우리는 문자열 혹은 수열을 하나의 정수로 치환하려고 한다. 간단하게는 수열의 값을 모두 더할 수도 있다. 해시 함수의 정의에서 유한한 범위의 출력을 가져야 한다고 했으니까 적당히 큰 수 M으로 나눠주자. 짜잔! 해시 함수가 완성되었다. 이를 수식으로 표현하면 아래와 같다.

![](https://static.blex.me/images/content/2024/1/4/2024141_hpzpXKzwneFHUsPOmRXL.png)

해시 함수의 입력으로 들어올 수 있는 문자열의 종류는 무한하지만 출력 범위는 정해져있다. 다들 비둘기 집의 원리에 대해서는 한 번쯤 들어봤을 것이다. 그 원리에 의하면 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. 이를 해시 충돌이라고 하는데, 좋은 해시 함수는 최대한 충돌이 적게 일어나야 한다. 위에서 정의한 해시 함수는 알파벳의 순서만 바꿔도 충돌이 일어나기 때문에 나쁜 해시 함수이다. 그러니까 조금 더 개선해보자.

어떻게 하면 순서가 달라졌을때 출력값도 달라지게 할 수 있을까? 머리를 굴리면 수열의 각 항마다 고유한 계수를 부여하면 된다는 아이디어를 생각해볼 수 있다. 가장 대표적인 방법은 `항의 번호에 해당하는 만큼 특정한 숫자를 거듭제곱해서 곱해준 다음 더하는 것`이 있다. 이를 수식으로 표현하면 아래와 같다.

![](https://static.blex.me/images/content/2024/1/4/2024141_nkf71lcwwnVcyIj8DD7C.png)

보통 r과 M은 서로소인 숫자로 정하는 것이 일반적이다. 우리가 직접 정하라고 하면 힘들테니까 r의 값은 26보다 큰 소수인 31로 하고 M의 값은 1234567891(놀랍게도 소수이다!)로 하자.

이제 여러분이 할 일은 위 식을 통해 주어진 문자열의 해시 값을 계산하는 것이다. 그리고 이 함수는 간단해 보여도 자주 쓰이니까 기억해뒀다가 잘 써먹도록 하자.

### 입력
첫 줄에는 문자열의 길이 L이 들어온다. 둘째 줄에는 영문 소문자로만 이루어진 문자열이 들어온다.
입력으로 주어지는 문자열은 모두 알파벳 소문자로만 구성되어 있다.

### 출력
문제에서 주어진 해시함수와 입력으로 주어진 문자열을 사용해 계산한 해시 값을 정수로 출력한다.

### 풀이
a부터 z까지 `아스키 코드 키`를 갖는 `딕셔너리(dictionary)`에 각각 `1부터 26까지` 값을 넣어, `31^i`만큼 곱해준 것의 합계를 `1234567891`으로 나눈 나머지를 출력하면 된다.

#### 해시 함수와 해시 테이블

![https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98#/media/%ED%8C%8C%EC%9D%BC:Hash_table_4_1_1_0_0_1_0_LL.svg](https://static.blex.me/images/content/2024/1/4/2024144_LyDBijL37Ykz0xBOUI4D.png)
`해시 함수`란 `임의의 길이 데이터`, `message`를 `고정의 길이 데이터`인 `hash value`, `hash code`, `digest` 또는 `hash`로 매핑하는 함수이다.

![https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94](https://static.blex.me/images/content/2024/1/4/2024144_LyDBijL37Ykz0xBOUI4D.png)
`해시 테이블`은 `해시 함수`를 이용하여, `키(key)`와 `값(value)`을 매핑한 자료 구조로 해시 함수를 적용하여 값을 `bucket`에 저장하거나 검색할 수 있다.

`해시 테이블`의 경우 시간 복잡도가 `O(1)`으로 `python`의 `dictionary`의 경우 대표적인 해시 테이블이다.

### 소스 코드
##### Python
```python
L = int(input())
string = input()

dic = {}
for i in range(26):
    dic[97 + i] = i + 1
sum = 0

for i in range(L):
    sum += (dic[ord(string[i])]) * (31 ** i)

print(sum % 1234567891)
```