c++ - 混淆在C++中实现rehash()函数

Question

我的目标是为我在C++模板类中编写的哈希表实现rehash()方法。但是，由于该方法仅将类型视为通用类型，因此我对可以在其上进行散列的确切内容感到困惑。据我所知，这与Java泛型有所不同

我对Java的理解...
在Java中，由于每个对象都继承了hashCode()方法，因此我们可以重写此方法。如果使用Java编写通用哈希表，则在rehash()期间，可以简单地调用hashCode()方法以返回值。可以通过tableSize进行修改。无痛

回到C++ ...
由于我不相信自己可以简单地在C++泛型上调用hashCode()方法，也无法访问泛型类型的数据成员，因此我不知道该如何处理。

C++中的通用类型是否可以某种方式继承抽象类，以便强制使用虚拟hashcode()= 0方法？
还是模板类中的哈希函数依赖于其他类型的非数据成员哈希？

试图尽可能清楚。感谢任何可以为我指明正确方向或提供指导的人。

Answer 1

注意:当然，我想您实现哈希表的目的是出于学习目的。如果不是，请使用std::unordered_map。

这里最重要的一点是您已经注意到的:模板和泛型不是ozt_rstrong。 (好吧，由于泛型删除，java泛型只是一个花哨的语法糖工具，但这是另外一个故事了)。

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

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

现在我们来看您的问题:
您希望类型的“可哈希”“接口(interface)”调用哈希表中的哈希函数。
这可以通过两种方式完成:

基于成员函数的方式:

解决问题的一种方法是假设您的类型具有hash()公共(public)成员函数(类似于java中的getHashCode()，它是从Object继承的)。
因此，在哈希表实现中，您可以像使用元素一样使用此哈希函数。不用担心传递的类型。
事实是，如果执行此操作，并且您将没有公共(public)哈希成员函数的类型作为模板参数传递，则无法实例化模板。维奥拉!
将模板视为契约(Contract):在模板中编写完全通用的代码。传递给模板的类型必须完全履行契约(Contract)。也就是说，必须拥有您认为应该拥有的所有东西。

这种方法的问题在于，哈希图中使用的任何类型都必须具有哈希公共(public)成员函数。请注意，您不能通过这种方式在哈希图中使用基本类型。

基于函子的方式:

函子是充当函数的类。也就是说，可以使用该类的实例，因为它是一个函数。例如:

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);
}

但是函子的最重要用途是基于函子是类的实例，因此可以作为argtments 传递到其他站点。即，函子充当高级函数指针。

它用于诸如std::find_if之类的通用STL算法中:Find if用于根据搜索条件查找指定间隔的元素。该条件是通过充当 bool(boolean) 谓词的函子传递的。例如:

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 */
   }
};

并在您的哈希表类中使用它:

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++模板允许您编写模板的特殊显式实例。例如，您编写了一个通用数组类，并注意到如果元素的类型为 bool(boolean) 型，则将 bool(boolean) 型存储为数字位可能会更有效，以减少内存消耗。使用C++模板，您可以编写特殊情况。您可以将显式类型的模板类显式地编写为模板参数。这称为"template specialization"。实际上，“使用 bool(boolean) 型位”示例就是 std::vector does。

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

template<typename T>
struct hash;

对于您在哈希图中使用的每种类型，我们都需要专门化。例如，无符号整数的特殊化:

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

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