Hash function[해시 함수]

나무 위키를 참고 했습니다.

 

Hash function

임의의 길이를 같는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수.

보통 입력의 범위보다 출력의 범위가 작으므로 서로 다른 입력이 충돌이 일어날 수 있다.

그러나 해시는 키를 넣으면 바로 해시의 인덱스로 대응되며 검색과 저장의 평균적인 시간 복잡도가 $O(1)$에 수렴한다. 

따라서 빠른 검색과 저장이 가능하다.

 

해시함수, 개별 체이닝[Separate Chaining]방법[나무위키]

위와 같이 충돌이 일어났을 때 보통 두가지 방법을 사용한다. 충돌이 일어나면 연결 리스트로 연결[link]하는 개별 체이닝[Separate Chaining]방법과 충돌 시 다른 빈 공간을 찾아 저장하는 방법인 오픈 어드레싱[Open Addressing]방법이 있다.

 

파이썬에서 dictionary type으로 쓸 수 있다. 

또한, 파이썬 `collections`모듈의 `Counter`클래스로 쉽게 이용할 수 있다.

파이썬 collection모듈의 Counter 사용법 [EaleSeo]