HashTable 구현을 사용하여 HashMap 구현

Question

insert, remove, find, exists과 같은 함수가 포함 된 해시 테이블 구현이 있습니다.

해시 테이블을 사용하여 해시 맵을 구현하고 싶습니다.

그래서 키와 값만 포함하는 간단한 쌍 클래스를 만드는 것이 좋습니다. 키 평등만을 고려하여 오버로드 된 operator=이 있습니다. 또한 해시 함수는 입력으로 쌍 객체를 가져 와서 키 부분 만 고려하여 해시를 반환합니다.

따라서 본질적으로 키 부분만을 고려하여 값 구성원을 수행하기 때문에 본질적으로는 hashtable<key>과 같은 hashmap 내에 hashtable<pair>이 있습니다.

하지만 문제가 발생했습니다.

예를 들어, 지정된 키가있는 쌍이 해시 맵에 있는지 여부를 확인하는 존재 함수를 구현하고자했습니다. 따라서 키를 가져 와서 키가지도 안에 있는지 확인합니다. 이것은, 해시 테이블의 존재를 사용해 구현됩니다. 그러나 hashtable::exists은 입력으로 쌍 유형을 사용합니다.

그래서 지금은 내가 좋아하지 않는 이러한 대안이있었습니다.

• 키와 쌍 객체를 생성하고,

• 캐스트 한 쌍의 객체에 키 객체 초기화되지 않은 값 부분을 남겨 해시 테이블의 기능 만 사용됩니다로 (reinterpret_cast (& 키) 등) 이 상황에서 쌍의 중요한 부분.

첫 번째 것은 불필요한 사본을 만듭니다. 두 번째 키의 주소가 쌍의 개체 주소와 같지 않을 수 있습니다. 나는 키의 주소가 나는

(&pair.key) - (&pair) 

을 계산할 수 있습니다 고려 내가 한 쌍으로 키를 전달하는 적절한 캐스트를 할 수있는 것을 사용하여 확실히 내가 아는 수 있다고 생각하지만.

대체 아이디어가 필요하십니까? (나는 std::unordered_map 같은 STL 코드를보다 읽기 쉽게 생각하기 때문에 내가 예를 들어이을) 당신이 here이 google::dense_hash_map 같은 해시 맵의 기존 구현을 보면

Answer 1

, 당신은 해시 맵은 단순히 템플릿 해시 아니라고 볼 수 있습니다 표. 즉

, 다음과 같이 구현되지 않습니다

template <class T> 
struct hash_table { ... }; 

template <class Key, class Value> 
using hash_map = hash_table<std::pair<Key, Value>>; 

...하지만 같은 :이 클래스는 그대로

template <class Value, class Key> 
struct hash_table { ... }; 

template <class Key, class Value> 
struct hash_map 
{ 
    using ht = hash_table<std::pair<Key, Value>, Key>; 
    ht _ht; 
}; 

그런 hash_table<Value, Key> 당신이, insert(const Value&)뿐만 아니라 find(const Key&)을 가질 수 있습니다 모든 유형을 알고 있습니다.

가장 위에는 hash_set을 매우 쉽게 구현할 수 있습니다.전체 로직은 hash_table 클래스에 있으며, hash_map 및 hash_set은 호출을 전달하고 API 클라이언트에 대해 몇 가지 작업을 수행합니다.