线性哈希：查找 'min' 和 'max' 的快速方法

Question

我为我的线性哈希实现了一个 min() 和 max() 函数table，但我几乎没有性能问题，因为我直接实现了它。 我只是假设找到的第一个元素是 min/mix 然后我将其余元素与它进行比较。有没有更快的方法 在散列 table 中找到 min/max？我在我的书中找不到任何东西。 我的第二种方法是将每个值写入一个数组，然后查看它，但我不认为这样更快。

Answer 1

通用哈希 table 不是经过排序的元素列表。所以这将是一个 O(n) 操作来找到给定 table 的 min() 和 max()。

Answer 2

同意 Bill Lynch 的意见，我们至少要花 O(n) 一次时间，但是我们可以越懒越好：

• 将 min 和 max 与 table
一起存储
• 只要用户在进行更新，就会根据需要更新 min 和 max
• 删除后，检查删除的项目是否为min或max，如果是，则将标志设置为true，指示最小或最大已更改。如果标志已经设置，则无需检查当前 min/max
• 查找 min/max 后，检查您的标志。如果尚未设置，您可以使用缓存的最小值或最大值。如果已设置，请花费 O(n) 时间重新设置它们。

现在我们只会在需要时花费 O(n) 时间，而不是每次有人请求最少或最多时花费 O(n) 时间。如果插入次数多于删除次数，您通常会看到 O(1) 查找时间。