哈希表

哈希表先将键交给哈希函数，再据所得结果确定桶或候选槽位。读取时重复相同计算，就能缩小需要检查的位置范围。程序仍要保存键与值之间的对应，并使用一致的哈希与相等规则；键的表示怎样处理，会直接影响同一逻辑键能否正确找到已有记录。

参考：[1]

不同键可能得到相同哈希结果，称为冲突。实现可以在同一桶里保存多项，也可以继续探测其他槽位。哈希匹配只是候选条件，必须进一步比较键。若大量键集中在少数位置，访问成本会增加；冲突处理是表的基本组成，而不是只在异常情况下临时补上的步骤。

参考：[2]

随着条目增加，可用槽位和平均桶长度会变化。扩容通常需要重新安排已有键的位置，带来一次较大的工作；负载限制和增长策略帮助平摊这种成本。某次插入可能明显比平常慢，因此讨论平均访问效率时，还要说明负载假设、哈希质量及是否允许对抗性输入。

参考：[1]

哈希组织突出等值查找，通常不会自然保留键的大小顺序。取出某个键的值，与取得一段有序范围，适合的结构可能不同。PostgreSQL的哈希索引支持等值条件，而其B树索引还利用排序关系。两种办法的比较，应从查询类型出发，而不是只比较一个脱离条件的速度数字。

参考：[2]