해시 테이블(Hash Table)에서 해시 충돌(Hash Collision)이 발생했을 때 이를 해결하는 대표적인 방법 두 가지를 설명하고, 각각의 장단점을 비교해주세요.

해시 테이블에서 해시 충돌을 해결하는 대표적인 방법은 체이닝(Chaining)과 오픈 어드레싱(Open Addressing)이 있습니다.

체이닝은 각 해시 값에 연결 리스트를 연결하여 충돌이 발생하면 해당 리스트에 새로운 노드를 추가하는 방식입니다. 장점은 구현이 비교적 간단하고 삭제가 용이하며, 테이블이 꽉 차더라도 어느 정도 성능을 유지할 수 있다는 점입니다. 단점은 연결 리스트를 위한 추가적인 메모리 공간이 필요하고, 최악의 경우 탐색 시간이 O(n)까지 늘어날 수 있다는 것입니다.

오픈 어드레싱은 충돌이 발생하면 미리 정해진 규칙에 따라 해시 테이블 내의 다른 빈 슬롯을 찾아 데이터를 저장하는 방식입니다. 선형 탐사, 이차 탐사, 이중 해싱 등이 있습니다. 장점은 추가적인 메모리 오버헤드가 없다는 점입니다. 단점은 테이블이 꽉 찰수록 성능이 급격히 저하될 수 있고, 특히 선형 탐사의 경우 클러스터링 문제가 발생하여 탐색 효율이 떨어질 수 있습니다.