[알고리즘] 해쉬 테이블(hash table) - 오버플로 체인(overflow chaining)

해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있다.

이를 충돌(collision)이라고 부른다.

충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있다.

 체인을 이용하는 방법은 충돌이 발생한 지점에 포인터로 링크드리스트와 같이 연결하는 것이다. 

 

아래는 오버플로 체이닝의 예이다.