hash table의 seperate chaining 질문

Question

안녕하세요 우선 좋은 강의 만들어주셔서 감사합니다! 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 해결 방식을 한 가지만 채택해야 하는가? 입니다! 고생 많으십니다!

rkddnr3304589 · Answer

좋은 답변 감사합니다 !

nossi · Answer

안녕하세요 욱님! 해시테이블에대해서 정확히 이해하셨네요~ 깊게 공부하시다보니 해당 질문에까지 다다른 것 같아 대단하게 생각합니다! 언어에서 어떤식으로 해시테이블을 구현할건지 먼저 정합니다. 이에따라 충돌이 발생할 때 어떤 방식으로 이를 해결할지 미리 정합니다. 따라서 한 언어에서 채택한 해시테이블구현 방식은 한번 정해지면 그걸 쓰게 됩니다. 여러 방식을 쓰는 이점이 딱히 없어서 하나를 채택하여 쭉 씁니다. 물론 두 방식을 합쳐서 쓰는 하이브리드형이 여러면에서 장점이 더 많다는 것을 누가 제안하고 합의가 이뤄진다면 하이브리드로 쓸 수도 있을 것같네요!   더 궁금한점이 있으시다면 언제든 질문주세요! 화이팅입니당