什么是一个好的哈希函数桶排序？

Question

首先，大多数声称拥有bucket sort实现的地方实际上都在实现counting sort。我的问题是关于bucket sort在极客观点和维基百科上实现的问题。我不太喜欢Geek Viewpoint上的散列函数，也不喜欢维基百科上的哈希函数。有人能解释一种更简单的方法来为桶排序创建一个好的散列函数吗？一般人能理解和记得的东西。

Answer 1

我不认为有一个普遍的好的哈希函数，那是桶类的捕获。如果哈希产生的大小大致相同，那么哈希是很好的，但这显然取决于要排序的值的分布。这就是为什么当你对分布的先验知识，例如当你必须根据人的身高对记录进行排序时，桶排序工作得那么好的原因。

此外，桶排序的最坏情况不是计数排序，正如Geekview链接错误地指出的那样。最糟糕的情况(关于时间复杂性)是当所有元素都进入同一个桶时。

当然，计数排序是--一种桶排序，特别是带有散列h(x) = x的桶排序。计数排序的不同之处在于，一旦您知道您的存储桶只保存了一个值，您就不需要存储元素本身，只需要存储它们的计数。