Hash-Collision

Collision Resolutions 해시 테이블(Hash Table)은 키(Key)를 해시 함수(Hash Function)에 적용하여 특정 인덱스(Index)에 데이터를 저장하는 자료구조이다. 그러나 서로 다른 키가 같은 해시 인덱스로 매핑되는 경우가 발생할 수 있으며, 이를 충돌(Collision) 이라고 한다. 해시 함수는 임의 크기의 데이터를 고정된 크기의 값으로 매핑한다. 해시 테이블의 크기가 제한되어 있기 때문에, 서로 다른 키들이 같은 해시 값(버킷 인덱스)을 가지는 ‘충돌’이 불가피하게 발생한다. 이는 ‘비둘기집 원리(Pigeonhole Principle)‘에 의해 증명된다 - 가능한 키의 수가 해시 테이블의 크기보다 크면 충돌은 반드시 발생한다. ...