질문이 있습니다 선생님!

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

위 이미지를 보던중 궁금한점이있습니다.

해시슬롯에 데이터셋을 바로 저장하는게 아니라 노드를 통해 계속 이어나가는 방식이 세퍼레이트 체이닝이라고 이해를 했습니다.(링크드 리스트)

그럼 이미지에서 해시테이블 슬롯에 저장되는 값은 링크드리스트의 헤드 포인터가 되는것인지 궁금합니다.

연결된 링크드리스트에 추가된다 에서 '연결된'이 어떤 의미인지 궁금해서요!

안녕하세요, 인프런 AI 인턴입니다. alopp님.

해시 테이블의 Separate Chaining에 대해 질문해 주셨네요. 질문 내용을 보면, 해시 슬롯에 데이터셋을 바로 저장하는 것이 아니라 노드를 통해 계속 이어나가는 방식에 대해 궁금해하시는 것 같습니다. 해당 방식은 맞게 이해하셨습니다. 해시 테이블 슬롯에는 실제 데이터가 아니라 링크드 리스트의 헤드 포인터가 저장됩니다.

이미지에서 ‘연결된 링크드리스트’라는 언급이 있는데, 이는 해당 슬롯에서 충돌이 발생한 경우, 동일한 인덱스에 데이터를 계속해서 추가하는 방식인 Separate Chaining을 의미합니다. 다시 말해, 해시 함수가 동일한 인덱스를 반환할 때마다 새로운 노드를 생성하여 링크드 리스트의 끝에 연결합니다.

추가적으로 비슷한 질문과 답변을 다른 게시글에서도 확인하실 수 있습니다. 아래 링크를 참조해 주세요:

여기에서 Separate Chaining과 Open Addressing을 비교하고, 각각의 구현 방식과 장단점에 대해 더 깊이 설명하고 있습니다. 예를 들어, Separate Chaining의 경우, 해시 충돌이 발생할 때마다 새로운 노드를 생성하여 링크드 리스트에 추가하는 방식을 사용하며, 해시 테이블 슬롯에는 링크드 리스트의 헤드 포인터가 저장된다고 볼 수 있습니다.

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

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