C++ STL에서 STL

Question

의 맵과 해시 맵의 차이점은 두 가지 맵, 맵 및 해시 맵이 있습니다. 누구든지 그 주된 차이점을 알고 있습니까?

Answer 1

지도 데이터 구조로 레드 - 블랙 트리를 사용하십시오, 그래서 요소가 당신이이 분류되어 있습니다 넣어 삽입합니다. 요소는 적어도 operator<을 구현해야합니다.

hashmap은 해시를 사용하므로 요소는 정렬되지 않으므로 삽입/삭제는 O (1)입니다. 요소는 적어도 operator==을 구현해야하며 해시 함수가 필요합니다.

Answer 2

map은 적색 - 검정색 트리, O(log(n)) 액세스 시간입니다. (표준이 아니기는하지만 표준이 아니기 때문에) 키의 해시를 연결된 목록의 배열에서 인덱스로 사용하므로 최상의 액세스 시간은 O(1)이고 최악의 경우는 O(n)입니다 (표준이 아닌 unordered_map이 표준이됩니다). O는 (로그 (N))/삭제

이 http://en.wikipedia.org/wiki/Red-black_tree

Answer 3

주요 차이점은 검색 시간입니다. 몇 가지 데이터를

많은 데이터에 대한

이

어쨌든 이전에 주어진 tecnical 답변이 정확 더 나은 해시 맵을하다 더 나은지도를합니다.

Answer 4

hash_map은 해시 테이블을 사용합니다. 이것은 이론 상으로는 "일정한"시간입니다. 대부분의 구현에서는 "충돌"해시 테이블을 사용합니다. 무엇 실제로 일어나는 것은 :

• 그것은
• 당신은 (표에 당신에게 임의의 장소를 생성하는 개체에 대한 "해시"기능이 큰 테이블을 생성 찾고 랜덤하지만 해시 함수는 항상 것입니다 객체에 대해 동일한 값을 반환합니다. 일반적으로이 값은 테이블의 크기에 대한 실제 32 비트 (또는 64 비트) 해시 값의 mod입니다.
• 테이블에서 공간을 사용할 수 있는지 확인합니다. 그렇다면 항목을 표에 배치합니다. 그렇지 않으면 삽입하려는 요소가 있는지 확인합니다. 그렇다면 복제본이므로 삽입 할 필요가 없습니다. 그렇지 않은 경우이를 "충돌 (collision)"이라고하며 다른 수식을 사용하여 수식을 사용하여 중복되거나 빈 셀을 찾을 때까지 계속됩니다.
• 표가 너무 많이 채워지면 크기가 조정됩니다. 효율적인 (시간에) 구현은 모든 원래 해시 값을 요소와 함께 저장하므로 해시를 다시 계산할 필요가 없습니다. 또한 해시를 비교하는 것이 대개 요소를 비교하는 것보다 빠르기 때문에 충돌의 대부분을 사전 단계로 제거하기 위해 검색하는 동안 해시를 비교할 수 있습니다.
• 아무 것도 삭제하지 않으면 간단합니다. 그러나 요소를 삭제하면 추가 복잡성이 추가됩니다. 삭제 된 요소가있는 셀은 모두 비어있는 상태와 다른 상태에 있습니다. 충돌이 있었을 수도 있고 비울 경우 요소를 찾을 수 없습니다. 그래서 보통 "표식"이 있습니다. 물론 우리가 셀을 재사용하고 싶을 때, 더 낮은 다운 (이 셀에 삽입 할 수없는 경우)이 남아있는 경우에 대비하여 재발행해야하며, 삭제 된 셀을 재사용하는 것을 잊지 마십시오.
• 일반적인 제약 조건은 객체가 동등성을 검사하기 위해 구현되어야하지만 Dinkumware (또는 SGI는 SGI가 구현 한 것입니다.) 연산자가 < 인 경우 구현이 느릴 수는 있지만 요소와 연관된 컨테이너의 유형을 분리하는 이점이 있습니다 는 해시 함수를 저장해야만 해시에 저장할 수 있습니다.

테이블이 충분히 크면 작업 시간은 일정합니다. 즉, 실제 요소 수에 의존하지 않습니다. 실제로, 실제로 충돌이 발생할수록 더 많은 요소가 발생합니다.

std :: map은 이진 트리를 사용합니다. 객체에 대한 해시 함수를 정의 할 필요는 없으며 엄격하게 정렬 된 비교 만 수행 할 수 있습니다. 삽입시 삽입 지점을 찾기 위해 트리를 되풀이하여 반복하고 노드를 추가하고 트리의 균형을 조정하여 잎의 깊이가 결코 1을 넘지 않도록해야합니다. 시간 재조정 (rebalancing)은 나무의 깊이와도 관련이 있으므로 모든 연산은 O (log N)입니다. 여기서 N은 요소의 수입니다. 완전히 확장

• :

  해시의 장점은 복잡 트리의 장점이다. 해시가 트리보다 요소 당 "수하물"을 덜 필요로 할지라도, 필요로하는 것만 사용하고, 거대한 테이블을 필요로하지 않으며, 테이블의 크기를 미리 차지할 필요가 없습니다.

• 먼저 해시 할 필요가 없습니다. 데이터 세트가 크지 않은 경우 좋은 함수의 경우 비교 시간보다 오래 걸릴 수 있습니다.

std::map와 또 다른 문제는 특히 가장 일반적으로 사용되는 키를 사용하여, 훨씬 더 효율적이 될 것이다 -1, 0 또는 1을 반환 된 "비교"기능 동안 단일 엄격하게 정렬 된 비교 함수를 사용한다는 것입니다 std :: string은 이미이 함수가 구현되어 있습니다 (char_traits::compare). (이 비효율은 x==y을 확인하기 위해 x<y과 y<x을 검사한다는 점을 전제로하므로 두 번의 비교를 수행합니다.이 작업은 조회 당 한 번 수행됩니다.