인프런 커뮤니티 질문&답변
작성한 질문수
hash table의 seperate chaining 질문
작성
·
287
·
수정됨
0
안녕하세요 우선 좋은 강의 만들어주셔서 감사합니다!
hash table의 seperate chaining 부분을 수강하다 질문이 생겨서 남깁니다.
제가 이해한 바로는, 'hash table의 collision 상황을 해결하기 위해 크게 open addressing, seperate chaining 두 가지가 있는데, open addressing은 기존 table 내에서 공간을 탐색해서 저장하는 방식이고, seperate chaining은 linked-list를 통해 동일한 index에서 다음 node에 데이터를 저장한다.' 라고 정리할 수 있을 것 같습니다.
제가 궁금한 사항은
1) open addressing과 seperate chaining을 비교했을 때, 애초에 collision이 발생하기 전부터 (key, value)를 저장하는 방식이 다른 건가? (hash table을 구현하는 방식이 array와 linked-list 로 나누어져 있는 건가요?)
2) 그렇다면 같은 hash table에서 open addressing으로 collision을 해결하다가 seperate chaining으로 collision을 해결할 수 있는가?
3) hash table을 초기에 선언할 때 collsion 해결 방식을 한 가지만 채택해야 하는가?
입니다!
고생 많으십니다!
답변 2
1
1
안녕하세요 욱님! 해시테이블에대해서 정확히 이해하셨네요~
깊게 공부하시다보니 해당 질문에까지 다다른 것 같아 대단하게 생각합니다!
언어에서 어떤식으로 해시테이블을 구현할건지 먼저 정합니다. 이에따라 충돌이 발생할 때 어떤 방식으로 이를 해결할지 미리 정합니다.
따라서 한 언어에서 채택한 해시테이블구현 방식은 한번 정해지면 그걸 쓰게 됩니다.
여러 방식을 쓰는 이점이 딱히 없어서 하나를 채택하여 쭉 씁니다. 물론 두 방식을 합쳐서 쓰는 하이브리드형이 여러면에서 장점이 더 많다는 것을 누가 제안하고 합의가 이뤄진다면 하이브리드로 쓸 수도 있을 것같네요!
더 궁금한점이 있으시다면 언제든 질문주세요! 화이팅입니당