인프런 커뮤니티 질문&답변

안녕하세요 세일님!! 좋은 질문 넘넘 감사합니다!!

질문하신 내용을 보면, 해시 충돌 해결을 위해 링크드 리스트 대신 내부적으로 해시 테이블을 또 사용하는 방식을 제안하셨는데요, 이를 실제로 구현하지 않는 이유를 함께 살펴보겠습니다.

1. 시간 복잡도의 차이

해시 테이블 내부에서 또 다른 해시 테이블을 사용하는 경우, 이론적으로는 각 충돌 체인의 검색 시간 복잡도가 O(1)로 줄어들 수 있습니다.
하지만 이 O(1)은 "해시 함수가 완벽히 동작하고 충돌이 전혀 없는 경우"에만 성립합니다. 현실적인 시스템에서는:

• 내부 해시 테이블에서도 충돌이 발생할 가능성이 있으며, 충돌을 해결해야 하므로 시간 복잡도가 O(1) * O(1)로 단순히 떨어지지 않습니다.

• 충돌 발생 시 다시 충돌 해결 전략(체이닝, 오픈 어드레싱 등)을 도입해야 하므로 복잡성이 증가할 수 있습니다.

2. 공간 효율성 문제

해시 테이블을 또 사용하는 방식은 다음과 같은 문제가 있습니다:

• 각 슬롯마다 새로운 해시 테이블을 생성하면 메모리 사용량이 급격히 증가합니다.

• 특히, 충돌이 적은 경우에도 불필요한 해시 테이블이 생성되어 공간 낭비가 발생합니다.

• 링크드 리스트는 간단히 메모리를 동적으로 할당하여 필요한 만큼만 사용하므로 공간 효율성이 훨씬 높습니다.

3. 구현 복잡성

해시 테이블 내부에 또 해시 테이블을 사용하면:

• 이중 해시 함수 설계가 필요합니다.

  • 외부 해시 테이블과 내부 해시 테이블이 각각 다른 해시 함수를 사용해야 합니다.

  • 이를 설계하고 관리하는 비용이 추가됩니다.

• 링크드 리스트는 단순히 노드를 연결하기만 하면 되지만, 이중 해시 테이블 구조는 더 복잡한 로직이 요구됩니다.

4. 실제 성능 차이

링크드 리스트를 사용하는 체이닝 방식은 충돌이 적은 경우 성능이 매우 뛰어나며, 충돌이 많아지는 경우에도 구현과 관리가 상대적으로 간단합니다.
반면, 내부에 해시 테이블을 사용하면 충돌이 많아질 경우 해시 충돌 해결 전략 자체가 다시 성능 병목이 될 수 있습니다.

결론

링크드 리스트를 사용하는 체이닝 방식은:

• 충돌 해결을 위한 간단하고 효율적인 방법입니다.

• 메모리 사용량을 최소화하면서 구현 복잡성을 낮추는 데 적합합니다.

해시 테이블 내부에 또 다른 해시 테이블을 사용하는 방법은 이론적으로 흥미로운 접근이지만, 메모리 사용량과 구현 복잡성, 충돌 가능성 등의 현실적인 문제 때문에 일반적으로 사용되지 않습니다.

좋은 질문 덕분에 저도 다시 한 번 생각해볼 기회를 가졌습니다! 추가적인 궁금증이 생기시면 언제든 편하게 질문 주세요