请问做网站需要什么,wordpress完全开发手册,python可以做网站开发吗,企业融资需求怎么写数据结构和算法 基于《算法图解》—Aditya Bhargava 和《数据结构》—严蔚敏
第5章 散列表
假设你在一家杂货店上班。有顾客来买东西时#xff0c;你得到一个本子中查找价格。如果本子的内容不是按字母顺序来排序的#xff0c;你可能为查找苹果价格而浏览每一页#xff0c…数据结构和算法 基于《算法图解》—Aditya Bhargava 和《数据结构》—严蔚敏
第5章 散列表
假设你在一家杂货店上班。有顾客来买东西时你得到一个本子中查找价格。如果本子的内容不是按字母顺序来排序的你可能为查找苹果价格而浏览每一页这显然需要很长的时间。此时使用简单查找需要浏览每一行这需要的时间为O(n)。 但如果以为名叫Maggie的店员能记住全部商品的价格那就不需要查找马上就能知道答案。报出商品价格的时间为O(1)这速度比二分查找都快。
5.1 散列表 散列表是这样的函数即无论你给它什么数据它都能还给你一个数字。
专业术语的表达是散列函数“将输入映射到数字”。 满足以下要求
必须一致。例如输入Apple时得到4那么每次输入Apple时得到的都必须是4。应将不同的输入映射到不同的数字。
散列函数具体原理
散列函数总是将同样的输入映射到相同的索引(其实不一定见5.3冲突)。散列函数将不同的输入映射到不同的索引。散列函数知道数组有多大值返回有效的索引。如果数组包含5个元素散列函数就不会返回无效索引100。
使用散列函数和数组创建了一个被称为散列表(hash table)的数据结构。 数组和链表都被直接映射到内存但散列表更复杂它使用散列函数来确定元素的存储位置。 散列表使用数组来存储数据因此其获得元素的速度与数组一样快。 任一优秀的语言都提供了散列表的实现。Python提供的散列表实现为字典由键和值组成使用函数dict来创建散列表。
5.2 应用案例
5.2.2 防止重复 使用散列表来检查列表内元素是否重复速度非常快。
voted {}
def check_voter(name):if voted.get(name):print(kick them out!)else:voted[name] Trueprint(let them vote!)5.2.3 将散列表用作缓存 以网站工作为例缓存是一种常用的加速方式所有大型网站都使用缓存而缓存的数据则存储在散列表中当打开网页时网站将数据记住而不再从新计算(缓存/记住数据以免服务器再通过处理来生成它们)。 网站使用缓存用户能够更快看到页面并减少网站的工作量。
比如当你访问facebook页面时它首先检查散列表中是否存储了该网页。
cache {}
def get_page(url):if cache.get(url):return cache[url]else:data get_data_from_server(url)cache[url] datareturn data5.3 冲突 假设我们要将apple的价格存储到散列表中分配第一个位置。
将banana的价格存储到散列表中分配第二个位置。
但现在要将avocado的价格存储到散列表中分配的也是第一个位置。但这个位置已经存储了价格这种情况被称为冲突(cllision)。
处理冲突的方法有很多最简单的是如果两个键映射到了同一个位置就在这个位置存储一个链表。
如果散列表中存在很多很长的链表那么散列表的速度会变慢。所以散列函数很重要。好的散列函数会将键均匀地映射到散列表的不同位置。好的散列函数很少导致冲突。 减少位置的浪费。
5.4 性能-如何选择好的散列函数 为避免冲突需要
较低的填装因子。良好的散列函数。
5.4.1 填装因子 填装因子散列表包含的元素个数 / 散列表位置总数
填装因子度量的是散列表中有多少位置是空的。 理想情况是刚好装满也就是填装因子为1(实际不太可能实现)。
填装因子大于1意味着商品数量超过了数组的位置数。一旦装填因子开始增大就需要在散列表中添加位置这被称为调整长度(resizing)通常创建一个更长的数组(原来的两倍)再使用函数hash将所有的元素都插入都这个新的散列表中。
填装因子越低发生冲突的可能性越小散列表的性能越高。(一般填装因子大于0.7就调整散列表长度。)
5.4.2 良好的散列函数 良好的散列函数让散列表呈数组值均匀分布。
糟糕的散列函数让值扎堆导致大量的冲突出现大量的链表。
5.5 小结
散列表的查找、插入和删除速度都非常快。散列表适合用于模拟映射关系。散列表可用于缓存数据(如在Web服务器上)。散列表非常适合用于防止重复。
——持续修改完善中…
