自适应文章网站模板,pc端网站优缺点,门户网站报价方案,the7企业中/英文wordpress模板文章目录问题散列函数应用案例将散列表用于查找防止重复将散列表用作缓存冲突性能装填因子良好的散列函数小结问题
你在一家杂货店上班。有顾客来买东西时#xff0c;你得在一个本子中查找价格。
如果本子的内容不是按字母顺序排列的#xff0c;你可能为查找苹果#xff0…
文章目录问题散列函数应用案例将散列表用于查找防止重复将散列表用作缓存冲突性能装填因子良好的散列函数小结问题
你在一家杂货店上班。有顾客来买东西时你得在一个本子中查找价格。
如果本子的内容不是按字母顺序排列的你可能为查找苹果apple的价格而浏览每一行这需要很长的时间。使用的是简单查找需要浏览每一行。时间复杂度为O(n)O(n)O(n)。
如果本子的内容是按字母顺序排列的可使用二分查找来找出苹果的价格这需要的时间更短为O(logn)O(log n)O(logn)。
前面介绍了两种用于查找的数据结构数组和链表为了针对上面的问题有个更快的查找方式引入散列表。查找时使用散列函数。
散列函数
散列函数是这样的函数即无论你给它什么数据它都还你一个数字。用专业术语来表达的话我们会说散列函数“将输入映射到数字”。
需要满足的要求
单一映射对于同样的输入总能得到相同的输出。应将不同的输入映射到不同的数字。可逆函数
对于上面的问题使用散列表来解决首先创建一个空数组。在这个数组中存储商品价格。如苹果价格为此将apple作为输入交给散列函数散列函数输出为数组索引根据索引我们就能找到对应位置苹果的价格。
散列函数准确地指出了价格的存储位置你根本不用查找之所以能做到原因有
散列函数总是将同样的输入映射到相同的索引。每次你输入avocado得到的都是同一个数字。因此你可首先使用它来确定将鳄梨的价格存储在什么地方并在以后使用它来确定鳄梨的价格存储在什么地方。散列函数将不同的输入映射到不同的索引。avocado映射到索引4milk映射到索引0。每种商品都映射到数组的不同位置让你能够将其价格存储到这里。散列函数知道数组有多大只返回有效的索引。如果数组包含5个元素散列函数就不会返回无效索引100
不同于数组和链表都被直接映射到内存散列表更复杂它使用散列函数来确定元素的存储位置。
散列表也被称为散列映射、映射、字典和关联数组。
应用案例
将散列表用于查找
创建一个话簿每个姓名都有对应的电话号码需要提供如下功能
添加联系人及其电话号码。通过输入联系人来获悉其电话号码。
这非常适合使用散列表来实现在下述情况下使用散列表是很不错的选择。
创建映射。查找。
创建电话簿非常容易。首先新建一个散列表。
phone_book dict()Python还提供了一种创建散列表的快捷方式——使用一对大括号。
phonr_book { } #与phone_book dict()等效下面在电话簿中添加一些联系人的电话号码
phone_book[jenny] 8675309
phone_book[emergency] 120现在假设你要查找Jenny的电话号码为此只需向散列表传入相应的键. print phone_book[jenny]
8675309散列表被用于大海捞针式的查找。例如你在访问像http://adit.io这样的网站时计算机必须将adit.io转换为IP地址。这个过程被称为DNS解析DNS resolution这不是将网址映射到IP地址吗散列表是提供这种功能的方式之一.
防止重复
假设你负责管理一个投票站。显然每人只能投一票但如何避免重复投票呢有人来投票时你询问他的全名并将其与已投票者名单进行比对。
为此首先创建一个散列表用于记录已投票的人。
voted { }有人来投票时检查他是否在散列表中。
value voted.get(tom)如果“tom”在散列表中函数get将返回它否则返回None。你可使用这个函数检查来投票的人是否投过票
代码如下
voted {}def check_voter(name):if voted.get(name):print kick them out!else:voted[name] Trueprint let them vote!使用散列表来检查是否重复速度非常快。
将散列表用作缓存
假设你访问网站facebook.com:
你向Facebook的服务器发出请求。服务器做些处理生成一个网页并将其发送给你。你获得一个网页。
facebook的服务器处理需要时间为了少做工作提高facebook网站的访问速度服务器使用缓存对于经常使用的主页等不让服务器生成它而是将主页存储起来在需要时直接发送给用户。缓存具有如下优点
用户能够更快地看到网页。Facebook需要做的工作更少。
缓存是一种常用的加速方式所有大型网站都使用缓存而缓存的数据则存储在散列表中
Facebook不仅缓存主页还缓存About页面、Contact页面、Terms and Conditions页面等众多其他的页面。因此它需要将页面URL映射到页面数据。
当你访问Facebook的页面时它首先检查散列表中是否存储了该页面。 代码如下
cache {}def get_page(url):if cache.get(url):return cache[url]else:data get_data_from_server(url)cache[url] datareturn data仅当URL不在缓存中时你才让服务器做些处理并将处理生成的数据存储到缓存中再返回它。这样当下次有人请求该URL时你就可以直接发送缓存中的数据而不用再让服务器进行处理了。
冲突
前面讲到散列函数最好是可逆函数其总是将不同的键映射到数组的不同位置。实际上几乎不可能编写出这样的散列函数。
当给两个键分配的位置相同时就会产生冲突(collision)不同的输入得到相同的映射值。冲突很糟糕必须要避免。处理冲突的方式很多最简单的办法如下如果两个键映射到了同一个位置就在这个位置存储一个链表
散列函数很重要。最理想的情况是散列函数将键均匀地映射到散列表的不同位置。如果散列表存储的链表很长散列表的速度将急剧下降。然而如果使用的散列函数很好这些链表就不会很长
如何选择好的散列函数呢
性能
在平均情况下散列表的查找获取给定索引处的值速度与数组一样快而插入和删除速度与链表一样快因此它兼具两者的优点但在最糟情况下散列表的各种操作的速度都很慢。因此在使用散列表时避开最糟情况至关重要。为此需要避免冲突。而要避免冲突需要有
较低的填装因子良好的散列函数。
装填因子
装填因子散列表中包含的元素数/位置总数装填因子散列表中包含的元素数/位置总数装填因子散列表中包含的元素数/位置总数
一旦填装因子开始增大你就需要在散列表中添加位置这被称为调整长度resizing
首先创建一个更长的新数组通常将数组增长一倍。使用函数hash将所有的元素都插入到这个新的散列表中。
填装因子越低发生冲突的可能性越小散列表的性能越高。一个不错的经验规则是一旦填装因子大于0.7就调整散列表的长度。调整长度的开销很大因此你不会希望频繁地这样做。
良好的散列函数
良好的散列函数让数组中的值呈均匀分布糟糕的散列函数让值扎堆导致大量的冲突。
小结
散列表是一种功能强大的数据结构其操作速度快还能让你以不同的方式建立数据模型。
你可以结合散列函数和数组来创建散列表。冲突很糟糕你应使用可以最大限度减少冲突的散列函数。散列表的查找、插入和删除速度都非常快。散列表适合用于模拟映射关系。一旦填装因子超过0.7就该调整散列表的长度。散列表可用于缓存数据例如在Web服务器上。散列表非常适合用于防止重复。
