对于桶排序来说，什么是一个好的哈希函数？

Question

首先，大多数声称实现了 的地方bucket sort实际上都在实现counting sort。我的问题是关于Geek Viewpoint和Wikipediabucket sort上的实现。我不太了解/喜欢 Geek Viewpoint 上的哈希函数，也不太了解 Wikipedia 上的哈希函数。有人可以解释一种更简单的方法来为桶排序创建良好的哈希函数吗？普通人可以理解和记住的东西。

Answer 1

我不认为存在一个通用的好的哈希函数，这就是桶排序的优点。如果散列产生大致相等大小的存储桶，那么它是好的，但这显然取决于要排序的值的分布。这就是为什么当您对分布有先验知识时，例如当您必须按身高对人员记录进行排序时，桶排序会如此有效。

此外，桶排序的最坏情况不是计数排序，正如 Geekview 链接错误地暗示的那样。最坏的情况（关于时间复杂度）是所有元素都进入同一个桶。

当然，计数排序是一种桶排序，特别是带有哈希的桶排序h(x) = x。计数排序的不同之处在于，一旦您知道存储桶仅保存单个值，您实际上并不需要存储桶来存储元素本身，而只需要存储它们的计数。