해시함수는 보통 서로 다른 두 개의 키에 대해 동일한 해시값을 반환하는 해시충돌(collision)이 발생하게 된다.

충돌이 일어났을 때 해결하는 방법은 여러가지가 있지만, 그 중 개방주소방식(Open Addressing)은 해시테이블 내에서 일정한 방식에 따라 비어있는 공간을 찾아 값을 저장하는 방식이다.

이러한 방식 중 선형조사(Linear Probing)을 이용하면 간단하게 해시충돌을 해결 할 수 있다.

다만 이때, 해시테이블의 키들이 뭉쳐있는 1차 군집화(Primary Clustering)이 일어나면 성능이 극단적으로 저하된다.

아래 코드는 아주 단순한 해시함수로 이번 문제에서 사용하면 된다.

def hash(key):
    return key % M    # M은 해시테이블 크기

M크기의 해시테이블을 생성하여 N개의 값을 저장하는 프로그램을 작성하시오.

이때, 해시함수는 위의 주어진 함수를 사용하고, 충돌이 일어난다면 선형조사(Linear Probing)로 충돌을 해결하자.

그리고 같은 key가 다른 데이터로 여러개 입력된다면 마지막 입력받은 데이터로 업데이트 시켜준다.

선형조사(Linear Probing) timer 1s memory 128MB

선형조사(Linear Probing) 1s 128MB