面试题：C语言哈希表多场景适配与算法融合

Question

在C语言环境下，假设有一个需要处理海量数据的哈希表应用场景，且数据分布不均匀。同时，该应用对插入、查找和删除操作的时间复杂度都有严格要求。请设计一种融合多种碰撞解决算法（如链地址法、线性探测法、二次探测法）的哈希表结构，阐述设计思路，并给出关键操作（插入、查找、删除）的伪代码实现，同时分析该设计在不同操作上的时间复杂度和空间复杂度。

Answer 1

设计思路

1. 整体结构：采用数组和链表相结合的方式。数组作为哈希表的主体，每个数组元素是一个链表头指针。这样可以综合链地址法处理冲突的优点。
2. 冲突解决策略：
   • 链地址法：当发生冲突时，使用链表来存储冲突的元素。
   • 线性探测法与二次探测法辅助：对于链表中的元素，当链表长度超过一定阈值（如8）时，切换到线性探测法或二次探测法，在数组中寻找空闲位置存储新元素。这是因为数据分布不均匀，链表过长会导致查找、插入和删除操作性能下降。

关键操作伪代码实现

插入操作

function insert(key, value)
    index = hash_function(key)
    if hash_table[index] is empty
        create new node with key and value
        hash_table[index] = new_node
    else
        current = hash_table[index]
        list_length = 0
        while current is not null
            if current.key == key
                current.value = value
                return
            current = current.next
            list_length++
        end while
        if list_length < threshold
            create new node with key and value
            append new_node to hash_table[index]'s list
        else
            // 线性探测法
            new_index = index
            while hash_table[new_index] is not empty
                new_index = (new_index + 1) % table_size
            end while
            create new node with key and value
            hash_table[new_index] = new_node
        end if
    end if
end function

查找操作

function search(key)
    index = hash_function(key)
    current = hash_table[index]
    while current is not null
        if current.key == key
            return current.value
        current = current.next
    end while
    // 线性探测法查找
    new_index = index
    while hash_table[new_index] is not empty
        if hash_table[new_index].key == key
            return hash_table[new_index].value
        new_index = (new_index + 1) % table_size
    end while
    return null // 未找到
end function

删除操作

function delete(key)
    index = hash_function(key)
    prev = null
    current = hash_table[index]
    while current is not null
        if current.key == key
            if prev is null
                hash_table[index] = current.next
            else
                prev.next = current.next
            end if
            free current
            return
        prev = current
        current = current.next
    end while
    // 线性探测法删除
    new_index = index
    while hash_table[new_index] is not empty
        if hash_table[new_index].key == key
            hash_table[new_index] = null
            return
        new_index = (new_index + 1) % table_size
    end while
end function

时间复杂度分析

1. 插入操作：
   • 平均情况下，假设哈希函数均匀分布，未达到链表阈值时，插入操作时间复杂度为 $O(1)$。
   • 当链表长度超过阈值切换到线性探测法时，最坏情况下时间复杂度为 $O(n)$，其中 $n$ 为哈希表大小。平均情况下仍接近 $O(1)$，因为数据分布不均匀但整体有哈希函数的分散作用。
2. 查找操作：
   • 平均情况下，未达到链表阈值时，查找操作时间复杂度为 $O(1)$。
   • 当链表长度超过阈值切换到线性探测法时，最坏情况下时间复杂度为 $O(n)$，平均情况下接近 $O(1)$。
3. 删除操作：
   • 平均情况下，未达到链表阈值时，删除操作时间复杂度为 $O(1)$。
   • 当链表长度超过阈值切换到线性探测法时，最坏情况下时间复杂度为 $O(n)$，平均情况下接近 $O(1)$。

空间复杂度分析

1. 空间复杂度：哈希表本身需要 $O(n)$ 的空间，其中 $n$ 为哈希表大小。
2. 链表额外空间：在数据分布不均匀情况下，链表存储冲突元素，最坏情况下链表长度总和可能达到 $O(m)$，其中 $m$ 为元素总数。所以整体空间复杂度为 $O(n + m)$。