문제
해시함수는 보통 서로 다른 두 개의 키에 대해 동일한 해시값을 반환하는 해시충돌(collision)이 발생하게 된다.
충돌이 일어났을 때 해결하는 방법은 여러가지가 있지만, 그 중 개방주소방식(Open Addressing)은 해시테이블 내에서 일정한 방식에 따라 비어있는 공간을 찾아 값을 저장하는 방식이다.
이러한 방식 중 선형조사(Linear Probing)을 이용하면 간단하게 해시충돌을 해결 할 수 있다.
다만 이때, 해시테이블의 키들이 뭉쳐있는 1차 군집화(Primary Clustering)이 일어나면 성능이 극단적으로 저하된다.
아래 코드는 아주 단순한 해시함수로 이번 문제에서 사용하면 된다.
def hash(key):
return key % M # M은 해시테이블 크기M크기의 해시테이블을 생성하여 N개의 값을 저장하는 프로그램을 작성하시오.
이때, 해시함수는 위의 주어진 함수를 사용하고, 충돌이 일어난다면 선형조사(Linear Probing)로 충돌을 해결하자.
그리고 같은 key가 다른 데이터로 여러개 입력된다면 마지막 입력받은 데이터로 업데이트 시켜준다.
입력
첫 줄에 입력 할 데이터들의 수 N과 해시테이블 크기 M을 입력받고, (0 < N, M <= 50)
N줄에 거쳐 키(key)값(0 이상, 100 이하의 정수)과 데이터(-100 이상 100 이하의 정수나 실수 혹은 20길이 이하의 문자열)를 입력받는다.
그 다음 줄에 질의의 수 Q를 입력받고, (1<= Q <=10)
Q줄에 거쳐 key값을 입력받는다. (-100 이상 100 이하의 정수)
출력
첫 줄에 해시 테이블에 들어있는 데이터를 전부 한줄에 출력해라. (비어있는 공간은 None으로 출력한다.)
그 다음줄부터 Q줄에 거쳐 들어오는 key값에 해당하는 데이터를 출력하자.
예제 #1
8 13
25 apple
35 banana
5 cherry
39 mango
19 lime
22 orange
63 watermelon
11 grape
4
25
5
19
22
mango grape None None None cherry lime None None banana orange watermelon apple
apple
cherry
lime
orange
예제 #2
8 5
3 apple
8 banana
5 cherry
1 mango
5 lime
15 orange
63 watermelon
11 grape
4
3
5
15
12
lime mango orange apple banana
apple
lime
orange
None
로그인해야 코드를 작성할 수 있어요.