영어-한국어 사전을 해싱을 이용하여 구현하려고 한다.

배열 기반 해시 테이블을 만들고, 문자열 key를 이용하여 데이터를 삽입하고 검색하는 프로그램을 작성하시오.

해시 테이블 클래스의 이름은 HashTable로 한다.

다음 이름의 함수들을 구현해야 한다.

• 생성자
• hash_function
• insert
• search

1. 생성자

해시 테이블의 크기를 저장하고, 크기가 M인 배열 기반 테이블을 생성한다.

빈 슬롯은 비어 있음을 나타내는 값으로 표현한다. (예: Python의 None, Java의 null, C++의 nullptr)

또한 다음 정보를 관리해야 한다.

• 현재 저장된 데이터 개수
• 전체 충돌 횟수

2. 해시 함수

문자열 key의 해시값은 다음 방식으로 계산한다.

초기 해시값 h는 0이다.

문자열의 각 문자 ch에 대해 다음 연산을 수행한다.

h = (h * 31 + ord(ch)) mod M

ord(ch)는 문자 ch의 아스키 코드 값이다.

여기서 M은 해시 테이블의 크기이다.

최종적으로 계산된 h를 반환한다.

3. 삽입 함수

삽입 함수는 key와 value를 받아 해시 테이블에 저장한다.

데이터는 key와 value를 한 쌍으로 저장한다.

먼저 해시 함수를 이용하여 기본 해시값 h를 구한다.

해당 위치가 비어 있으면 바로 저장한다.

이미 다른 데이터가 저장되어 있다면 충돌로 처리하고, 이차 조사법을 사용하여 다음 위치를 탐색한다.

이차 조사법의 탐사 위치는 다음과 같다.

(h + i^2) mod M

여기서 i는 0부터 시작한다.

충돌이 발생하면 빈 슬롯을 찾을 때까지 탐사를 반복한다.

빈 슬롯을 찾으면 데이터를 저장하고 저장된 데이터 개수를 1 증가시킨다.

삽입 연산마다 다음 형식으로 출력한다.

[INSERT] `key` `value`
h(`key`) = X
collision X   (충돌 발생 시)
stored X

• X : index 또는 해시값

4. 검색 함수

검색 함수는 key를 받아 해당 key에 대응하는 value를 찾는다.

검색도 삽입과 동일한 해시 함수와 이차 조사법을 사용해야 한다.

탐색 중 현재 위치에 저장된 key가 찾는 key와 다르면 충돌로 처리한다.

빈 슬롯을 만나면 검색 실패이다.

key가 일치하는 데이터를 찾으면 검색 성공이다.

검색 과정에서 확인한 슬롯의 개수를 총 탐색 횟수로 계산한다.

검색 연산마다 다음 형식으로 출력한다.

[SEARCH] `key`
h(`key`) = X
collision X   (충돌 발생 시)
X VALUE       (검색 성공 시)
-1            (검색 실패 시)
total K

• X : index 또는 해시값
• VALUE : 검색된 value
• K : 검색 과정에서 확인한 슬롯 수

각 연산의 출력이 끝나면 빈 줄을 하나 출력한다.

입력 설명

첫째 줄에 해시 테이블의 크기 M이 주어진다.

둘째 줄에 삽입할 데이터의 개수 N이 주어진다.

다음 N개의 줄에 영어 단어 key와 한국어 단어 value가 공백으로 구분되어 주어진다.

그 다음 줄에 검색할 key의 개수 Q가 주어진다.

다음 Q개의 줄에 검색할 key가 한 줄에 하나씩 주어진다.

출력 설명

각 연산의 출력 결과를 출력한다.

마지막 줄에 전체 충돌 수를 total_collision C 형식으로 출력한다.

Notes

• 입력되는 key는 중복되지 않는다.
• 해시 테이블이 가득 차는 경우는 주어지지 않는다.
• key와 value는 공백을 포함하지 않는다.

예제 입력 1

11
7
no 아니오
on 위에
ton 톤
not 아니다
apple 사과
grape 포도
melon 멜론
4
ton
not
grape
pear

예제 출력 1

[INSERT] no 아니오
h(no) = 1
stored 1

[INSERT] on 위에
h(on) = 9
stored 9

[INSERT] ton 톤
h(ton) = 0
stored 0

[INSERT] not 아니다
h(not) = 4
stored 4

[INSERT] apple 사과
h(apple) = 10
stored 10

[INSERT] grape 포도
h(grape) = 0
collision 0
collision 1
collision 4
collision 9
stored 5

[INSERT] melon 멜론
h(melon) = 2
stored 2

[SEARCH] ton
h(ton) = 0
0 톤
total 1

[SEARCH] not
h(not) = 4
4 아니다
total 1

[SEARCH] grape
h(grape) = 0
collision 0
collision 1
collision 4
collision 9
5 포도
total 5

[SEARCH] pear
h(pear) = 0
collision 0
collision 1
collision 4
collision 9
collision 5
-1
total 6

total_collision 13

예제 입력 2

13
8
cat 고양이
act 행동
tac 택
dog 개
god 신
apple 사과
banana 바나나
zebra 얼룩말
4
tac
god
banana
orange

예제 출력 2

[INSERT] cat 고양이
h(cat) = 8
stored 8

[INSERT] act 행동
h(act) = 7
stored 7

[INSERT] tac 택
h(tac) = 0
stored 0

[INSERT] dog 개
h(dog) = 12
stored 12

[INSERT] god 신
h(god) = 6
stored 6

[INSERT] apple 사과
h(apple) = 1
stored 1

[INSERT] banana 바나나
h(banana) = 2
stored 2

[INSERT] zebra 얼룩말
h(zebra) = 4
stored 4

[SEARCH] tac
h(tac) = 0
0 택
total 1

[SEARCH] god
h(god) = 6
6 신
total 1

[SEARCH] banana
h(banana) = 2
2 바나나
total 1

[SEARCH] orange
h(orange) = 1
collision 1
collision 2
-1
total 3

total_collision 2