C ++에서 map과 hash_map

C ++에서 map과 hash_map

---

C ++ hash_map과 관련 하여 질문이 map있습니다. 나는 그것이 mapSTL에 있지만 hash_map표준이 아니라는 것을 이해합니다 . 둘의 차이점은 무엇입니까?

---

그것들은 매우 다른 방식으로 구현됩니다.

hash_map( unordered_mapTR1 및 Boost에서 대신 사용하십시오) 키가 테이블의 슬롯에 해시되고 값이 해당 키와 연결된 목록에 저장되는 해시 테이블을 사용하십시오.

map 균형 이진 검색 트리 (일반적으로 빨강 / 검정 트리)로 구현됩니다.

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

---

hash_map많은 라이브러리 구현에서 제공하는 일반적인 확장이었습니다. 이것이 바로 unordered_mapTR1의 일부로 C ++ 표준에 추가되었을 때 이름이 바뀌는 이유 입니다. 지도는 일반적으로 빨강-검정 나무와 같은 균형 잡힌 이진 나무로 구현됩니다 (구현 방법은 다양합니다). hash_map그리고 unordered_map일반적으로 해시 테이블로 구현됩니다. 따라서 순서가 유지되지 않습니다. unordered_map삽입 / 삭제 / 쿼리는 O (1) (일정 시간)이며 맵은 O (log n)입니다. 여기서 n은 데이터 구조의 항목 수입니다. 따라서 unordered_map더 빠르며 항목 순서에 신경 쓰지 않으면보다 선호해야합니다 map. 때로는 순서를 유지하고 싶을 때 (키로 정렬) map그 선택이 될 것입니다.

---

주요 차이점 중 일부는 복잡성 요구 사항에 있습니다.

• A는 map필요 O(log(N))그것이로 구현됩니다으로, 삽입 및 발견 작업을위한 시간을 레드 - 블랙 트리 데이터 구조.

• 은 unordered_map의 '평균'시간이 필요 O(1)삽입 및 발견을위한, 그러나의 최악의 시간을 가질 수있다 O(N). 해시 테이블 데이터 구조를 사용하여 구현 되었기 때문 입니다.

따라서 일반적 unordered_map으로 더 빠르지 만 저장하는 키와 해시 기능에 따라 훨씬 더 나빠질 수 있습니다.

---

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

많은 사람들이 실제로 해시 테이블을 원하기 때문에 해시 기반 STL 연관 컨테이너는 수년간 일반적인 확장이었습니다. 결과적으로 unordered_mapC ++ 표준의 이후 버전에 추가되었습니다 .

---

map의 모든 멤버 가 정렬되어 맵이므로 balanced binary search tree(보통 a rb_tree) 에서 구현 balanced binary search tree됩니다.

hash_map의 hashtable모든 멤버 hashtable가 정렬되지 않았으므로 멤버가 정렬되지 hash_map(unordered_map)않습니다.

hash_mapc ++ 표준 라이브러리는 아니지만 이제는 이름이 바뀌고 unordered_map( 이름이 바뀐 것으로 생각할 수 있음) c ++ 11 이후 c ++ 표준 라이브러리가됩니다.이 질문을 참조하십시오 hash_map과 unordered_map? 자세한 내용은.

아래에서는 두 가지 유형의 맵이 구현되는 방식의 소스 코드에서 핵심 인터페이스를 제공합니다.

지도:

아래 코드는 map이 단지 래퍼이며 balanced binary search tree거의 모든 함수가 함수를 호출 한다는 것을 보여줍니다 balanced binary search tree.

template <typename Key, typename Value, class Compare = std::less<Key>>
class map{
    // used for rb_tree to sort
    typedef Key    key_type;

    // rb_tree node value
    typedef std::pair<key_type, value_type> value_type;

    typedef Compare key_compare;

    // as to map, Key is used for sort, Value used for store value
    typedef rb_tree<key_type, value_type, key_compare> rep_type;

    // the only member value of map (it's  rb_tree)
    rep_type t;
};

// one construct function
template<typename InputIterator>
map(InputIterator first, InputIterator last):t(Compare()){
        // use rb_tree to insert value(just insert unique value)
        t.insert_unique(first, last);
}

// insert function, just use tb_tree insert_unique function
//and only insert unique value
//rb_tree insertion time is : log(n)+rebalance
// so map's  insertion time is also : log(n)+rebalance 
typedef typename rep_type::const_iterator iterator;
std::pair<iterator, bool> insert(const value_type& v){
    return t.insert_unique(v);
};

hash_map:

hash_map다음 hashtable과 같은 구조 로 구현됩니다 .

아래 코드에서의 주요 부분 hashtable을 제공 한 다음 제공합니다 hash_map.

// used for node list
template<typename T>
struct __hashtable_node{
    T val;
    __hashtable_node* next;
};

template<typename Key, typename Value, typename HashFun>
class hashtable{
    public:
        typedef size_t   size_type;
        typedef HashFun  hasher;
        typedef Value    value_type;
        typedef Key      key_type;
    public:
        typedef __hashtable_node<value_type> node;

        // member data is buckets array(node* array)
        std::vector<node*> buckets;
        size_type num_elements;

        public:
            // insert only unique value
            std::pair<iterator, bool> insert_unique(const value_type& obj);

};

Like map's only member is rb_tree, the hash_map's only member is hashtable. It's main code as below:

template<typename Key, typename Value, class HashFun = std::hash<Key>>
class hash_map{
    private:
        typedef hashtable<Key, Value, HashFun> ht;

        // member data is hash_table
        ht rep;

    public:
        // 100 buckets by default
        // it may not be 100(in this just for simplify)
        hash_map():rep(100){};

        // like the above map's insert function just invoke rb_tree unique function
        // hash_map, insert function just invoke hashtable's unique insert function
        std::pair<iterator, bool> insert(const Value& v){
                return t.insert_unique(v);
        };

};

Below image shows when a hash_map have 53 buckets, and insert some values, it's internal structure.

The below image shows some difference between map and hash_map(unordered_map), the image comes from How to choose between map and unordered_map?:

---

I don't know what gives, but, hash_map takes more than 20 seconds to clear() 150K unsigned integer keys and float values. I am just running and reading someone else's code.

This is how it includes hash_map.

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

I read this here https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap

saying that clear() is order of O(N). That to me, is very strange, but, that's the way it is.

참고URL : https://stackoverflow.com/questions/2189189/map-vs-hash-map-in-c