【算法图解】散列表

散列表

当要快速查找一样水果的价格时，可以用前面所学的二分查找来进行查找，但是二分查找的运行时间虽然为O(log n)但是总归会随着元素数量增加而拖慢查找速度。

所以数据结构中引入了散列表,散列表的运行时间始终为O(1)，是比较理想的数据存储方式。

散列表的数据存储原理如下：

1. 创建一个合适的空数组。
2. 将输入的值用链表的方式加入数组中。
3. 如果散列表中填装因子过大，则扩大数组（一般扩大两倍）。

以上所说的填装因子为：（散列表包含的元素数/位置总数）一般填装因子临界值设置为0.7。

回到一开始的问题，假如苹果价钱是0.67，牛奶的价格是1.49，鳄梨价格是1.49，要快速查找各个水果价格可以用散列表。

虽然散列表自己实现比较难，但是任何主流语言都提供了散列表的实现，python提供的散列表实现为字典。

>>>book = dict()
>>>book["apple"] = 0.67
>>>book["milk"] = 1.49
>>>book["avocado"] + 1.49
>>>print book

如果要查询鳄梨的价格，我们只需输入print book["avocado"]即可。

散列表的应用

用于查找

手机内置电话簿就可使用散列表实现，具体实现代码如下：

>>>phone_book = dict() #亦可使用phone_book = {}
>>>phone_book["jenny"] = 8675309
>>>phone_book["emergency"] = 110

现在要查找jenny的电话号码，只需输入print phone_book["jenny"]即可得出jenny的电话号。

还有DNS解析也使用了散列表。

防止重复

投票中，要知道一个人是否已经投过票需要查找一串长长的名单，但是运用散列表就可以很快的查处一个人是否已经投过票。

voted = {}

def check_voter(name):
    if voted.get(name):
        print "kick him out!"
    else:
        voted[name] = True
        print "let him vote!"

check_voter("tom")
check_voter("mike")
check_voter("tom")

输出结果为：

let him vote!
let him vote!
kick him out!

如果存储在列表中，运用简单查找速度将非常慢，存储在散列表中，查询速度非常快。

用于缓存

当你第一次进入网页时，服务器需要做大量的查找工作，如果每次进网页都交由服务器处理，那么服务器将不堪重负，所以当你第一次进入网页中时，服务器处理后会生成一个散列表在缓存上，当你再次进入相同的页面时，就不用通过服务器处理，直接调用散列表中的缓存的数据就可以快速访问网页，大大提高了服务器的运行效率。

具体代码如下：

cache = {}
def get_page(url):
	if cache.get(url):
		return cache[url]
	else:
		data = get_data_from_server(url)
		cache[url] = data
		return data

散列表性能

根据散列表特性，最好的情况为O(1),最坏的情况为O(n),所以当填装因子过大时，为了防止冲突，我们需要对散列表进行扩容，虽然调整散列表长度开销很大，但是就整体而言，散列表的整体运行时间依然是O(1)。

散列函数

散列函数作为非基础模块，本章不做解释，具体可以了解SHA函数和MD5算法。