散列表(也叫哈希表)是根据键而直接访问在内存存储位置的数据结构,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表,大多数编程语言都提供了散列表的实现,例如Python中的dict,C++中的map。
散列函数
散列函数是这样的函数,既无论你给它什么数据,它都返回一个数字,同时散列函数还遵循两个规则:
- 对于同样的输入数据,返回的数字必须是一样的。
- 对于不同的输入数据,它应该尽可能返回不同的结果。
冲突
对于不同的键,散列函数返回的结果相同,这种情况被称为冲突,这种情况虽然少,但也确实存在。
处理冲突的方法很多,最简单的办法是如果多个键映射到了同一个位置,就在这个位置存储一个链表,在链表里存放冲突的键和值,当查找到冲突的键时去链表里再查一次,由于冲突一般情况下很少,所以链表一般很短,对查找速度影响不大。
性能
散列表的查找,插入,删除的平均时间都很快为O(1),但最差时间为O(n),冲突越多散列表的性能越差,避免冲突需要有较低的填装因子和良好的散列函数。
填装因子指的是散列表包含的元素数除以散列表长度,填装因子越低,发生冲突的可能性越小,一个不错的经验规则是:一旦填装因子大于0.7就调整散列表的长度。不要频繁调整散列表长度,因为它的开销很大。