해시 세트는 O (1)로 가장 작은 또는 가장 큰 요소를 찾을 수 있습니까?

Question

해시의 아키텍처와 기능을 잘 이해해야합니다.

STL :: set과 비교할 때, STL :: set과 비교할 때 해시 세트의 장점은 무엇입니까? O (1) 시간 검색을 생각합니다. 이것이 사실이라면 해시 테이블을 사용하지 않는 이유는 무엇입니까? 그들의 차이점은 중복 요소입니까? 또는 다른 사람?

STL :: set의 경우 검색된 최소/최대 검색 시간은 O (1)이기 때문에 주문되었습니다.

해시 세트는 바이너리 검색 트리가 아니며, O (1)을 사용하여 가장 작거나 큰 요소를 찾는 방법은 무엇입니까?

What is the difference between set and hashset in C++ STL?

을 읽은 후 나는 답을 찾을 수 없습니다.

내 아이디어 :

언제 해시 테이블이 아닌 해시 테이블을 사용해야합니까?

STL :: set is ordered set. 따라서, 가장 작은/가장 큰 요소를 얻는 것은 O (1)입니다.

해시 세트의 경우 어떻게됩니까? 주문 됐어?

감사

Answer 1

해시 세트는 방법 O (1) 가장 작은 또는 큰 요소를 찾기 위해, 이진 검색 트리 아닌가요?

이것은 정확히 주요 차이점 중 하나입니다. 일정 시간에 해시 세트에서 가장 작은/가장 큰 요소를 찾을 수 없습니다. 물론 전체 세트를 스캔하여 시간을 O(n) 시간으로 할 수 있습니다.

또 다른 중요한 차이점은 해시 집합을 반복하면 요소가 정렬 된 순서로 반환되지 않는다는 것입니다.

Answer 2

해시 세트는 기본적으로 저장된 값 (키만)이없는 해시 테이블이며 C++의 std::set은 균형 이진 검색 트리로 구현됩니다.

몇 가지 기본적인 오해가있는 것처럼 알고리즘/컴퓨터 과학 서적의 차이점을 읽어야합니다. 예를 들어, 이진 검색 트리에서 가장 작은/가장 큰 요소를 찾는 비용은 로그가 아닌 O(log N)이며 일정하지 않습니다 O(1).

자주 수행해야하는 작업에 따라 두 가지 데이터 구조가 더 적합합니다. 가장 작은 요소를 자주 찾으려면 std::set이 O(log N)에서 연산을 수행하지만 해시 테이블을 사용하면 모든 요소를 ​​검사해야하므로 선형 시간 O(N)을 의미합니다. 반면에 연산이 일반적이지 않고 정규 조회 (집합의 요소?)가 더 일반적이라면 해시 집합의 상수 시간 조회가 집합에서 O(log N) 조회보다 낫습니다.