共计 1589 个字符，预计需要花费 4 分钟才能阅读完成。
线性查找的时间复杂度 O(n)，二分查找为 O(logn)，有没有时间复杂度为 O(1)的查找吗？当然有，这就是散列表。
散列函数
散列函数“将输入映射到数字”。其必须满足一些要求。
它必须是一致的。对于同样的输入，输出必须是一样的。
最理想的情况是, 将不同的输入映射到不同的数字。这样，不同的输入就会映射到不同的位置。
这样就可以使用散列函数将输入映射到数组的不同位置，从而得到一个简单的散列表（hash table）。散列表是目前该书介绍的第一种包含额外逻辑的数据结构。数组和链表都被直接映射到内存, 但散列表更复杂, 它使用散列函数来确定元素的存储位置。散列表由键和值组成，将键映射到值。
同时散列表也被称为散列映射、映射、字典和关联数组。比如，Python 提供的散列表实现为字典。Python 内置字典的用法：
>>> book = dict() # 创建空字典
>>> book[“apple”] = 0.67 # 添加键值对
>>> book[“milk”] = 1.49 # 添加键值对
>>> book[“avocado”] = 1.49 # 添加键值对
>>> print(book) # 打印当前散列表
{‘apple’: 0.67, ‘milk’: 1.49, ‘avocado’: 1.49}
>>> print(book[“avocado”]) # 散列表使用键查找值
1.49
应用案例
将散列表用于查找
通过键快速查找其关联的值。
比如，电话簿姓名为键，电话号码为值
DNS 解析 (DNS resolution) 域名为键，IP 地址为值
防止重复
比如，投票限制每人只能投一票。可以将某人的信息（如，姓名、IP 等）作为键存到散列表内，每次用户投票前，先看看之前有没有投过，没投的话允许投票，并将信息存到散列表内，如果投过票，则不允许再投。
将散列表用作缓存
缓存是一种常用的加速方式, 所有大型网站都使用缓存, 而缓存的数据则存储在散列表中。缓存的工作原理: 网站将数据记住, 而不再重新计算，这样的好处是减少响应的时间，同时也节省了服务器的计算资源。
当访问网站的页面时, 它首先检查散列表中是否存储了该页面。仅当 URL 不在缓存中时, 你才让服务器做些处理, 并将处理生成的数据存储到缓存中, 再返回它。这样, 当下次有人请求该 URL 时, 你就可以直接发送缓存中的数据, 而不用再让服务器进行处理了。
冲突(collision)
最理想的情况是, 散列函数将不同的输入映射到不同的数字，但几乎不可能编写出这样的散列函数。冲突：给两个键分配的位置相同。
处理冲突的方式很多, 最简单的办法如下: 如果两个键映射到了同一个位置, 就在这个位置存储一个链表。
这种处理方式也有可能出现最糟的情况，如，除第一个位置外, 整个散列表都是空的, 而第一个位置包含一个很长的列表，这时查找速度等同于链表的查找速度，会很慢。
好的散列函数很少导致冲突，这样会将键均匀地映射包散列表的不同位置，从而使链表不会太长。
性能
在平均情况下, 散列表执行各种操作的时间都为 O(1)。O(1)被称为常量时间。常量时间并不意味着马上, 而是说不管散列表多大, 所需的时间都相同。在最糟情况下, 散列表所有操作的运行时间都为 O(n)——线性时间。
要避免冲突，需要有：
较低的填装因子；
填装因子 = 散列表包含的元素数 / 位置总数填装因子度量的是散列表中有多少位置是空的。
一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度（resizing）。调整长度需要重新创建新的存储空间，然后使用散列函数将所有的元素都插入到新的散列表内，所以开销较大。但平均而言, 即便考虑到调整长度所需的时间, 散列表操作所需的时间也为 O(1)。
填装因子越低, 发生冲突的可能性越小, 散列表的性能越高。一个不错的经验规则是: 一旦填装因子大于 0.7, 就调整散列表的长度。
良好的散列函数。
良好的散列函数让数组中的值呈均匀分布。糟糕的散列函数让值扎堆, 导致大量的冲突。
请继续关注我的公众号文章
