具有完美哈希函数的hashtable是否比数组更好？
Is hash table with a perfect hash function better than an array?
我正在从事一个使用自定义数据结构解释选举数据的项目。目前我正在决定哪种数据结构最适合存储有关候选人在不同地区单位获得的最终票数的信息。
由于这是作业，因此禁止使用语言内置的数据结构和来自外部库的数据结构。此外，搜索的复杂度必须小于 O(n)。
我打算使用的散列函数如下所示
密钥类型为 unsigned int 类型，密钥本身就是候选人在选票上的编号。
template<typename K, typename T>
inline int CandidateResultsHashTable<K, T>::hashFunction(const K & key) const
{
return key % (amount_of_candidates + 1);
}
候选人的数量是已知的，但在选举轮次之间可能会发生变化。哈希 table 中存储的所有数据将从一个文件中读取，该文件包含所有候选人的数据。所以不应该有任何不属于候选人的号码。
我想知道，根据访问时间和内存使用情况，哪种实现会更好。
我已将我的评论汇总为一个答案。
这是对实现称为 map（某些其他语言中的字典）的数据结构的不同方法的总结。
key-value 对列表
解决问题的最简单方法是 array/list 对 key-value 对，您只需一对一检查，直到找到正确的密钥。
但是，它的效率非常低。 O(n) 只适用于小数据集。速度并不重要，在数据量非常少的情况下，由于更复杂的数据结构（例如计算哈希函数）的开销，这种方法可能会更快。
如果您对键进行排序并使用仅为 O(log(n)) 的二进制搜索，则可以显着优化此方法。
哈希table
Hash table 实现起来相当棘手。您需要足够好的哈希函数。
好的散列函数意味着它有少量的冲突——当两个不同的键有相同的散列时的情况。无论如何你都需要针对这种情况的程序，但是太多的冲突会减少使用散列的好处 table.
你的实现很简单。
key % (amount_of_candidates + 1)
如果不知道按键是如何分配的，就很难判断它是否足够好。
如果键只是连续的数字就完美了。 （你甚至不需要 + 1。）实际上，在那种情况下你有一个哈希 table 的特殊情况，你不需要检查冲突因为你可以告诉不会有任何。
在这一点上你可以停止假装你使用散列 table 而只是做一个数组;）每个候选人的位置只是 key - smallest_key。事实上，这将是一个非常有效的解决方案：O(1).
如果键是随机分配的，你就不能把它简化那么多。在这种情况下，您的解决方案基本上是好的。但是，(amount_of_candidates + 1) 对于散列 table 来说太小了。它应该比数据量 (load factor) 大 30% 左右。这会将碰撞次数减少到合理的水平。
二叉树
另一种解决方案是使用直接映射到密钥的二进制表示的二叉树。 （0 - 左分支，1 右分支）
这是一种与数组中的二进制搜索非常相似的方法，但它允许轻松添加新元素，而无需调整数组大小并将新元素排序到其中。
该解决方案的缺点是需要更高的内存。
您还可以试验其他类型的二叉树。你只需要记住让它们保持平衡，这样它们就能保持高效。我不太了解平衡，所以我不会在这个话题上写更多。
结论
我推断，在你的情况下，键只是连续的整数，所以我会推荐使用普通数组的解决方案，索引层直接指向键的值。
这是一个非常简单同时非常有效的解决方案。
编辑
好了，下面就按照标题来实际回答一下吧
你展示的完美哈希函数的实现与数组没有什么不同。这只是对同一事物进行编码的另一种方式，并且根据某些因素，结果组装可能是相同的。
对于键分布在整个 K 范围内的其他哈希函数，直接数组将不切实际/无法使用，因为它需要大量内存。如果您成功分配了这么多内存，array 会稍微快一些，因为它不需要计算哈希值，但它肯定不值得。
我正在从事一个使用自定义数据结构解释选举数据的项目。目前我正在决定哪种数据结构最适合存储有关候选人在不同地区单位获得的最终票数的信息。
由于这是作业，因此禁止使用语言内置的数据结构和来自外部库的数据结构。此外，搜索的复杂度必须小于 O(n)。
我打算使用的散列函数如下所示
密钥类型为 unsigned int 类型，密钥本身就是候选人在选票上的编号。
template<typename K, typename T>
inline int CandidateResultsHashTable<K, T>::hashFunction(const K & key) const
{
return key % (amount_of_candidates + 1);
}
候选人的数量是已知的，但在选举轮次之间可能会发生变化。哈希 table 中存储的所有数据将从一个文件中读取，该文件包含所有候选人的数据。所以不应该有任何不属于候选人的号码。
我想知道，根据访问时间和内存使用情况，哪种实现会更好。
我已将我的评论汇总为一个答案。
这是对实现称为 map（某些其他语言中的字典）的数据结构的不同方法的总结。
key-value 对列表
解决问题的最简单方法是 array/list 对 key-value 对，您只需一对一检查，直到找到正确的密钥。 但是，它的效率非常低。 O(n) 只适用于小数据集。速度并不重要，在数据量非常少的情况下，由于更复杂的数据结构（例如计算哈希函数）的开销，这种方法可能会更快。
如果您对键进行排序并使用仅为 O(log(n)) 的二进制搜索，则可以显着优化此方法。
哈希table
Hash table 实现起来相当棘手。您需要足够好的哈希函数。 好的散列函数意味着它有少量的冲突——当两个不同的键有相同的散列时的情况。无论如何你都需要针对这种情况的程序，但是太多的冲突会减少使用散列的好处 table.
你的实现很简单。
key % (amount_of_candidates + 1)
如果不知道按键是如何分配的，就很难判断它是否足够好。
如果键只是连续的数字就完美了。 （你甚至不需要 + 1。）实际上，在那种情况下你有一个哈希 table 的特殊情况，你不需要检查冲突因为你可以告诉不会有任何。
在这一点上你可以停止假装你使用散列 table 而只是做一个数组;）每个候选人的位置只是 key - smallest_key。事实上，这将是一个非常有效的解决方案：O(1).
如果键是随机分配的，你就不能把它简化那么多。在这种情况下，您的解决方案基本上是好的。但是，(amount_of_candidates + 1) 对于散列 table 来说太小了。它应该比数据量 (load factor) 大 30% 左右。这会将碰撞次数减少到合理的水平。
二叉树
另一种解决方案是使用直接映射到密钥的二进制表示的二叉树。 （0 - 左分支，1 右分支） 这是一种与数组中的二进制搜索非常相似的方法，但它允许轻松添加新元素，而无需调整数组大小并将新元素排序到其中。 该解决方案的缺点是需要更高的内存。
您还可以试验其他类型的二叉树。你只需要记住让它们保持平衡，这样它们就能保持高效。我不太了解平衡，所以我不会在这个话题上写更多。
结论
我推断，在你的情况下，键只是连续的整数，所以我会推荐使用普通数组的解决方案，索引层直接指向键的值。 这是一个非常简单同时非常有效的解决方案。
编辑
好了，下面就按照标题来实际回答一下吧
你展示的完美哈希函数的实现与数组没有什么不同。这只是对同一事物进行编码的另一种方式，并且根据某些因素，结果组装可能是相同的。
对于键分布在整个 K 范围内的其他哈希函数，直接数组将不切实际/无法使用，因为它需要大量内存。如果您成功分配了这么多内存，array 会稍微快一些，因为它不需要计算哈希值，但它肯定不值得。