链式哈希表函数平均复杂度及算法正确性咨询

目标 #

使用满足**简单均匀哈希假设（Simple Uniform Hashing Assumption）**的哈希函数h实现链式哈希表，存储数字（同一数字多次插入时，在h(n)对应的链表中多次存储）。需实现三个函数：

• 插入数字n并统计其出现次数
• 删除数字n并统计其出现次数
• 仅统计数字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先在链表头插入元素再调用COUNT统计；DELETE先找到第一个目标元素删除，再统计剩余次数，完全符合需求。
• 平均复杂度：确实是O(1+a)（a为负载因子）。在简单均匀哈希假设下，每个元素被哈希到任意桶的概率相等，每个桶的平均长度为a。COUNT需遍历整个桶链表，平均复杂度O(a)；INSERT的LIST_PREPEND是O(1)，加上后续COUNT的O(a)，整体平均O(1+a)；DELETE的LIST_SEARCH平均O(a)，CHAINED_HASH_DELETE找到指针后是O(1)，加上后续COUNT的O(a)，整体平均也是O(1+a)。

问题2：计数器方案的复杂度与差异 #

• 该方案的平均复杂度确实也是O(1+a)，但理论场景下差异极大：
  • 原方案每次操作后都要遍历整个桶链表统计，最坏情况（比如所有元素都哈希到同一个桶）是O(n)；而计数器方案在插入/删除时仅需对计数器做O(1)的增减，统计次数直接读计数器也是O(1)，无论平均还是最坏情况，实际执行效率都远高于原方案。
  • 只有当负载因子a趋近于0时，两者的实际差异才会很小，只要a有一定规模，计数器方案的优势会非常明显。

内容的提问来源于stack exchange，提问作者selenio34