유은영 님이 쓰신 글 :
: 요즘 많이들 해시 테이블을 사용하고 계신데
:
: 해시 테이블과 일반 array의 차이점을 알고 싶어서요
:
: 저는 해시 알고리즘이 해시펑션에 많이 의존적이어서 동일한 해시 펑션을 사용했을때
:
: 일반 어레이나 해시 테이블을 썻을경우에 성능차이가 별로 없을거라고 생각했는데요
:
: 요즘에 찾다보니까 동일한 해시 펑션을 써도 해시 테이블과 vector 에서의 성능차이가 있다고 해서요
:
: 정확하게 알고 싶어서 질문드려요
:
: 예를들어서
:
: 데이터 - 해시 펑션 - 인덱스 펑션 - 해시 테이블 의 구조하고
:  데이터 - 해시 펑션과 비슷한 펑션 - 어레이 순서에 맞춰주는 인덱스 펑션 - vector 하고 비교해 봤을때
:
: 두개의 차이가 크게 나나요?
:
: 요약하자면 해시 알고리즘에서 해시 펑션을 제외한 알고리즘하고 vector 하고 성능차이가 나는지 알고 싶어요.
:

답변:


해쉬펑션이 잘 만들어졌다면 버킷 크기가 작지 않은 한... 해쉬충돌을 적게하면서 골고루 분포시킬 수 있죠.
동일한 해쉬펑션을 사용하면서... 삽입/삭제를 빈번하게 사용한다면... vector 보다는 list 구조가 낫습니다.
삽입/삭제가 빈번할 경우... vector는 element 들을 이동시켜야 하니까.

그 때는 list 구조가 낮죠. (vector 와는 달리 elements 의 이동 없이, 하나의 요소에 대한 링크드 포인터 값만 바꾸면 되므로)
hash map을 구현할 때... 일반적으로 list 구조를 이용해서 구현하기 마련입니다.

STL Template 라이브러리를 이용하는 게 편하고요.
추가로 최적화가 필요하다면... template specialization을 이용하든가, 아니면 직접 구현해서 써도 되고요.