4

我正在尝试通过模板在 C++ 中实现 HashTable。这是签名：

template<class T1, class T2>
class HashTable {

public:
void add(T1 a, T2 b);

void hashFunction(T1 key, T2 value)
{

// how to implement this function using key as a generic 
// we need to know the object type of key

}
};

因此，我无法继续执行涉及通用键的实现。

在 Java 中，我可以轻松地将键转换为字符串，然后将键的哈希实现为字符串。但是，在 C++ 中，我知道有一个 RTTI 的概念，它可以动态地将对象转换为所需的对象。

如果此方法完全正确，如何实现该动态转换？

如果在这种情况下使用模板不是实现泛型的正确方法，那么请提出一些更好的方法。

4

2 回答 2

10

您通常会使用std::hash它，并让类型实现者根据需要专门化该模板。

size_t key_hash = std::hash<T1>()(key);

对于给定的任何随机类型，您无法通用地实现散列函数。如果两个对象相等，则它们的哈希码必须相同。您可以通过散列函数简单地运行对象的原始内存，但这些类型可能会实现operator==忽略某些对象数据（例如同步对象）的重载。在这种情况下，您可能（并且非常容易）为相等的对象返回不同的哈希值。

于 2013-04-26T19:21:46.117 回答
4

奇怪的是，您想要同时散列键和值。在它之后，你将如何通过唯一的关键来获得价值？

如果您使用的是 C++11，那么好主意是使用std::hash<T1>为某些类型（整数、字符串、指针）提供的，并且可能专门用于其他类。此外，允许使用第三个模板参数类更改它是个好主意。看看unordered_map是怎么做的

template<typename K, typename V, typename H = std::hash<T>>
class HashTable {
   //...
   void hashFunction(const T1& key) {
        hash = H()(key);
        //process hash somehow, probably you need get reminder after division to number of buckets or something same
        return hash % size;
   }
}

似乎不可能编写自己的哈希器，这对于大多数类型都可以正常工作，因为相等运算符可能会以某种复杂的方式被覆盖

于 2013-04-26T19:25:31.527 回答