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

충돌이 일어났을 때 해결하는 방법은 여러가지가 있지만, 그 중 폐쇄주소방식(Closed Addressing)은 해시테이블 내에서 키에 대한 해시값에 대응되는 곳에만 값을 저장하는 방식이다.

그러면 충돌이 난 데이터들이 같은 곳에 모여있게 되는데, 이를 구현하는 가장 대표적인 방법은 체이닝(Chaining)이다.

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

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

키(key)값과 데이터를 입력받아 해시테이블에 저장시키는 프로그램을 작성하시오.

충돌이 일어난다면 주어진 해시함수를 사용하여 체이닝(Chaining)으로 충돌을 해결한다.

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

체이닝(Chaining) timer 1s memory 128MB

체이닝(Chaining) 1s 128MB