散列表（也叫哈希表）时根据键（key）而直接访问在内存位置的数据结构。它通过计算一个键值的函数，将需要的数据映射到表中一个位置来访问记录，从而加快了速度，这个映射函数就叫做散列函数，存放记录的数组叫做散列表。
Python中可以字典就是散列表的应用，可以使用dict来创建散列表。字典由key,value组成，散列表将键映射到值。
散列表应用到缓存中：
假设小明的一个侄女问你地球到月球的距离，此时你会去Google下，假如过了几分钟她忘记了这个距离，又再次提问小明，那么此时小明已经记住了这个距离，就不用再去Google了，直接就可以告诉她这个距离，这里我们把Google比作服务器，把小明比作一个缓冲，这样既可以减轻服务器的压力，又可以快速得到你需要的答案，而散列表适合作缓存。
防止重复：
这里介绍一个简单的例子来理解防止重复，假设你负责管理一个投票站，每人只能投一票，那么如何避免重复投票呢？
一般我们会这么做，先把名子写在一张名单上，如果这个人投过票了，那么就拒绝给他再次投票，但是如果很多人投票过后，那么名单会达到很长，接下来有人再来投票需要从名单中查询这个人的名字，你需要浏览很长的名单，这会很糟。更好的办法就是使用散列表，用来记录已投票的人。可以很快速知道是否投过票。
代码如下:
vote = {} #创建散列表
def check_vote(name):
if vote.get(name):
print("%s已经投过票了，不能再次投票了" % name)
else:
vote[name] = True
print("%s可以投票" % name)
check_vote("A")
check_vote('A')
check_vote('B')
#OUTPUT:
A可以投票
A已经投过票了，不能再次投票了
B可以投票
散列表小结：散列表适用于模拟映射关系，防止重复，缓存数据，减轻服务器压力。
冲突：
平均情况下，散列表的查找速度与数组一样快，而插入与删除速度与链表一样快，兼具两者优点。一般来说，只要避开了最糟情况，速度的确很快，为此就需要避免冲突。
避免冲突需要注意下列两点
> 1较低的填充因子（填充因子计算:散列表包含的元素数 / 位置总数）
2 良好的散列函数
散列表使用数组来存储数据，不管元素放在哪个位置，获取的时间都是相同的，当你的数组又20个位置时，如果20个元素都填下去了，而且没有产生冲突。此时填充因子为1， 但是当你元素超过20个了，那么此时你就需要再散列表中添加位置了，添加位置被称为调整长度，当数组越大，元素占用数组位置越少时，填充因子就越小，发生冲突的可能性就越小。一般填充因子大于0.7就需要调整长度了。
小结：
>> 1冲突很糟糕，你应该使用最大限度减少冲突的散列函数
2 散列表的查找，插入，删除都很快
3 散列因子超过0.7，就应该调整长度了
4 散列表适用于数据缓存
5 散列表可用于防止重复
6 散列表占用空间巨大，典型的空间换时间算法
网友评论