算法图解 - 散列表

🏷️ 《算法图解》

散列函数

• 将输入映射到数字

• 散列函数必须满足以下要求

  1. 它必须是一直的。即相同的输入总是映射到相同的数字。

  2. 它应将不同的输入映射到不同的数字。

散列表 (hash table)

• 结合使用散列函数和数组

• 散列表也被成为散列映射,映射,字典和关联数组.

• 散列表适用于

  1. 模拟映射关系

  2. 防止重复

  3. 缓存/记住数据,以免服务器再通过处理还生成它们

性能

	散列表 (平均情况)	散列表 (最糟情况)	数组	链表
查找	$O(1)$	$O(n)$	$O(1)$	$O(n)$
插入	$O(1)$	$O(n)$	$O(n)$	$O(1)$
删除	$O(1)$	$O(n)$	$O(n)$	$O(1)$

• 在平均情况下，散列表的查找速度和数组一样快，而插入和删除则和链表一样快

• 在最糟情况下，散列表的各种操作的速度都很慢

• 为避免最糟情况，需要有：

  • 较好的填装因子

  • 良好的散列函数

填装因子

• 填装因子 = 散列表包含的元素数 / 位置总数

• 度量的是散列表中有多少位置是空的

• 经验规则 : 一旦填装因子大于 0.7，就调整散列表的长度

散列函数

• 良好的散列函数让数组中的值呈均匀分布,降低冲突产生的几率