哈希表

哈希表用哈希函数 $h(\text{key})$ 算出存放的位置。两个键落到同一个位置叫冲突,常见的处理是链地址(同一位置挂一条链)和开放寻址(按规则找下一个空位)。

性能取决于装载因子、哈希函数的质量和冲突的处理方式。平均是 $O(1)$,最坏情况不是:所有键都冲突时退化成线性查找。

衡量查找性能常用平均查找长度:查询对象 $i$ 的概率是 $p_i$、比较次数是 $c_i$,

一个典型用法是和 前缀和 配合,统计和为 $T$ 的子数组个数。

用到它的地方

• 知识库 前缀和与差分

核对

这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。