HashSet的时间复杂度

Question

我正在和一个朋友讨论使用mod函数作为散列函数的Hashset设计。这种实现的时间复杂度似乎是O(N/K)，其中N是存储在集合中的项目总数，k是存储桶的总数。这个时间复杂度假设所有项目都分布在所有存储桶中，并且存储桶的平均大小为N/K。

我把自己搞糊涂了，因为我相信时间复杂度应该是O(N)。因为时间复杂度是最差的性能。在这里，最坏的情况可能是所有N个项目都进入相同的存储桶，而我们要查找的值可能在存储桶的末尾。请帮帮我。

Answer 1

您说得对，最坏的情况是所有项目都放入一个存储桶中。均匀分布的项目是最好的情况。也就是说，如果k保持不变，则O(N/k)与O(N)相同，因为常数可以忽略。我不希望k成为查找的输入的一部分。如果k可以变化，那么它是不同的，但最坏的情况仍然是O(N)。