hash + BST 자료구조에 대해서 어떻게 생각하시나요?
글쓴이: trymp / 작성시간: 수, 2019/06/26 - 6:27오후
대용량 트래픽에서 IP 주소로 엔트리를 검색하는 함수를 짜려고 합니다.
물론 도중에 추가/삭제도 일어날 수 있습니다.
근데 hash방식을 사용하면 hash table 을 길게 잡아야 되서 메모리가 부담스럽습니다.
그래서 아래 사이트에서 hash + BST 라는 소스코드가 있길래 이방식을 쓰면 어떻까?
생각중입니다
hash table 사이즈는 줄이고 대신 각 bucket 에 BST 가 들어가서 충돌시 검색에 사용하는데요.
이 방법 괜찮을까요? 고수님들의 조언 부탁드립니다.
https://www.sanfoundry.com/c-program-implement-hash-tables-chaining-binary-trees/
Forums:
그냥
hash key가 이상적이라고 가정할 때, 어차피 hash table 버켓 수보다 들어올 수 있는 아이템의 수가 많다면 반드시 충돌이 생기죠. 그 충돌이 생겼을 때, 나이브한 리스트보다는 BST로 해두겠다는 뜻인 것 같구요.
데이터의 수를 N, 해쉬 테이블 엔트리의 수를 m이라고 하면, 평균적으로 하나의 버켓,, 그러니까 하나의 BST 또는 리스트에 들어갈 아이템의 수는 N/m입니다. m이 작다면 상수고 크다면 N으로 보면 되겠구요.
이 데이터 크기에 대해 BST vs. 리스트니까 주어진 문제랑 각 데이터 스트럭쳐의 메모리/시간 복잡도를 생각하셔서 결정하면 될 것 같네요.
...
그냥 C++ STL로 unordered_map 사용해도 될 것 같습니다만... C++을 쓸 수 없는 환경인가요?
그냥2
이 경우에는 sparse hash table을 한 번 생각해 보세요.
STL의 경우 내부 구현이 아마도 버킷 + list로 되어 있으리라 생각되네요. 버킷 수가 작으면 원하는 속도를 얻을 수 없을지도 모르겠습니다.
댓글 달기