如何在C++中实现泛型哈希函数

问题描述：

我想通过模板在C++中实现HashTable。下面是签名：如何在C++中实现泛型哈希函数

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的概念，它可以动态地将对象转换为所需的对象。

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

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

就强制约束'T1'有“可哈”。即一个给你散列键的方法必须存在。 – millimoose 2013-04-26 19:23:39

（Java解决这个问题的方法是让所有对象都可排序） – millimoose 2013-04-26 19:23:56

你知道C++ 11中有['std :: unordered_set']（http://en.cppreference.com/w/cpp/container/unordered_set）？它是标准库中的一个哈希表。 – dyp 2013-04-26 19:28:07

答

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

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

没有办法一般地实现你给定的随机类型的散列函数。如果两个对象相等，则它们的哈希码必须相同。你可以简单地通过散列函数运行对象的原始内存，但是这些类型可能会实现忽略某些对象数据片段（比如同步对象）的重载。在这种情况下，你可能（很容易）为相同的对象返回不同的散列值。

但是，我想为通用密钥实现我自己的散列表。在STL中必须有某种方式来实现它。这里的实现是在现实生活中使用的情况。 – Sankalp 2013-04-26 19:24:39

@Sankalp有，我已经给你了：'std :: hash'。例如，你可以使用'std :: hash '。如果当你的HashTable模板被实例化时没有专门的'T1'，编译器会给出一个错误。如果你不是'T1'给出的类型的作者，那么你*不可能*希望为它实现正确的哈希算法。 – cdhowie 2013-04-26 19:25:43

@PeterBecker谢谢你的编辑......我显然没有足够的咖啡因。 – cdhowie 2013-04-26 19:29:14

答

奇怪的是，你想散列键和值。你如何能够通过只有钥匙才能获得价值？

如果您使用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; 
    } 
}

这似乎是不可能写你自己的散列器，这将适用于大多数类型的确定，因为运营商的平等在一些复杂的方式也许覆盖

+1为建议提供哈希实现作为模板参数。 – cdhowie 2013-04-26 19:29:59

如何在C++中实现泛型哈希函数

相关推荐