需要帮助开始构建我自己的哈希表

Question

我正在学习哈希表，试图了解它们是如何工作的。我想制作一个相当简单的具有单独链接的哈希表（使用数组中的列表）。我有几个问题：

1. 假设密钥可以是任何类型，我会要求用户实现哈希函数，对吧？这可以避免吗？

2. 用户还需要在初始化时提供包含列表（用于冲突）的数组的长度，对吗？这可以避免吗？

如果您有任何其他提示，或者可能是哈希表的 C++ 中的一些清晰的代码示例，我将不胜感激。

感谢您的帮助。

Answer 1

通常，是的，您需要客户端指定哈希函数，因为如果您正在编写通用哈希表并在任意类型 T 上进行操作，您将不知道如何以语义上有意义的方式对其进行哈希处理。您可以通过对所存储元素的类型和哈希函数的类进行参数化来实现此目的。例如：

template <typename T, typename Hash = std::hash<T>>
    class MyHashTable {
    /* ... */
}

在这里，您可以使用模板的默认参数来选择默认的哈希函数，除非用户另有指定。

虽然客户端通常可以指定表的初始大小，但这不是必需的。您可以对存储桶的数量进行有根据的猜测（例如，最初使用 17 个存储桶），并随着负载系数的增加而增长表。这类似于 std::vector 的工作原理：实现可以选择默认大小，但如果客户端显式请求预设大小的向量或调用 Reserve ，该实现接受用户的提示。例如，您可以有一个以下形式的构造函数：

template <typename T, typename Hash = std::hash<T>>
    class MyHashTable {
public:
    MyHashTable(unsigned numBuckets = 17);
}

这样，客户端就可以构造一个具有默认存储桶数量的哈希表，或者如果他们了解他们想要的存储桶数量，则可以将其指定为范围。但是，您可能还希望将存储桶隐藏为详细信息，并让客户端指定他们希望放入表中的元素数量，然后让您的类为此在幕后进行计算。这使得在幕后切换实现变得更容易，因此，如果您想使用动态完美哈希表之类的东西而不是链式哈希，则该类可以处理计算初始大小的复杂性。

至于代码示例，我不确定如何在不放弃构建哈希表所涉及的大量复杂性的情况下提供任何代码示例。 :-) 如果您对某段特定代码感兴趣，但自己编写时遇到困难，请随时将其作为单独的问题发布，以便获得更有针对性的反馈。

希望这有帮助！

Answer 2

查看哈希算法的各种实现。有很多可用的。如果需要，您可以使哈希存储可变。由你决定。对于大多数哈希算法，可能会发生冲突。请记住这一点。

Answer 3

如果您想了解哈希表，我建议您从最简单的开始，即线性链接哈希表

在这里您考虑一个固定大小的指针数组（指向您定义的类型项目的指针），您的项目将存储在其中，考虑还有一些计数器，一个用于跟踪数组的长度，另一个用于跟踪添加到表中的项目数，直到某一时刻

您可以使用宏来定义向表添加项目的功能像这样的哈希表

 h(k) = k % M  

，其中 k 是要添加的项目的索引（键），M 是一个质数，表示指针数组的大小（例如 13、29、41、543），h(k) 将为您提供项目将要到达的位置被插入。

您应该考虑使用固定大小的指针数组的原因是因为这样会产生

 O(n) 

成本。

因此，从这个简单的函数开始，您可以修改它并考虑实现一些更复杂的函数，例如开放寻址、线性探测、二次探测和双散列

至于用户请求的有关项目数量的输入，我完全同意 templatetypedef 之前所说的