寻找哈希函数的摊销复杂度

Question

我在复习期末考试时遇到了这个问题。
对于1a，我认为它的摊销复杂度是O(1)，因为它采用x mod N方法进行稀疏化，并使用线性探查来处理插入失败的情况。但我不确定如何精确地陈述或证明这一点。

对于1b，如果散列到同一个位置，每次插入时都会进行线性探查，但我也不确定如何从中推导出运行时间。

- user1879789

Answer 1

[编辑，我的原始分析是针对开放式哈希而不是开放式地址] 对于1a），h（x）= x mod N，n＜N，因此哈希值将为0，1，...，n-2，0。除了最后一个之外，所有插入都将无冲突。最后一个插入将使用线性探测。第一个探测到桶0，但它被占用且键不同。下一个探测在插槽1，结果相同，直到它达到第一个空桶（n-1）。因此，您需要（n-1）个额外操作，总计为（2n-1）。平摊成本为每个插入（2n-1）/ n。

对于1b），哈希表退化为链接列表。插入线性增长，有n个插入，因此总共有（n + 1）* n / 2次操作。即每次插入为（n + 1）/ 2。

- mornfall

---

这并不是真的，因为N将会与0相撞，然后你将值增加1，它将会与1相撞，以此类推。总共会发生（n-1）次碰撞。 - notbad

啊，糟糕，开放地址法（也称闭散列）。呃。你当然是对的。 - mornfall

Answer 2

1a、除了最后一次（N将与每个值碰撞，即N将首先与0碰撞，然后您将增加该值1，它将与1发生碰撞，依此类推），将完全没有碰撞，总成本将为1 + 1 + ... + 1 + n =（n-1次）+ n = 2n-1，摊销成本将为（2n-1）/ n，使用大O符号表示为O（1）。

1b、对于第i个插入，将有（i-1）次碰撞，加上插入操作，第i个操作的成本将为i。因此，总成本将为1 + 2 + ... + n-2 + n-1 + n =（n + 1）* n / 2，您已经插入了n次，摊销成本将为（n + 1）/ 2。

- notbad

---

你应该澄清1a)（因为线性解决方案链来自闭散列，而使用开放散列它将是一个常数）。 - mornfall

@mornfall 开放寻址和闭合寻址不同吗？我以为它们是同义词 :) http://en.wikipedia.org/wiki/Open_addressing - notbad

开放地址法与闭散列法相同。闭散列法与开放地址法相同。开放地址法意味着每个桶只有一个键，并且冲突根据探测序列存储在其他位置。闭散列法意味着使用链表或其他方式将多个键存储在单个桶中。 - mornfall