algorithm - 哈希表和链接方法

Question

在我的哈希表中，每个列表都进行了排序（链接方法）。1.这将如何影响搜索现有密钥的运行时间 2.这将如何影响搜索丢失密钥的运行时间？3.这将如何影响添加和删除密钥的搜索时间？

标签： algorithmhashtable

Answer 1

1.这将如何影响搜索现有密钥的运行时间。

没那么多，因为碰撞很少发生。

N 是哈希表的大小，M 是碰撞次数。

M 通常太小（从 0-50 ），因此速度没有太大变化。

如果 M 太大且接近 N，在这种情况下，我们的哈希算法很差，应该改进。

如果你有一个糟糕的散列算法，最坏的情况 M=N，所以你有一个复杂度为 O(Log N) 的二进制搜索。

哈希表的好处被破坏了。退化 O(1) -> O(Log N)

所以无论如何我们都应该避免它。

2.这将如何影响搜索缺失键的运行时间。

与 1 的答案相同。M 通常很小，如果不是，请重写您的哈希算法。