c++ - 使用 HashTable 实现实现 HashMap

Question

我有一个哈希表实现，其中包含 insert, remove, find, exists 等函数.

我想使用该哈希表来实现一个 HashMap 。

所以我想创建一个简单的对类，它只包含一个键和一个值。 它会有 operator=重载以仅考虑键的相等性。 此外，哈希函数将获取一对对象作为输入并返回哈希，再次仅考虑关键部分。

因此我会有一个 hashtable<pair>在 HashMap 中，本质上类似于 hashtable<key>因为它只考虑关键部分，只带一个值成员。

但随后问题出现了。

例如，我想实现一个 exists 函数，该函数将检查 hashmap 中是否存在具有指定键的对。这样就会接受一个 key 并检查 key 是否在 map 内。这将使用哈希表的存在来实现。 但是 hashtable::exists现在将一对类型作为输入。

所以现在我有了这些我不太喜欢的选择。

• 用key创建一个pair对象，value部分不初始化

• 将键对象转换为对对象(如 reinterpret_cast(&key))，因为哈希表的函数在这种情况下将仅使用对的键部分。

第一个创建了一个不必要的拷贝。 并且第二个键的地址可能不等于对的对象地址。虽然我相信我可以确定 key 的地址，但考虑到我可以计算

(&pair.key) - (&pair)

并且使用它我可以进行适当的转换以将 key 作为一对传递。

有替代方案吗？

Answer 1

如果您查看 HashMap 的现有实现，例如 google::dense_hash_map here (我以此为例，因为我相信它比像 std::unordered_map 这样的 STL 代码更容易阅读)，您会看到 HashMap 不仅仅是一个模板化的哈希表。

换句话说，它不是这样实现的:

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 的客户端做一些修饰。