1

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

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

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

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

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

4

1 回答 1

1

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

这里最重要的一点是您已经注意到的：模板和泛型不是一回事。（好吧，java 泛型只是一个花哨的语法糖工具，这要归功于类型擦除，但这是另一个故事）。

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

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

现在我们看看你的问题：
你想要一个“可散列的”“接口”为你的类型调用散列表中的散列函数。这可以通过两种方式完成：

基于成员函数的方式：

解决问题的一种方法是假设您的类型具有hash()公共成员函数（就像getHashCode()在 java 中一样，它是从 Object 继承的）。所以，在你的哈希表实现中，你使用这个哈希函数，就好像元素有它一样。不用担心传递的类型。事实是，如果您这样做，并且您将类型作为模板参数传递，但该类型没有公共散列成员函数，则无法实例化模板。维奥拉！
将模板视为合同：您在模板中编写完全通用的代码。传递给模板的类型必须满足合同。也就是说，必须拥有您认为他们拥有的一切。

这种方法的问题是在 hashmap 中使用的任何类型都必须有一个 hash 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);
}

但是仿函数最重要的用途是仿函数是类的实例，因此可以作为参数传递给其他站点。也就是说，仿函数充当高级函数指针。

这用于通用 STL 算法，例如std::find_if： Find if 用于根据搜索条件查找指定区间的元素。该标准通过充当布尔谓词的函子传递。例如：

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++ 模板允许您编写模板的特殊显式案例。例如，您编写了一个通用数组类，并且您注意到如果元素的类型是布尔值，那么将布尔值存储为数字位会更有效，以减少内存消耗。使用 C++ 模板，您可以编写特殊情况。您使用显式类型作为模板参数显式编写模板类。这被称为“模板专业化”。事实上，那个“使用位用于布尔大小写”的例子正是std::vector.

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

template<typename T>
struct hash;

我们需要对您将在哈希图中使用的每种类型进行专门化。例如，无符号整数的特化：

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

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

于 2013-07-30T11:47:27.913 回答