索引与散列：两种快速定位记录的策略

当记录不能按处理顺序原样存放、又需要快速按键值检索时，有两种经典策略：索引文件维护一份”键值→存储位置”的对照表（类似书本的索引页），检索时先查这张表再跳转到对应位置，代价是要额外维护和存储这份索引本身；散列文件则完全跳过”查表”这一步，用一个散列函数直接把键值计算成存储位置（桶号），检索时对键值重新计算一次同样的函数就能直接定位，理论上不需要额外的索引结构。但散列不是没有代价：如果散列函数设计不当（比如把桶数选成一个键值们共享的公因数），大量键会挤进同一个桶，这种聚类现象会拖累性能；而且哪怕散列函数设计良好，键值数量增加时碰撞（不同键算出同一个桶号）在数学上几乎必然发生——负载因子（已用记录数占总容量的比例）一旦超过约 50%，性能就开始明显下降，超过 75% 往往需要整体重建更大容量的散列系统。发散：索引和散列的取舍，本质是”额外维护一份查找辅助结构”与”靠计算直接换算位置”这两种加速检索思路的对照，后者更快但脆弱（容易受键值分布特征影响导致聚类），这也是为什么现实的存储系统常常两者结合——用散列做初步的快速定位，再在桶内部用索引或线性搜索处理少量的碰撞。