购物网站含有哪些模块上海高玩seo

当前位置： 首页 > news >正文

购物网站含有哪些模块,上海高玩seo,seo的宗旨是什么,课程网站建设课程文章目录 1. 一山二虎2. 泾渭分明3. 开放定址4. 线性试探5. 赖惰删除 1. 一山二虎 此前我们已经多次指出#xff0c;对于需要动态维护的散列表冲突是不可避免的#xff0c;无论你的散列函数设计的有多么精妙#xff0c;因此我们不得不回答的第二个重要问题就是一旦发生冲突对于需要动态维护的散列表冲突是不可避免的无论你的散列函数设计的有多么精妙因此我们不得不回答的第二个重要问题就是一旦发生冲突我们应该如何加以排解 当然任何一种可行的排解方法都应该是在事先就约定好的预案。 所谓冲突形象地说也就是一山不容二虎。那么倘若的确有两只老虎呢用铁丝网将这座山分成两部分两只老虎各居一侧。这种思路也就是所谓的多槽位法。如果此前的桶单员对应于山那么每一个 slot 就对应于在这个山中用铁丝网分割出的一个子区域。 在这幅图中如果这是散列表那么这就是一个又一个的桶单元。在这里我们将每个桶单元都继续细分为 a、b、c、d 四个槽位。每个桶内部的这些槽位就可以用来存放彼此冲突的若干个词条。 比如这就是一个长度为 23 的散列表其中每一个桶都被分成了三个槽位。现在我们依次将24个词条插入其中。 可以看到这里尽管有些词条的确会彼此冲突但依然可以在对应的桶中和平共处。当然查找过程需要多出一步除了需要根据关键码确定对应的统单元地址还需要在桶中遍历所有的槽位直到找到目标或者失败。 当然只要每个桶中槽位的总数能够控制在常数以内整体的查找效率就不会有实质的降低。 不过这种方法的缺点也是显而易见的你能看得出来吗是的每一桶具体应该细分为多少个槽位在事先几乎是无法预测的。如果分得过细就会造成空间上的浪费。而反过来无论你分得多细在极端情况下仍有可能在某个特定的桶中发生大规模的冲突。那么面临这一两难的抉择如何破解呢

1. 泾渭分明 多槽位法在空间效率和时间效率之间的两难处境我们在学习向量时也曾遇到过还记得那时的解决办法吗是的改用列表。 新的策略如这幅图上图所示如果这是整个桶数组那么其中每一个单元都将各自拥有一个对应的列表。而每一个列表都可以用来存放一组彼此冲突的词条。是的将相互冲突的词条串接起来也就是所谓的 separate chaining。 来看独立链法的一个实例依然是一个长度为23的散列表。接下来我们将64个词条插入其中。请留意观察每个桶所对应的列表是如何演化的。 ~   相对于与多槽位法独立链法的优势非常明显比如除了最初的空链表我们无需预留任何更多的空间。而且表的长度可以根据需要自由的伸缩。只要系统的资源足够任意多次的冲突都可以解决。 得益于此前对 List 结构的良好封装我们只需寥寥几句即可实现相应的散列表结构。当然这种方法的缺点也同样是很明显的。比如这里需要引入额外的指针而为了生成或销毁节点也需要借助动态内存的申请相对于常规的操作此类动态申请操作的时间成本大致要高出两个数量级。 然而这种方法最大的缺陷还不仅于此你能发现吗是的系统的缓存功能。在这里每桶内部的查找都是沿着对应的列表顺序进行的。然而在此之前不同列表中各节点的插入和销毁次序完全是随机的。比如可能会是这样(上图中的黄色线条)。 因此对于任何一个列表而言其中的节点在物理空间上往往不是连续分布。因此系统很难预测你的访问方向无法通过有效的缓存加速查找过程。当散列表的规模非常之大以至于不得不借助 IO 时这一矛盾就显得更加突出了。 那么为了有效的激活并充分利用系统的缓存功能我们又当如何继续改进呢
2. 开放定址 反观独立链法其采用的是所谓封闭定址策略 closed addressing。也就是说对于散列表中的任何一个单元在其所对应的列表中能够存放而且只能够存放那些与这个桶单元的地址比如 k 相冲突的词条。 也就是说每个词条应该属于哪个桶所对应的列表都是在事先已经注定了的。不难理解只要采用这种策略就很难保证每组冲突的词条在空间上能够彼此毗邻。 因此后续我们应该放弃这种策略并反其道而行之也就是采用所谓的开放定址策略 open addressing。 这种策略的特点是散列表所占用的空间在物理上始终是地址连续的一块相应的所有的冲突都在这块连续的空间中加以排解而无需向独立链法那样申请额外的空间。没错所有的散列以及冲突排解都在这样一块封闭的空间内完成。 因此相应的这种策略也可以称作为闭散列 closed hashing。既然是闭散列那么每一个桶单元都应该面向所有可能的词条开放。也就是说在特定的情况下每一个词条都有可能存放在任何一个桶中。 当然对于每一个特定的词条具体存放在哪个桶中是有不同的优先级的。其中优先级最高的自然是它本来就应该归属的那个桶。从这个桶开始所有的桶都按照某种优先级关系排成一个序列。 而在查找对应的词条时我们也总是从这个序列的起点出发顺次去尝试每一个桶单元。每个词条所对应的这样一个序列也称作试探序列、试探链或者查找链。当然沿查找链的查找同样有两种结果或者在某一个特定的桶中找到目标元素也就是所谓的成功或者一旦抵达第一个空桶即可报告失败。 那么具体的应该如何来约定查找链呢
3. 线性试探 查找链的第一种组织方法就是所谓的线性试探。具体来说所谓的 linear probing 就是一旦发生冲突之后我们会转而去试探它的后继后继的后继以及后继的后继的后继诸如此类。同样的最终可能会因为发现目标而报告成功或者因为抵达某个空桶而说明查找失败。 可以看到在如此形势的散列表中除了数据词条无需任何附加空间。 而更重要的是每一查找链都集中在某一局部。因此系统的缓存作用将得到充分的发挥而对于大规模的数据集如此更可以有效地减少 IO。当然这种策略同样也具有它的弱点。 其中重要一点就是为了消除以往的冲突可能会导致后续发生更多的冲突。来看这样一个实例考察一个长度为7的散列表。 假设我们需要插入的是 0 1 2 3 7 这样 5 个词条如果就按照这种顺序依次插入那么首先是0就位1 就位2 和3 也相继就位。为了插入最后的7我们首先去试探 0 号单元结果发现它非空为了排解这一冲突我们会转而试探它的后继也就是 1 号单元情况一样进而去试探 2 号 3号单元直到最终在4号单元发现一个空桶从而将7安置在这个桶中。在这个散列表的生命期内发生冲突的只有一个词条也就是7。 ~   现在再来看另一插入次序比如将 7 调整到最前端首先插入它我们依然开始于一个空的散列表。按照约定的次序首先将 7 安置在0号桶没有冲突。既然0号单元已被占用所以接下来插入 0 必然发生一次冲突并经过一次试探最终将 0 安置在 1 号单元。至此1号桶也会被占用。因此接下来词条 1 的插入也会发生一次冲突并最终将它安置在 2 号桶。这样的故事还会发生多次具体的也需要在这个位置发现一次冲突之后再将词条2存入到3号桶最后依然要经过一次冲突才能将词条 3 存入 4 号桶。在整个这样的过程中词条0、词条1 2和3都发生了冲突。前后对比不难发现后一种插入序列所对应的很多冲突本来的确是可以不必发生的。 5. 赖惰删除 以线性试探为代表的开放定址策略在使用时若要支持词条的删除则需格外的小心。我们来就此做一探讨。按照这种策略先后插入彼此冲突的一组词条都将存放在同一个查找序列中。而更确切地讲他们应该按照逻辑次序构成整个查找链的一个前缀其中不得有任何的空桶缝隙。 因此词条的删除操作需要做额外的一些处理。反之如果直接将词条删除那么被删除的词条所留下的空桶就有可能将查找链切断从而导致在此之后的词条丢失掉。尽管他们的确存在于散列表中却如何也访问不到。 针对这一问题一种简明的方法就是所谓的懒惰删除 lazy removal。也就是说如果在某个桶中此前曾有一个词条那么在这个词条被删除之后我们并不是简单地将这个桶清空而是为其做上一个特殊的标记比如说R在这样一个桶所属的每一条查找链中这类桶单元将根据具体情况可能扮演两种角色。 如果是针对某一特定词条的查找那么在抵达这个桶时根据这个标志我们就知道不应该在此中断而因越过它继续查找下去。反过来如果我们是为了插入新的词条而寻找一个空桶那么在首次抵达带有这样一个标志的桶之后就可以将它等效的视作是一个空桶并将待插入的新词条径直的插入其中。
   应该说针对开放定制策略懒度删除不仅是不得已而为之的方法也甚至可以说是针对这种情况的最优方法。因为毕竟在开放定址策略中每一个同单元都同时属于多个查找链。