哈希表

哈希表是根据设定的哈希函数处理冲突的方式,将一系列离散的记录映射到一段有限的、连续的存储空间上

在哈希表中:

由此可见:


构造哈希函数的方法

H(key) = key 或者 H(key) = a * key + b
H(key) = key MOD p, p <= m

构造处理冲突的方式

chainhash.png

查询时,先根据记录的关键字和哈希函数,计算出哈希地址,然后根据哈希地址找到哈希桶,最后再遍历哈希桶。

hashbucket.png

Python 示例

tim-chow 的 Github