面试题答案
一键面试1. 开放地址法
- 解决方法：当发生哈希冲突时，通过一定的探测序列在哈希表中寻找下一个空闲位置来存储冲突的数据。常见的探测序列生成方式有线性探测（每次探测间隔为1）、二次探测（探测间隔为1², 2², 3²...）和双重哈希（使用第二个哈希函数来计算探测间隔）。例如，对于线性探测，若哈希值为
h的位置已被占用，则尝试h + 1，若仍被占用则尝试h + 2，以此类推。 - 适用场景：适用于数据量相对较小且哈希表负载因子较低的场景。例如在一些嵌入式系统或轻量级的分布式索引应用中，由于内存和性能限制，开放地址法简单直接的特点能够有效利用有限资源，并且在数据量不大时，哈希冲突概率相对较低，线性探测等方式足以应对。
2. 链地址法（拉链法）
- 解决方法：每个哈希值对应一个链表，当发生哈希冲突时，将冲突的数据插入到对应哈希值的链表中。例如，在分布式索引构建中，若有多个键值对通过哈希函数计算得到相同的哈希值，这些键值对会被依次添加到该哈希值对应的链表上。
- 适用场景：适用于数据量较大且无法准确预估数据规模的场景。在大规模分布式系统中，如搜索引擎的索引构建，数据量巨大且动态变化，链地址法可以灵活地处理大量的哈希冲突，链表的无限扩展性使得系统能够应对不断增长的数据，同时查找、插入和删除操作的平均时间复杂度在合理的哈希函数下可以保持在 O(1) 附近。