해시 충돌 구현 링크드리스트 사용이유!

학습하는 분들께 도움이 되고, 더 좋은 답변을 드릴 수 있도록 질문전에 다음을 꼭 확인해주세요.

1. 강의 내용과 관련된 질문을 남겨주세요.
2. 인프런의 질문 게시판과 자주 하는 질문(링크)을 먼저 확인해주세요.
(자주 하는 질문 링크: https://bit.ly/3fX6ygx)
3. 질문 잘하기 메뉴얼(링크)을 먼저 읽어주세요.
(질문 잘하기 메뉴얼 링크: https://bit.ly/2UfeqCG)

질문 시에는 위 내용은 삭제하고 다음 내용을 남겨주세요.
=========================================
[질문 템플릿]
1. 강의 내용과 관련된 질문인가요? (예/아니오)
2. 인프런의 질문 게시판과 자주 하는 질문에 없는 내용인가요? (예/아니오)
3. 질문 잘하기 메뉴얼을 읽어보셨나요? (예/아니오)

[질문 내용]
안녕하세요! 강사님께서 링크드 리스트를 사용하시는 이유를 설명해주셨는데 잘 이해가 안가서 질문을합니다!

어레일이스트를 사용하는것보다 링크드 리스트를 사용하는 이유가.. 충돌?이 덜나서라고 하셨는데 이부분을 자세하게 설명해주실수있나요? 잘 이해가 안가네요 ㅜㅜ

안녕하세요, 인프런 AI 인턴입니다. 냠냠냠님의 질문은 해시 테이블 구현에 있어서 왜 링크드 리스트(LinkedList)가 배열(Array)이나 동적 배열(ArrayList) 대신 사용되는지에 대한 궁금증을 담고 있습니다. 여기서 말하는 ‘충돌’이란 해시 테이블에서 두 개 이상의 엔트리가 동일한 해시 값을 가지게 되는 상황을 말합니다. 이 때 발생하는 충돌을 처리하는 데 링크드 리스트가 효과적이라는 설명에 대해 더 알아보고자 하는 것 같습니다.

질문과 직접적으로 관련이 있는 정보로, “6강 해시 충돌 구현”에 대한 질문이 있었습니다. 해당 질문에서 사용자는 해시 테이블에서 LinkedList를 전체 버킷의 컨테이너로 사용한 이유에 대해 궁금해 하였고, 공식 서포터즈 David이 답변을 통해 강사님께서 3분 2초부터 LinkedList 사용 이유에 대해 설명하고 있음을 안내하였습니다.

해시 테이블의 버킷에 데이터를 저장할 때 충돌이 발생할 가능성이 있습니다. 각각의 버킷에는 연결된 리스트를 사용해서 여러 개의 엔트리를 저장할 수 있게 만들어 충돌을 관리합니다. 링크드 리스트를 사용하는 핵심 이유는 충돌이 발생했을 때 새로운 엘리먼트를 쉽게 추가할 수 있기 때문입니다. 또한, 링크드 리스트는 엘리먼트가 메모리 상에 연속적으로 위치할 필요가 없어, 동적으로 데이터를 추가하거나 제거할 때 높은 유연성을 제공합니다.

반면에, ArrayList를 사용할 경우 내부 배열을 재구성해야 하는 비용이 발생할 수 있습니다. 특히, 버킷의 용량을 넘어설 때마다 크기를 확장하기 위해 전체 배열을 새로운 배열로 복사해야 하는 비용이 들 수 있습니다. 이러한 이유로 해시 테이블 구현에 있어 LinkedList가 선호될 수 있습니다.

해시 충돌 구현 관련 질문에서 더 자세한 설명을 찾아보시면 도움이 될 것 같습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

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