散列表——最有用的基本数据结构之一，用途广泛。
散列表的内部机制：实现、冲突和散列函数。
假设你在一家杂货店上班。有顾客来买东西时，你得在一个本子中查找价格。如果本子的内容不是按字母顺序排列的，你可能为查找苹果 （apple）的价格而浏览每一行，这需要很长的时间。
散列函数
无论你给它什么数据，它都还你一个数字。散列函数
将输入映射到数字
实散列函数必须满足一些要求。它必须是一致的。
最理想的情况是，将不同的输入映射到不同的数字。
散列表 （hash table）的数据结构。种包含额外逻辑的数据结构。
数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的存储位置。
散列表由
键和值组成。
将散列表用于查找
假设你要创建一个类似这样的电话簿，将姓名映射到电话号码。该电话簿需要提供如下功能。添加联系人及其电话号码。通过输入联系人来获悉其电话号码。
phone_book = dict()
phone_book["jenny"] = 8675309
phone_book["emergency"] = 911
print phone_book["jenny"]
#8675309
如果要求你使用数组来创建电话簿，你将如何做呢？
散列表被用于大海捞针式的查找。访问网站时，计算机必须将adit.io转换为IP地址。无论你访问哪个网站，其网址都必须转换为IP地址。这不是将网址映射到IP地址吗？好像非常适合使用散列表啰！这个过程被称为DNS解析 （DNS resolution），散列表是提供这种功能的方式之一。
防止重复
假设你负责管理一个投票站。显然，每人只能投一票，但如何避免重复投票呢？有人来投票时，你询问他的全名，并将其与已投票者名单进行比对。如果名字在名单中，就说明这个人投过票了，因此将他拒之门外！
voted = {}
def check_voter(name):
if voted.get(name):
print "kick them out!"
else:
voted[name] = True
print "let them vote!"
将散列表用作缓存
假设你访问网站facebook.com。
(1) 你向Facebook的服务器发出请求。
(2) 服务器做些处理，生成一个网页并将其发送给你。
(3) 你获得一个网页。
缓存的工作原理：网站将数据记住，而不再重新计算。
缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中！
当你访问Facebook的页面时，它首先检查散列表中是否存储了该页面。
cache = {}
def get_page(url):
if cache.get(url):
return cache[url] # 返回缓存的数据
else:
data = get_data_from_server(url)
cache[url] = data # 先将数据保存到缓存中
return data
冲突
给两个键分配的位置相同，这种情况被称为
冲突（collision）：
如果两个键映射到了同一个位置，就在这个位置存储一个链表。
散列函数将所有的键都映射到一个位置，而最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。
着无论散列表包含一个元素还是10亿个元素，从其中获取数据所需的时间都相同。
而要避免冲突，需要有：
- 较低的填装因子；
- 良好的散列函数。
填装因子
散列表的填装因子很容易计算。散列表使用数组来存储数据，因此你需要计算数组中被占用的位置数。
填装因子度量的是散列表中有多少位置是空的。
填装因子大于1意味着商品数量超过了数组的位置数。一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度。
填装因子越低，发生冲突的可能性越小，散列表的性能越高。
一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。
良好的散列函数
良好的散列函数让数组中的值呈均匀分布。糟糕的散列函数让值扎堆，导致大量的冲突。
什么样的散列函数是良好的呢？你根本不用操心——天塌下来有高个子顶着。
网友评论