문제
해시함수는 보통 서로 다른 두 개의 키에 대해 동일한 해시값을 반환하는 해시충돌(collision)이 발생하게 된다.
충돌이 일어났을 때 해결하는 방법은 여러가지가 있지만, 그 중 폐쇄주소방식(Closed Addressing)은 해시테이블 내에서 키에 대한 해시값에 대응되는 곳에만 값을 저장하는 방식이다.
그러면 충돌이 난 데이터들이 같은 곳에 모여있게 되는데, 이를 구현하는 가장 대표적인 방법은 체이닝(Chaining)이다.
아래 코드는 아주 단순한 해시함수로 이번 문제에서 사용하면 된다.
def hash(key):
return key % M # M은 해시테이블 크기 키(key)값과 데이터를 입력받아 해시테이블에 저장시키는 프로그램을 작성하시오.
충돌이 일어난다면 주어진 해시함수를 사용하여 체이닝(Chaining)으로 충돌을 해결한다.
그리고 같은 key가 다른 데이터로 여러개 입력된다면 마지막 입력받은 데이터로 업데이트 시켜준다.
입력
첫 줄에 입력 할 값들의 수 N과 해시테이블 크기 M을 입력된다. (0 < N, M <= 50)
N줄에 거쳐 키(key)값(0 이상, 100 이하의 정수)과 데이터(-100 이상 100 이하의 정수나 실수 혹은 20길이 이하의 문자열)가 입력된다.
그 다음 줄에 질의의 수 Q가 입력된다. (1<= Q <=10)
이어서 Q줄에 거쳐 들어오는 key값에 해당하는 데이터가 입력된다. (-100 이상 100 이하의 정수)
출력
첫 M줄에 해시 테이블에 들어있는 데이터를 전부 출력예와 같이 출력한다. (비어있는 공간은 None으로 출력한다.)
그 후 Q줄에 거쳐 들어오는 key값에 해당하는 데이터를 출력한다.
예제 #1
14 6
1 A
3 B
5 C
8 D
10 E
12 F
13 G
16 H
17 I
18 J
19 K
20 L
21 M
22 N
4
3
5
10
16
0 : [18:J] [12:F]
1 : [19:K] [13:G] [1:A]
2 : [20:L] [8:D]
3 : [21:M] [3:B]
4 : [22:N] [16:H] [10:E]
5 : [17:I] [5:C]
B
C
E
H
예제 #2
0 1
1
0
0 :
None
로그인해야 코드를 작성할 수 있어요.