本篇将介绍散列表（哈希表）的相关基础知识。
一、简介
散列表(Hash table，也叫哈希表)是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。
二、内部机制
2.1 散列函数：
散列函数：简单来说是一个函数，传入一个Key就返回一个固定的数。该数即为散列表数组的下标。（用一句话描述：散列函数将“输入”映射到“数字”。）
2.2 解决冲突：
对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突(碰撞)。
常见的解决哈希冲突方案有以下四种：（详细细节见下篇讲解）
-
开放定址法：为产生冲突的地址
H(key)求得一个新的地址序列：
Hi =（H(key)+ di）% m（i=1，2，3，...，m-1）
其中H(key)为哈希函数，m为表长，di称为增量序列。（其中增量di的取值方法也有多种，详细细节见下篇） -
链地址法：将所有哈希地址相同的记录都链接在同一链表中。
-
再哈希法：产生冲突时计算另一个哈希函数（散列函数）的地址，直到冲突不再发生为止。
-
建立公共溢出区：把冲突的值都放在另一个溢出表中，不把冲突的值存原表中。
三、性能对比
先介绍一个散列表的专有名词：填装因子（负载因子）。
这里列出了常见数据结构操作的时间复杂度。
| / | 散列表（平均情况） | 散列表（最坏情况） | 数组 | 链表 |
|---|---|---|---|---|
| 取值 | O(1) | O(n) | O(1) | O(n) |
| 插入 | O(1) | O(n) | O(n) | O(1) |
| 删除 | O(1) | O(n) | O(n) | O(1) |
可以看出散列表在平均情况下的性能是很出色的，虽然最坏情况的性能不好，但我们可以通过一些手段避免掉最坏情况。因此，散列表的最优情况就是平均情况，时间复杂度为常数级O(1)。
因此，散列表在使用中需要注意两点：
- 较低的填装因子（或称负载因子）。（建议：高于
0.7时，考虑散列表翻倍扩容） - 优秀的散列函数。（尽量减少冲突的发生）
PS：Python的做法是，会设法保证大概还有三分之一的表元是空的，当快要达到这个阀值的时候，会进行扩容，将原散列表复制到一个更大的散列表里。
四、应用场景
散列表应用广泛，下面介绍几种常见的应用场景。
4.1 散列表用于查找
例如，用散列表实现一个电话薄。
主要功能如下：
- 加入联系人及电话号码。
- 通过输入联系人来得出电话号码。
iphone_telBook = dict()
iphone_telBook["police"] = 110
iphone_telBook["647"] = 138888888
print iphone_telBook["police"]
print iphone_telBook["647"]
4.2 防止重复
例如，做一个投票系统，每个用户id只能投一次。
如果用数组或链表，那么查询或插入的时间就会比较多。这时，我们就可以考虑使用散列表。
主要功能如下：
- 支持投票，加入用户id与被投票者名单。
- 查询并判断id是否已投过。投过就打印fail，没投过就打印success。
voted = dict()
def check_voter(id):
if voted.get(id):
print "failed"
else:
print "success"
check_voter(01)
voted[01] = 01
check_voter(01)
4.3 散列表用于缓存
例如，访问一个网站，
会经历如下几个步骤：
- 向该网站的服务器发送请求。
- 服务器做一些处理，生成一个网页并将其发送给你。（可做缓存）
- 你看到了一个网页。
实际上，每次重复的请求都可以做缓存，
下一次发同样请求时就可以直接展示网站，不用再由服务器做一些处理。
缓存是一种常用的加速方式，使用户能够更快的看到网页，同时也减轻了服务端的重复工作量。而这些缓存的数据就存储在散列表中。
模仿代码如下：
cache = dict()
def get_data_from_server(url):
print "server did some thing here"
def get_page(url):
if cache.get(url):
return cache[url]
else:
data = get_data_from_server(url)
cache[url] = data
return data
cache["www.so.com"] = "360so"
cache["www.baidu.com"] = "baidu"
print get_page("www.so.com")
网友评论