1

我正在尝试在 C++ 中实现一个类似于 Java 版本的哈希表

我希望它具有以下形式

template <class Key, class Value> 
class hashtable {
...
}

很快我注意到我需要以某种方式将 Key 转换为数字，以便我可以使用简单的哈希函数 

int h(int hashkey) { 
    return hashkey%some_prime;
}

但令人头疼的是，Key 类型仅在运行时才知道。是否可以在 C++ 中检查运行时的 Key 类型。或者我必须手动创建这个具有不同类型的哈希表类？这更容易做到但很难看。有人知道优雅的解决方案吗？

4

3 回答 3

3

C++ 模板通常是鸭子类型的，这意味着您可以在模板中显式转换为整数类型，并且所有实现适当转换的类型都可以用作键。这样做的缺点是要求类以散列函数合适的方式实现转换运算符，这要求很多。

您可以改为提供函数模板

template<typename T> int hash (T t);

除了内置类型的特化外，任何想要使用自定义类作为键的用户都只需要提供自己的特化即可。我认为这是一个不错的方法。

于 2013-01-02T21:04:43.303 回答
2

你似乎有一些误解。键类型在编译时是已知的——这就是使用模板的全部意义所在。其次，实际上不存在适用于任何类型的完全通用的散列函数。您需要使用函数重载或模板特化为不同类型实现不同的哈希函数。例如，有许多用于字符串的常用哈希函数。

最后，C++11 包含一个标准哈希表 ( std::unordered_map )，您可以使用它来代替自己实现。

于 2013-01-02T20:57:57.827 回答
1

如果你想尝试实现一个“通用”的，也许你可以从一个类似这样的骨架开始：

template <class T, class K>
struct HashEntry {  // you would need this to deal with collision
    T curr;
    K next;
}

template <class V, size_t n>
class HashTable {
    void insert(V v)
    {
        ...
        size_t idx = v->getHashCode(n);
        ...
    }
private:
    HashEntry <V> table_[n];

}

它通常用一些指针类型实例化，要弄清楚指针应该去哪里，它需要类型实现成员函数“getHashCode”......

于 2013-01-02T21:50:31.327 回答