使用HashTable实现实现HashMap [英] Implementing a HashMap using a HashTable implementation

问题描述

我有一个hashtable实现，其中包含插入，删除，查找，存在。

I have a hashtable implementation which contains functions such as insert, remove, find, exists.

那个散列表我想实现一个hashmap。

Using that hashtable I wanted to implement a hashmap.

所以我想到创建一个简单的对类，只是包含一个键和一个值。
它将使 operator = 重载以仅考虑键的相等性。
此外，散列函数将获得一个对对象并返回散列，再次只考虑关键部分。

So I had in mind to create a simple pair class that would just contain a key and a value. It would have the operator= overloaded to take into account only the keys equality. Also the hash function would get as input a pair object and return the hash, again taking into account only the key part.

因此，我会有一个< $ hascable> hashtable 在hashmap里面，其实质上就是 hashtable< key> ，因为它只会考虑到

Thus I would have a hashtable<pair> inside the hashmap which in essence would be something like hashtable<key> because it would take into account only the key part and just carry along a value member.

但是随后出现了问题。

以实现一个exists函数，该函数将检查在hashmap中是否存在具有指定键的对。所以，这将采取一个键，并检查键是否在地图内。这将实现使用hashtable的存在。
但是 hashtable :: exists 现在输入一个对类型。

For example I wanted to implement an exists function that would check whether a pair with a specified key existed in the hashmap. So that would take in a key and check if the key is inside the map. This would be implemented using the hashtable's exists. But the hashtable::exists now takes as input a pair type.

• 使用键创建一个对对象，并将值部分保留为未初始化

• Create a pair object with the key, and leave the value part uninitialized

将密钥对象转换为一个对对象（如reinterpret_cast（& key）），因为散列表函数在这种情况下只使用对的关键部分

Cast the key object to a pair object (like reinterpret_cast(&key)) as the hashtable's functions will use only the key part of the pair in this situation.

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

The first one creates an unnecessary copy. And with the second one key's address may not be equal to pair's object address. Although I believe I can know for sure the key's address taking into account that I can calculate

(&pair.key) - (&pair)

并且使用我可以做正确的转换来传递密钥作为一对。

And using that I could do proper casts to pass the key as a pair.

有关替代方案的任何想法吗？

Any ideas for alternatives?

推荐答案

哈希映射的实现，如 google :: dense_hash_map 这里 （我把这个作为例子，因为我相信它比STL代码比如 std :: unordered_map 更容易阅读，你会看到哈希映射不是简单的模板哈希表。

If you look at existing implementations of hash map like google::dense_hash_map here (I take this as example because I believe it is easier to read than STL code like std::unordered_map), you will see that the hash map is not simply a templated hash table.

换句话说，它不是像下面这样实现：

In other words, it is not implemented like:

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

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

... like：

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&）

Then, in hash_table<Value, Key> you can have insert(const Value&) but also find(const Key&), as this class is aware of all the types.

在上面，你可以非常方便地实现 hash_set 。整个逻辑将在您的 hash_table 类中， hash_map 和 hash_set 只转发调用并为API的客户端做一些装饰。

On the top of that you can implement very easily hash_set. The entire logic will be in your hash_table class, hash_map and hash_set only forward the calls and do some cosmetic stuff for the client of the API.

这篇关于使用HashTable实现实现HashMap的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！