c++ - 具有完美哈希函数的哈希表是否比数组更好？

Question

我正在从事一个使用自定义数据结构解释选举数据的项目。目前，我正在决定哪种数据结构最适合存储有关候选人在不同地区单位中获得的最终票数的信息。

由于这是一项家庭作业，因此禁止使用语言构建的数据结构和来自外部库的数据结构。此外，搜索的复杂度必须小于 O(n)。

我打算使用的散列函数如下所示

key 类型是 unsigned int 类型， key 本身就是候选人在选票上的编号。

template<typename K, typename T>
inline int CandidateResultsHashTable<K, T>::hashFunction(const K & key) const
    {
        return key % (amount_of_candidates + 1);
    }

候选人的数量是已知的，但在选举轮次之间可能会发生变化。哈希表中存储的所有数据将从一个文件中读取，该文件包含所有候选人的数据。所以不应该有任何号码不属于候选人。

我想知道，根据访问时间和内存使用情况，哪种实现会更好。

Answer 1

我已将我的评论汇总为一个答案。

这是对实现称为 map(某些其他语言中的字典)的数据结构的不同方法的总结。

---

键值对列表

解决问题的最简单方法是使用键值对的数组/列表，您只需逐一检查，直到找到正确的键。 但是，它的效率非常低。 O(n) 只适用于小数据集。速度并不那么重要，在数据量非常少的情况下，由于更复杂的数据结构具有开销(例如计算哈希函数)，这种方法可能会更快。

如果您对键进行排序并使用仅为 O(log(n)) 的二进制搜索，则可以显着优化此方法。

---

哈希表

哈希表实现起来相当棘手。您需要足够好的哈希函数。 好的散列函数意味着它有少量的冲突——当两个不同的键有相同的散列时的情况。无论如何，您都需要为这种情况编写程序，但过多的冲突会降低使用哈希表的好处。

您的实现非常简单。

key % (amount_of_candidates + 1)

如果不知道键是如何分配的，就很难判断它是否足够好。

如果键只是连续的数字就很好了。 (你甚至不需要 + 1。)实际上，在那种情况下你有一个哈希表的特殊情况，你不需要检查冲突因为你可以告诉不会有任何。 在这一点上，你可以停止假装你使用哈希表而只是制作一个数组;)每个候选人的位置只是key - smallest_key。事实上，这将是一个非常有效的解决方案:O(1)。

如果键是随机分配的，你就不能把它简化那么多。在这种情况下，您的解决方案基本上是好的。但是，(amount_of_candidates + 1) 对于哈希表来说太小了。它应该比数据量 (load factor) 大 30% 左右。这会将碰撞次数减少到合理的水平。

---

二叉树

另一种解决方案是使用直接映射到 key 的二进制表示的二叉树。 (0 - 左分支，1 右分支) 这是一种与数组中的二进制搜索非常相似的方法，但它允许轻松添加新元素，而无需调整数组大小并将新元素排序到其中。 该解决方案的缺点是需要更高的内存。

您还可以试验其他类型的二叉树。你只需要记住让它们保持平衡，这样它们就能保持高效。我对平衡知之甚少，所以我不会在这个主题上写更多内容。

---

结论

我推断，在你的情况下，键只是连续的整数，所以我会推荐使用普通数组的解决方案，索引层直接指向键的值。 这是一个非常简单但同时又非常有效的解决方案。

---

编辑

好吧，我们来实际回答标题中的问题。

您展示的完美哈希函数的实现与数组没有什么不同。这只是对同一事物进行编码的另一种方式，并且根据某些因素，结果组装可能是相同的。

在其他散列函数的情况下，键分布在 K 的整个范围内，直接数组将不切实际/不可能使用，因为它需要大量内存。如果您成功分配了这么多内存，array 会稍微快一些，因为它不需要计算哈希值，但它肯定不值得。