【从0到1学算法】散列表
这可能是这么多种数据结构中最有用的-----散列表。
一、什么是散列表
超市中用到的条形码，每个码对应一个商品，扫一下马上就能知道商品的价格，查询速度O（1）。哪种数据结构能做到这样？那只有散列表了。
散列函数
首先需要理解散列函数，散列函数是散列表的灵魂。
散列函数是这样的函数，无论你给他什么数据，它都还给你一个数字。
image
专业点说，就是散列函数“将输入映射到数字”。
散列函数映射数字有这些规则：
1.相同的输入，输出必定也相同。例如，假设输入apple得到4，那每次输入apple得到都是4。
2.不同的输入映射到不同数字。（这是最理想情况）
这有何用途？当然是用来打造散列表。
首先创建一个空数组。
image
我们将在这个数组中存储商品价格。下面将苹果的价格加入这个数组中，输入apple到散列函数。输出为3，因此将苹果价格存储的索引3位置。
image
image
下面将牛奶价格存储到数组中。
image
image
不断重复这个过程，最终将数组填满。
image
现在你想知道鳄梨（avocado）的价格，你无需遍历数组查找，只需将avocado作为输入交给散列函数，它就会帮你找到它。
image
image
这便是散列表，利用散列函数构造的数据结构，能够快速找到想要的数据，理想情况下速度为O（1）。散列表可能是你学习的复杂数据结构中最有用的，也成为散列映射、映射、字典和关联数组。
很多时候你根本不需要自己去实现散列表，在很多优秀语言中都提供了散列表的实现。比如Java中的Map, Python中的字典Dictionary。
二.冲突
前面我们说到，散列函数在理想情况下，不同的输入映射到不同数字。但没有那么多的理想情况，有时候散列函数会发生冲突，这影响着散列表的性能。
假设有这样一个数组，它包含26个位置。
image
而使用的散函数很简单：按字母表顺序分配数组的位置。
image
将苹果价格存储到散列表中，分配的是第一个位置。香蕉则是第二个位置。
image
image
然而，如果要将鳄梨（avocado）存进去，分配的还是第一个位置，可是第一个位置已经放了苹果！这种情况被称为冲突：给两个键分配相同位置。
image
处理冲突的方式有很多，其中最简单是拉链法：如果连个键映射到同一个位置，就在这个位置上存储一个链表。
image
在这个例子中，查询香蕉的价格依然很快，而查询A开头的物品时就慢一些，因为需要遍历链表。如果这个链表很短，那没什么大不了，只需搜索几个元素即可。但是，假设这散列表中只存在以字母A开头的物品，这就很糟糕了！散列表会很慢。
image
这里可得这样的经验教训。
-
散列函数很重要，最坏的情况是所有键都映射到同一个位置，最理想的情况是不同键映射到不同位置。
-
散列表的链表很长，查询速度会急剧下降。良好的散列函数，不会导致很长的链表。
良好的散列函数是避免冲突的关键之一。
三、填装因子
较低的填装因子是避免冲突的关键之二。填装因子计算公式为：散列表包含的元素数/位置总数。例如，下面的散列表的填装因子为2/5=0.4
image
一旦填装因子大到一定程度，就需要在散列表中添加位置，这被称为调整长度。通常会将数组增长一倍。
例如下面这个散列表，规定达到3/4时调整长度。
image
这是需要调整长度，首先创建一个更长的新数组：长度为原来的2倍。
image
接下来，通过散列函数将所有元素插入到这个新数组中。
image
填装因子越低，发生冲突的可能性越小，散列表性能越高。但是填装因子越低，空间利用率就越低，所以需要取平衡。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表长度。
四、应用案例
1.快速查找
在大量的数据中查找想要的信息，散列表是一个不错的选择。
比如电话本，将每个姓名映射到电话号码
image
image
或是DNS解析。在你访问一个网址时，比如http://adit.io，在DNS服务器会将它转换为IP地址。
image
无论访问哪个网址，它都必须转换为IP地址。
image
网址映射到IP地址，这很适合用散列表。
2.防止重复
散列表中每个键只会对应一个位置，无法存储相同的键，这可以起到防重复的效果。
比如，现在需要创建一个投票程序，每个人只能投一票，我们可以用散列表来检查这个人是否已投过票。
image
3.用作缓存
还有一个重要应用：缓存。其中网页缓存，我们应该经常听到。
假设你正在访问Facebook登录页面，这是一个通用的页面，经常会被缓存到你电脑中。当你第二次打开登录页面，你会发现会比第一次打开的速度快，因为你访问的是你电脑中的缓存数据，而从Facebook服务器下载数据。
除了登录页，一般还会存储主页、About页面、Contact页面等等。
而散列表是这样起到缓存作用的：
image
小结
-
散列表可以用散列函数和数组构成。
-
冲突很糟糕，会严重影响散列表的性能。
-
避免冲突的两个关键：
-
良好的散列函数
-
较低的填装因子
- 常见应用
-
快速查找
-
防止重复
-
缓存
如果文章觉得不错，别忘了点赞、评论、转发哦！
文章首发于公众号【KEN DO EVERTHING】
本公众号专注于java相关技术,但不限于java、mysql、python、面试技巧、生活感悟等。分享优质博文,技术干货，学习资源等优质内容。
欢迎关注，一起学习，共成长！
