지도 대 C++의 hash_map

Question

C++에서 hash_map 및 map이라는 질문이 있습니다. map은 STL이지만, hash_map은 표준이 아닙니다. 둘의 차이점은 무엇입니까?

Answer 1

매우 다른 방식으로 구현됩니다.

hash_map (TR1 및 부스트에서는 unordered_map) 대신 해시 테이블을 사용하면 키가 테이블의 슬롯에 해시되고 해당 값이 해당 키와 연결된 목록에 저장됩니다.

map은 균형 이진 검색 트리 (보통 빨간색/검은 색 트리)로 구현됩니다.

unordered_map은 컬렉션의 알려진 요소에 액세스 할 때 약간 더 나은 성능을 제공해야하지만 map은 추가적인 유용한 특성 (예 : 정렬 된 순서로 저장되어 시작부터 끝까지 허용)을 갖습니다. unordered_map은 삽입 및 삭제가 map보다 빠릅니다.

Answer 2

C++ 사양은 STL 컨테이너에 사용해야하는 알고리즘을 정확히 말하지 않습니다. 그러나 map 및 기타 연관 컨테이너의 해시 테이블 사용을 배제하는 성능에 특정 제약 조건을 적용합니다. (가장 일반적으로 빨강/검정 나무로 구현됩니다.) 이러한 제약 조건은 해시 테이블이 제공 할 수있는 것보다 더 나은 최악의 경우 성능을 요구합니다.

많은 사람들이 실제로 해시 테이블을 원하지만 해시 기반 STL 연관 컨테이너는 수년간 공통된 확장 프로그램이었습니다. 결과적으로 그들은 더 많은 버전의 C++ 표준에 unordered_map 등을 추가했습니다.

Answer 3

hash_map은 많은 라이브러리 구현에서 제공되는 공통 확장입니다. 이것이 바로 TR1의 일부로 C++ 표준에 추가되었을 때 unordered_map으로 이름이 변경된 이유입니다. 지도는 일반적으로 빨강 - 검정 나무와 같은 균형 잡힌 이진 트리로 구현됩니다 (구현은 물론 다릅니다). hash_map 및 unordered_map은 일반적으로 해시 테이블로 구현됩니다. 따라서 주문은 유지되지 않습니다. unordered_map 삽입/삭제/질의는 O (1) (상수 시간)가 될 것이며, 여기서 map은 O (log n)가 될 것이다. 여기서 n은 데이터 구조에있는 항목의 수이다. 따라서 unordered_map은 빠르며, 항목의 순서가 마음에 들지 않으면 map 이상을 선호해야합니다. 때로는 주문을 키순으로 유지하기를 원하며 그 경우 map이 선택 될 수 있습니다.

Answer 4

몇 가지 중요한 차이점은 복잡성 요구 사항에 있습니다.

지도에는 삽입 및 찾기에 O (log (N)) 시간이 필요합니다.

unordered_map은 삽입과 발견에 대해 O (1)의 평균 시간이 필요하지만 최악의 경우 O (N) 시간이 허용됩니다.

일반적으로 unordered_map은 더 빠르지 만 저장하는 키와 해시 함수에 따라 훨씬 더 심각해질 수 있습니다.

Answer 5

무엇을 제공하는지 모르지만 hash_map은 부호없는 정수 키와 부동 소수점 값을 지우는 데 20 초 이상 소요됩니다. 나는 지금 막 달리고 다른 사람의 부호를 읽고있다.

hash_map을 포함하는 방법입니다.

#include "StdAfx.h" 
#include <hash_map> 

나는 그() O (N)의 순서 분명하다 말을 여기 https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap

이를 참조하십시오. 그것은 저에게는 매우 이상합니다. 그러나 그것이 그 방법입니다.