在之前我们已经学过了二分查找和简单查找，我们知道二分查找的运行时间为O(㏒ n)， 简单查找的运行时间为O(n)。除此之外，还有没有更快的查找算法呢？
可能有人会说数组的查找速度更快，查找速度为O(1)。没错，但是我们今天讲的是一种进化版的类似于数组的数据结构--散列表。
散列表的性能取决于散列函数，那什么是散列函数呢？
散列函数
散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。专业术语来描述就是：将输入映射到数字。
散列函数需要满足一些要求：
-
它必须是一致性的，就是同样的输入必须映射到相同的数字。
-
它应该将不同的输入映射到不同的数字。但绝大多数情况是达不到这种要求的，这就产生了冲突。关于冲突的介绍，后面再讲。
散列函数和数组结合在一起就创建了一种名为散列表的数据结构。散列表是一种包含额外逻辑的数据结构。数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。
几乎每种语言都提供了散列表的实现方式。Python提供的散列表实现为字典，我们可以使用函数dict()来创建散列表。
>>> book = dict()
对了， Python还提供另一种创建散列表的快捷方式--使用大括号
>>> book = {}
以上两种方式是等效的。
现在创建了散列表后，在其中添加一些商品的价格。
>>> book = dict()
>>> book["apple"] = 8
>>> book["banana"] = 5
>>> book["milk"] = 4
>>> print(book)
{'apple': 8, 'banana': 5, 'milk': 4}
现在我们来查询香蕉的价格：
>>> print (book["banana"])
5
这就实现了一个简单的散列表。
散列表由键和值组成，散列函数将键映射到值。在Python中使用字典来实现散列表，如果对字典不太熟悉的同学，可以看我以前关于字典的文章：Python基础学习-字典
散列表的应用
将散列表用于查找
散列表被用于大海捞针式的查找。当我们访问一个网站的时候，我们输入类似于：www.baidu.com这样的域名，然后通过DNS解析到一个IP地址。这里将网站地址映射到IP地址，就是运用了散列表的功能。
将散列表用作缓存
缓存是一种常用了加速方式，它可以使用我们浏览网站更加快速，所有的大型网站都使用缓存，而缓存的数据则是存储在散列表中的。其基本原理是将页面url映射到页面数据。
冲突
由于大多数语言都提供了散列表的实现方式，所以我们可以不必深究散列表的内部实现原理，但我们必须要考虑散列表的性能。
关于散列表的性能我们首先要了解一个名为冲突的概念。理想的情况是散列函数总将不同的输入映射到数组的不同位置，但实际上，几乎没有这样的散列函数。我们来看一个示例，假设有一个数组，它包含了26个位置：
使用的散列函数非常简单，它按照字母表顺序分配数组的位置。先将苹果的价格存储到散列表中，分配给第一个位置：
接下来将香蕉的价格存储到散列表中，分配给第二个位置：
接下来再将杏仁的价格存储在散列表中，由于杏仁的英文单词为apricot，分配给它的又是第一个位置：
但是这个位置已经存储了苹果的价格，怎么办？这种情况被称为冲突：给两个键分配了相同的位置。
处理冲突的方式有很多，最简单的一种就是在发生冲突的位置存储一个链表：
所以，一个好的散列函数对于散列表的性能尤其重要。
性能
在平均情况下，散列表执行各项操作的时间都为O(1)。O(1)被称为常量时间。
简单查找的运行时间为线性时间：
二分查找的所需时间为对数时间：
在散列表中查找所花费的时间为常量时间：
在最糟情况下，散列表所有的操作的运行时间都为O(n)--线性时间。下面将散列表同数组和链表比较一下：
为了避免冲突，需要有：
-
较低的填装因子
-
良好的散列函数
填装因子
散列表的填装因子很容易计算：
填装因子越低，发生冲突的可能性越小，散列表的性能越高，一个不错的经验是：一旦填装因子大于0.7，就调整散列表的长度。
良好的散列函数
良好的散列函数可以使数组中的值呈均匀分布。什么样散列函数是良好的呢，有兴趣的话，可以去研究一下SHA函数。这里不做介绍，因为我也不懂~
小结
-
在Python中使用字典来实现散列表
-
散列表的查找、插入和删除都很快
-
散列表适合于模拟映射关系
-
散列表可用于缓存数据
-
一旦填装因子超过0.7，就该调整散列表的长度
每天学习一点点，每天进步一点点。
网友评论