哈希表函数的平均复杂度

Question

目标

目标是使用一个链式哈希表，其哈希函数h满足简单统一哈希假设，来存储一些数字（同一个数字，如果插入多次，会在与h关联的链表中多次存储（ n))。 我们要实现 3 个函数：一个插入一个新数字 n 并计算该数字出现的次数，一个删除一个数字并计算该数字出现的次数，一个仅计算该数字出现的次数.

注释

我们必须使用伪代码（类似于Python），并且可以使用方法“.head”返回链表的头，以及函数LIST_PREPEND、LIST_SEARCH在前面添加一个项目（作为指针给出）并搜索一个键（返回关联指针）在链表中。我们还可以使用 CHAINED_HASH_DELETE 从与其关联的链表中删除一个项目（作为指针给出）。请注意，变量 x 始终表示指向哈希表的链表之一中的一项的指针，n 始终是一个整数，我们将其用作键，M 是链式哈希表。语法和“编程”其实并不重要，重要的是算法。

我的代码

COUNT(M, n): 
    count = 0
    x = M[h(n)].head
    if x == NIL: #the linked list is empty
        return 0
    else:
        while x != NIL: #search the list until its end
            if x.key == n:
                count = count + 1
            x = x.next
        return count

DELETE(M, n)
    x = LIST_SEARCH(M[h(n)], n)
    CHAINED_HASH_DELETE(M, x)
    COUNT(M, n)

INSERT(M, n):
    <let x be a pointer to n>
    LIST_PREPEND(M[h(n)], x)
    COUNT(M, n)

我的问题

1. 我的代码背后的想法可能有点低效，因为每次我都必须重新计算出现的次数。但是，所有函数（COUNT、INSERT、DELETE）的平均复杂度无论如何都应该是 O(1+a)，其中 a 是负载因子，因为 LIST_SEARCH 和 COUNT 的复杂度为 O(1+a)。平均复杂度正确吗？算法本身正确吗？

2. 另一种解决方案是在 M[h(n)] 中链表的第一项上使用属性 .counter，并在每次插入或删除项目时加 1 或减 1。由于最终的复杂性也是 O(1+a)，因为我必须找到第一个等于 n 的项，所以在理论场景中这应该不重要，对吗？

Answer 1

哈希本质上是确定性的。但是，我们可以使用概率分析来了解在键均匀分布的假设下哈希表操作的平均情况性能。

用α=N/M表示负载因子，其中N是哈希表中的条目数，M是桶的数量。在 SUHA 下，每个键同样有可能散列到任何存储桶。因此，我们希望键均匀分布在各个存储桶中。平均每个桶会有 α 个条目，因此查找、插入和删除的平均时间复杂度为 O(1 + α)。您可能会发现这篇文章简单统一哈希假设和哈希表的最坏情况复杂性很有洞察力，它提供了对 SUHA 的不同看法。

但是，这个结果意味着，如果哈希表的大小 M 至少与表中元素的数量 N 成正比，则 N = O(M)。因此，α = N/M = O(M)/M = O(1)，查找平均需要 O(1)。因此，对于 O(1) 查找性能，α 应以一个小常数为界，最好低于 1。

如果α增长超出可接受的限度，我们可能会选择重新散列哈希表。这涉及扩大表的大小并将现有条目重新插入到新的更大的表中。由于 M 相对于 N 变大，因此负载系数 α 相应减小。

对于第二个问题，您可以将计数函数的成本保持在 O(1)，所以就这样做。通过在链表的第一项上使用 .counter 属性，您可以在每次插入或删除项目时加 1 或减 1。