《算法图解》读书笔记5-散列函数及扩展
algorithms Linux散列函数
散列函数就是一种映射,是从关键字到存储地址的映射。通常,包含散列函数的算法的算法复杂度都为 O(1),对应到 Python 中的数据结构就是字典,给一个 key 可以得到一个固定的 value 值。散列函数必须满足一些要求:
- 它必须是一直的。例如,假设输入 apple 时得到的是 4,那么每次输入 apple 时,都必须是 4,不然这个散列函数就是无意义的;
- 散列函数应该将不同的输入值,对应到不同的值上。(虽然不同的 key 对应相同的 value 是允许的,但最理想的情况是不同的 key,对应不同的 value,这种称之为完美散列)