哈希索引的冲突消解策略与负载因子权衡

哈希索引把关键字通过哈希函数直接映射成存储地址，插入删除修改的 理想时间复杂度是O(1)，但代价是完全丢失顺序信息（只支持等值查询， 范围查询、排序扫描效率和无序表相同）。真正决定哈希索引好不好用的， 是冲突（不同关键字映射到同一地址）发生后怎么处理，处理思路分两大类。 内消解法在哈希表本身的存储区域内解决冲突：线性探查法从冲突位置起 逐个往后找空位插入；双哈希探查法用第二个哈希函数决定探查步长， 让冲突后的查找路径分散得更均匀，减少”扎堆”现象——但内消解法的共同 局限是存储区域大小固定，随着数据填满存储区，冲突只会越来越频繁， 无法从根本上缓解。外消解法在哈希表存储区之外解决冲突：溢出区法给 冲突的数据另开一块空间顺序存放，溢出量小时效率尚可，溢出量大时性能 急剧下降；链地址法把哈希值相同的数据组织成链表挂在对应位置，应用 最广泛，因为链表可以无限延伸、不受固定存储区大小限制。衡量哈希表 “满”的程度用负载因子（已存储数据项数/存储区可容纳数据项数）表示： 负载因子太小意味着空间浪费，太大意味着冲突频发、增删改查效率骤降， 内消解法通常要求负载因子不超过0.7，而外消解法里负载因子本质等价于 链表平均长度，理论上可以容忍更大的负载因子，但链表过长时查询时间会 退化成链表长度的线性函数。

结构图：

flowchart TD
    A[哈希冲突消解] --> B[内消解法<br/>在固定存储区内解决]
    A --> C[外消解法<br/>用额外空间解决]
    B --> B1[线性探查法: 逐个往后找空位]
    B --> B2[双哈希探查法: 第二哈希函数决定步长]
    C --> C1[溢出区法: 冲突数据存入独立溢出区]
    C --> C2[链地址法: 相同哈希值组成链表]
    B1 -.负载因子建议不超过0.7.-> D[数据填满后冲突必然加剧]
    C2 -.负载因子约等于链表平均长度.-> E[理论上可容忍更大负载因子]