std::unordered_set

김대익·2022년 3월 21일
0

unordered_set은
unordered_set이라는 이름답게 내부에서 정렬을 하지않는다
또한
삽입, 삭제, 검색이 O(lg n)의 시간복잡도를 가지던 set과 다르게
O(1)의 시간복잡도를 갖는다.

이는 hash함수와 linked list를 이용한 index로 저장하기 때문이다.

hash화를 시키면
긴 정수값이 나오므로 그대로 index로 사용하기에는 부적합하여
hash % bucket count를 bucket으로써 index로 사용하여 힙에 저장한다.
만약 index가 겹치는 충돌이 일어나면 linked list를 이용하여 연결시켜놓는다


bucket과 linked list는 모두 힙에 저장된다.


만약 bucket보다 많은 양의 데이터가 들어오면
rehashing이 일어나면서 메모리의 공간을 다시 확보하는데 이때 시간복잡도는 O(n)이다.

0개의 댓글