二次探测法和线性探测法

### 哈希表冲突解决方法：二次探测法 vs 线性探测法 #### 两种探测法概述 线性探测法是一种简单的开放地址法，当发生碰撞时，按照固定的增量顺序寻找下一个可用槽位。具体来说，如果键值k映射到了已被占用的位置i，则尝试位置(i+1)%m, (i+2)%m...直到找到空闲位置为止[^2]。 相比之下，二次探测法采用的是基于平方数列的步长来定位新的候选存储单元。对于初始索引h(k)，后续探查序列为 h(k)+1², h(k)-1², h(k)+2², h(k)-2²,... 这种方式可以减少因连续插入造成的聚集效应[^1]。 #### 性能对比分析 ##### 查找效率方面： - **线性探测法** - 当数据分布较为均匀时表现良好；然而一旦形成局部密集区（即所谓的“堆积”），则会显著增加平均查找长度。 - 能够有效缓解由简单增量带来的簇集问题，从而提高检索速度。不过，由于跳跃式的间隔选取机制可能导致某些区域被过度跳过，反而造成其他地方更易饱和。 ##### 存储利用率角度： - 使用二次探测的情况下，尽管减少了直接相邻项之间的干扰，但如果遇到特定模式的数据输入可能会陷入无限循环而无法完成分配操作。 #### 应用场景建议 针对不同类型的业务需求选择合适的策略至关重要： - 如果应用程序允许一定程度上的性能波动，并且预计不会频繁遭遇大量重复key的情况，那么实现起来更为直观简便的线性探测将是不错的选择。 - 反之，在追求稳定高效的查询响应时间以及面对复杂多变的工作负载环境时，应该优先考虑引入更加灵活稳健的二次探测方案以优化整体性能表现。 ```python def linear_probe(hash_table, key, hash_func): index = hash_func(key) while True: if not hash_table[index]: return index elif hash_table[index].key == key: break else: index = (index + 1) % len(hash_table) def quadratic_probe(hash_table, key, hash_func): i = 0 m = len(hash_table) initial_index = hash_func(key) probe_sequence = lambda j: (initial_index + pow(-1,j)*pow((j//2),2))%m while True: index = probe_sequence(i) if not hash_table[index]: return index elif hash_table[index].key == key: break i += 1 ```