使用 HashTable 实现实现 HashMap

Question

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

等函数

我想使用那个哈希表来实现一个哈希映射。

所以我想创建一个简单的对 class，它只包含一个键和一个值。它将重载 operator= 以仅考虑键的相等性。此外，哈希函数将获得一对对象和 return 哈希作为输入，同样只考虑关键部分。

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

但是后来问题出现了

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

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

用key创建pair对象，value部分不初始化
将键对象转换为对对象（如 reinterpret_cast(&key)），因为哈希表的函数在这种情况下将仅使用对的键部分。

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

(&pair.key) - (&pair)

并使用它我可以进行适当的转换以成对传递密钥。

有替代方案吗？

Answer 1

如果你看看像 google::dense_hash_map here 这样的哈希映射的现有实现（我以此为例，因为我相信它比像 std::unordered_map 这样的 STL 代码更容易阅读），你会看到哈希映射不仅仅是一个模板化的哈希 table.

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

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&)，因为这个 class 知道所有类型。

最重要的是，您可以非常轻松地实施 hash_set。整个逻辑将在您的 hash_table class、hash_map 和 hash_set 中，仅转发呼叫并为 API 的客户做一些美容工作。

使用 HashTable 实现实现 HashMap

Implementing a HashMap using a HashTable implementation

c++

type-conversion

abstract-data-type