混淆如何在C++中实现rehash()函数

Question

我的目标是为我在C++模板类中编写的哈希表实现一个re散列()方法。但是，我搞不懂我到底可以散列什么，因为这个方法只知道作为泛型的类型。据我所知，这与Java泛型不同

我对java的理解..。在Java中，由于每个对象都继承了hashCode()方法，所以我们可以重写该方法。如果用java编写一个通用哈希表，那么在rehash()期间，可以简单地调用hashCode()方法来返回一个值。这可以通过tableSize进行建模。无痛

回到C++..。因为我不相信我可以简单地在我的hashCode泛型上调用一个C++ ()方法，也不能访问泛型类型的数据成员，所以我不知道我可以重新散列什么。

我在C++中的泛型类型是否有可能继承一个抽象类，以便强制使用一个虚拟的hashcode()=0方法？还是模板类中的哈希函数依赖于其他类型的非数据散列？

试着尽可能清楚。感谢任何人，谁能指出我的正确方向或提供一些指导。

Answer 1

注意:当然，，我认为您实现哈希表的目标是为了学习。如果没有，请使用std::unordered_map。

这里最重要的一点是您注意到的：模板和泛型并不是相同的东西。(由于类型擦除，java泛型只是一个花哨的语法工具，但它的另一个故事)。

C++模板为模板的每个不同实例化编写一个类的版本。也就是说，如果在您的程序中使用std::vector<int>和std::vector<bool>，编译器将生成以int为类型的类向量和以bool为类型的类向量的代码。

模板最强大的方面之一是，每个类型相关的操作都在编译时进行评估。也就是说，每一个模板实例化、别名、typedef等等都是在编译时完成的。您在运行时获得的代码是不同模板实例的最终生成类的复合。因此，您不需要在运行时考虑类型，比如在java或C#这样的面向对象语言中，而是考虑编译时。在编译结束时，必须解决的所有问题。

现在我们来看看你的问题：

您希望为您的类型提供一个"hashable“”接口“，以便在哈希表中调用哈希函数。这可以通过两种方式实现：

基于成员职能的方式：

解决问题的一种方法是假设您的类型有一个hash()公共成员函数(就像java中的getHashCode()，它是从对象继承的)。因此，在您的hashtable实现中，您使用这个散列函数，就好像元素有它一样。别担心过去的类型。事实是，如果您这样做，并且将一个类型作为没有公共散列成员函数的模板论证传递，则不能实例化模板。维奥拉！

将模板视为契约:在模板中编写一个完全通用的代码。传递给模板的类型必须完全填充合同。也就是说，必须拥有你认为他们拥有的一切。

这种方法的问题是，在hashmap中使用的任何类型都必须有一个散列公共成员函数。请注意，您不能用这种方式在hashmap中使用基本类型。

基于函子的方式：

函子是充当函数的类。也就是说，可以像使用函数一样使用该类的实例。例如：

template<typename T>
struct add
{
    T operator()(const T& a , const T& b)
    {
        return a + b;
    }
};

您可以如下所示使用此函式：

int main()
{
   add<int> adder;

   int a = 1 , b = 2;
   int c = adder(a,b);
}

但是函子最重要的用途是基于函子是类的实例，因此可以作为的论证传递到其他站点。也就是说，函子充当一个高级函数指针.

这在一般的STL算法中使用，如std::find_if：Find用于根据搜索条件查找指定间隔的元素。该条件与充当布尔谓词的函子一起传递。例如：

class my_search_criteria
{
   bool operator()(int element)
   {
      return element == 0;
   }
};  

int main()
{
    std::vector<int> integers = { 5 , 4 , 3 , 2 , 1 , 0 };

    int search_result = std::find_if( std::begin( integers ) , std::end( integers ) , my_search_criteria() );
}

但是，函子如何解决你的问题呢？

您可以使用充当散列函数的泛型函式：

template<typename T>
struct hash
{
   unsigned int operator()(const T& element) 
   {
      return /* hash implementation */
   }
};

并在您的hashtable类中使用它：

template<typename T>
class hachtable
{
private:
   hash<T> hash_function;
   std::vector<T> _container;

   void add(const T& element)
   {
      _container.insert(std::begin( _container ) + hash_function( element ) , element);
   }
};

注意，您需要为元素的类型实现哈希。C++模板允许您编写模板的特殊显式情况。例如，您编写了一个泛型数组类，并且注意到，如果元素的类型是布尔型，则如果将布尔值存储为位数，可以更有效地减少内存消耗。使用C++模板，您可以编写特殊情况。使用显式类型作为模板论证，显式地编写模板类。这就是所谓的“模板专业化”。事实上，“为布尔案例使用位”的例子正是有吗？的例子。

在我们的例子中，如果我们有一个哈希函子的声明：

template<typename T>
struct hash;

对于您将在hashmap中使用的每种类型，我们都需要一个专门化。例如，对未签名的ints的专门化：

template<>
struct hash<unsigned int>
{
   unsigned int operator()(unsigned int element)
   {
       return element;
   }
};

基于函子的方式正是C++标准libray所做的。它有一个哈希函子std::hash的定义，并在哈希表实现中使用它，比如std::unordered_map。注意，libray对于基本类型有一组内置的散列专门化。