徐州网站建设优化,2021年中国中小企业最新数据,wordpress留言板模板下载,wordpress 建立小工具文章目录 1. 冲突难免2. 何为优劣3. 整除留余4. 以禅为师5. M A D6. 平方取中7. 折叠汇总8. 伪随机数9. 多项式10. Vorldmort 1. 冲突难免 好#xff0c;接下来的这一节我们就来介绍散列策略中的第一项#xff0c;也是最重要的技术#xff0c;散列函数的设计与定制。
在上… 文章目录 1. 冲突难免2. 何为优劣3. 整除留余4. 以禅为师5. M A D6. 平方取中7. 折叠汇总8. 伪随机数9. 多项式10. Vorldmort 1. 冲突难免 好接下来的这一节我们就来介绍散列策略中的第一项也是最重要的技术散列函数的设计与定制。
在上一节我们已经看到散列策略具有诸多的优势和巨大的潜力。然而尽管如此冲突却是这一策略的致命缺陷。然而更糟糕的是从理论上讲这一缺陷是无法根本消除的。 依然回到我们电话键盘的实例借助字符来助记电话号码的策略尽管十分精巧但同样不难举出冲突的实例。比如有时你需要找某个人但对应的号码却有可能属于某个学院。你要找的或许是欧几里得但这个电话却有可能属于小黄鸭。你可能需要联系太阳鸟但接听这个电话的却可能是只臭虫凡此种种皆是冲突。 ~ 我们知道散列函数无非是一个映射其功能无非是将词条空间中的元素映射到散列表地址空间。 而在通常的情况下前者要远远地大于后者因此绝不可能是一个单射。 当然面对这种现实我们并非无可作为。这方面的一条好消息是在一般的实际应用中我们还是可以在一定的程度上得到一个近似的单射。 比如黑白打印机经常要做的一件事就是将原本是彩色的图像转换为黑白灰度的。从映射的角度来看这样一种转换也是散列对于这个散例而言数据项的取值范围应该是图像中各像素可能取的颜色种类数也就是2的24次方而散列表的长度也就是灰度的级别2的8次方。二者之间的差异也高达10的4至5次方。 然而尽管经过了如此之大幅度的压缩对我们辨识灰度图像中的物体并没有多大的影响。当然这主要得益于图像中各像素在空间上是有一个分布的。然而即便离开这个条件一般意义上的散列也是有可能做得足够实用的。为此我们需要做两件事这也是实现散列的两项基本任务。
首先我们需要精心的设计散列表及其对应的散列函数消除掉一些能够导致冲突的先天性因素从而尽可能地压低日后发生冲突的概率。这也是本节讨论的主题。当然既然无论如何都不可能从根本上消除冲突。所以我们也应该在事先准备好充分的预案日后一旦发生冲突我们就可到此预案及时予以排解。关于冲突的排解技巧往下看。
2. 何为优劣 什么样的散列函数更好好的散列函数又必须具备哪些要素呢
首先它必须具有确定性也就是说词条空间中的任何一个元素都应该能被唯一的映射到散列地址空间中的某一元素。这种映射关系必须是明确的。其次从计算的角度来看这种映射应该能够快速地兑现。第三条相对于更大的取值空间散列的地址空间要小得多也需要更加充分的加以利用。为此散列函数必须是一个满射。同样是为了充分地利用有限的散列空间并降低冲突发生的概率我们应该使得各关键码被映射到散列表各位置的概率尽可能地接近。也就是要将所有可能的关键码尽可能均匀地压缩到散列空间中最大程度的避免很多元素在局部汇聚的现象也就是所谓的 clustering。
以下我们就按照这4条基本的标准介绍若干种常用的散列函数并分析起各自的优劣以及适用场合。
3. 整除留余 我们所设计的第一个散列函数使用的是所谓的除余法。实际上我们对这种方法应该并不陌生。是的在此前清华大学校园电话簿那个应用实例中我们所采用的正是这种散列方法。当然这里有一个问题你应该还记得当时的表长也就是这里取模余的基底是取做90001为什么取这样一个有点古怪的数字呢
是的这个数字的确有些古怪。因为照常理我们或许会选用一个更为规整的数字比如熟知二进制的你很有可能会选取2的若干次方。你甚至会发现如此可以更加高效地来计算散列地址。 因为此时 m 的二进制展开应该是 1 后面接 1 个 2 个 3 个直到第 k 个 0。而此时相对于 M 的模余计算也就等同于相对于 M-1 的位与运算是的就计算效率而言的确如此。 然而就我们刚才所确立的第四条原则也就是均匀性而言这种方法却是非常糟糕的。因为在整个关键码的取值空间中存在某个特定的子集该子集中的每一个元素都会统一地映射到散列表中的某一个特定单元而不是均匀地分布于整个散列表中。
实际上M 的每一个同余类都是这样的一个实例。放弃这些形式极其规整的表长映射的均匀性的确会有所改进但这还不是根本的办法。
一种最为简明的策略莫过于将表长取作为素数。 此时不仅数据对于散列表的覆盖程度能够达到最充分而且在散列表中的分布也将达到最均匀。我不凡从一个角度来理解这一点。
4. 以禅为师
知道在实际应用中我们所处理的数据通常都具有一定的局部性。其中一种典型的现象是数据序列中的数据项大多是按某一步长单调变换。想想你在程序中常写的 while 或者 for 之类的循环就应该不难理解这一点。
如果数据序列的步长为 S我们来考察 S 与 M 的最大公因子将其记作 G。 假设这就是散列表的地址空间其长度为 M而你的数据序列呢将从某一个位置开始以 S 为间隔逐次的转入下一项以及再下一项。当然如果你的数据序列足够长它就有可能会从另一端回到这个空间并且继续以 S 为间隔在散列地址空间中逐次访问下去。 现在考察这个数据序列在散列地址空间中留下的足迹。这些足迹能够遍历整个散列表空间吗如果能那么这种散列方法就具有均匀性反之就不具有。
借助数论的知识不难知道数据序列的足迹能够遍布整个散列表当且仅当刚才这个最大公因子 G 等于1。
请注意因为可能有不同的程序而每一程序的每一次运行所对应的这个步长未必相等。也就是说这里的 M 相对于几乎任何 S 最大公因子都只能是 1。这意味着什么呢意味着 M 应该是一个素数。
很有意思是很动物包括一些昆虫都懂得这个道理。在这里我们再次向禅学习学习它的哲学。没错禅的哲学。 昆虫学告诉我们禅有很多变种每一个变种都有其固定的生命周期。比如有些蚕是3年而有些却是17年。那么蝉是否有某一个子类寿命是14年、15年甚至16年呢据我所知没有。为什么没有呢不妨回到我们的散列表。实际上每一只禅在生命周期都可以对应为一个散列表蝉的寿命有多长散列表也就有多长。 ~ 所以有些种类的蝉所对应的散列表长度为13有些等于17当然也可能是11等等这类的数字。我们知道在自然界蝉是弱势群体它有很多天敌无论是螳螂还是螳螂之后的那只黄雀。每一种天敌大致也有一个自己的生命周期这就相当于我们这里的步长 S。每经过 S 年蝉的天敌都会更新一代。当然蝉不能去改变弱肉强食的法则但唯一能期望的只能是在同一年不要遇到更多的天敌。 ~ 相应的反过来所有的天敌都应该尽可能在每一年分布得更加均匀。这更有利于蝉作为一个物种得以在自然界延续下去。用数学的语言来说如果蝉能够选择自己的生命周期那么自然的就应该选择与天敌的生命周期保持最大公约数为1。 而为了以更多的天敌在生命周期上保持这种关系尽管禅有不同的变种但是在经过长时间的进化之后每一个变种都会聪明地将其生命周期设定为素数就像我们所看到的那样取做17、13等等。
5. M A D 我们接下来将要介绍的是 MAD法名字听出来多少有点恐怖这种方法可以认为是除余法的改进或推广。
是的如果更为严格地考察均匀性除余法的确还存在一定的缺陷体现在两个方面问题。
问题首先出在零点无论表长 M 取值如何零点总是会被映射到零点也就是说存在不动点这与任何元素都拥有均等的概率被映射到任何位置的原则是完全相悖的。其次尽管其他的元素都大体拥有均等的概率被分配到各个桶中但不同关键码之间的这种映射却存在着某种简明的关联关系。具体来说经过散列映射之后相邻的关键码也必然依然的相邻。
就此意义而言除余法所拥有的均匀性只是低阶。当然我们更希望实现更高阶的均匀性比如至少临近的关键码在经过散列之后不要继续地彼此临近。那么如何实现这种更高阶的均匀性呢
为此我们需要对除余法略做改进。除了表长继续取做素数我们还需要另外两个整数整个散列的计算过程包括三步首先做一次乘法再做一次加法最后再做整除模余。这里的计算步骤增加了但如此却可以针对性地修复此前的两个缺陷。 你看出来了吗是的新引入的整数 b 可以视作是偏移量如此即可有效的消除不动点。而另一个引入的整数 a 则扮演着步长的角色也就是说在经过散例变换之后原本相邻的关键码将变成间隔为 a从而不再继续相邻。 当然实际应用的需求多种多样的我们这里暂且只考虑最普遍的应用。实际上在不同的场合散列的原则都有可能发生变化甚至翻转比如在某些特殊的场合未必需要高阶的乃至通常的均匀性比如在一些几何计算的场合我们需要处理的往往是来自于高维空间中的一系列点。为了将他们压缩到更加低维的空间我们往往也需要借助散列。此时我们对散列的要求可能恰恰相反也就是要尽可能使得临近的关键码被映射到临近的位置这也就是所谓的 locality—Sensitive hashing 散列技术在当今的信息处理中之所以能够无处不在恰恰在于它的这些准则是灵活的。
再比如在我们这个课程中所讨论的主要技术多是指在将一个相对而言更大的空间通过散列映射压缩至一个相对而言更小的空间。而实际上反过来也是大有用处的这也就是所谓的密码学。
6. 平方取中 散列函数是一个庞大的家族其中的成员形形色色各有所长这也是散列技术的趣味性和魅力所在。
接下来我们不妨就来看看其中的几个典型代表。
首先是所谓的数字分析法这里的原则是无论此前的关键码有多少位我们只从其中挑选出若干位构成散列地址。 比如我们可以将关键码的数位间隔的分为两组并选择其一组成最终的散列地址。当然尽管这里需要分组但分组的方式必须是事先确定的否则也就违背了确定性的原则。 ~ 另外这种方法的缺陷也十分明显因为没有被选用的那一组数位对最终的散列地址没有任何的影响和贡献没有足够的体现均匀性的要求。 就此可以有很多种改进方法。
比如平方取中法。按照这种策略我们首先要计算出关键码的平方并截取中间的若干数位作为散列地址。以123为例如果没有算错它的平方应该是15129。因此我们可以取居中的三位也就是512作为对应的散列地址。更复杂的情况也是按同样的方法处理。至此你或许会有一个疑问这里为什么我们会倾向于保留居中的数位呢实际上这正是为了使得构成原关键码的各数位能够对最终的散列地址有尽可能接近的影响。
来看这样一幅图它将一个数的平方运算分解为一系列的左移操作以及若干次加法。如果最终的结果是这个从图中不难看出如果忽略进位每一个数位都是由原关键码中的若干数位经求和得到的。因此两侧的数位是由更少的原数位累计而得。而越是居中的数位则是由更多的原数位累积而得。因此截取居中的若干位可以使得原关键码的各数位对最终地址的影响彼此更为接近。
7. 折叠汇总 为了使得原关键码中的各数位对最终地址拥有更为平均的影响力从而实现更好的均匀性还有一些非常有趣的散列函数值得借鉴。
比如所谓的折叠法可以按照最终散列地址的宽度将原关键码中的个数位依次分为若干组并将每一组独立的视作为一个整数而是他们的总和就是对应的散列码。这种方法还有一些有趣的变种比如原关键码中的各数位将按照交替的方向转换为对应的整数123 456 789诸如此类。 形象地说这个好比我们需要做一张千层饼。为此我们首先需要将和好的面擀成一张薄片前一方法会将面继续地切成均等的一段并按次序将他们落起来最后通过挤压将他们合成一张薄饼。而相对于真实的千层品制作工艺后一种方法更为接近也就是以一种往复折返的方式同样将面折叠起来并最终压实。 尽管同样是经过分段和对齐最终压实的那一步却未必只能通过求和。比如对于二进制很多种位运算都具有同样的功效比如最常用的就是按位做异或。就不妨就此来验证这里所给的实例。
当然此类方法零零种就此你应该对反例函数的特征有了更具体的理解。是的总之大致说来散列函数越是随机越是没有规律就越好。
8. 伪随机数 谈到随机你应该很自然会想到系统所提供的随机数发生器。
比如这就是一种实现的方式可以看到这里每一个所谓的随机数实际上都是在前一个所谓随机数基础上按照确定的计算规则递推而得。因此更为准确的应该称之为伪随机数发生器。
就逻辑效果而言这等同于将取值范围以内的所有整数按照这种规则重新编排为一个貌似随机实则确定的序列。而这个发生器所有返回的只不过是在这个序列中对应于某个特定秩的那个元素。比如一种最常见的方法就是将这个秩取作系统当前的时间。
如果就接口参数的形式对散列函数以及伪随机数发生器函数做一对比我们就会发现二者惊人的相似。 难道不是吗只不过前者是经统一散列转换之后所得的关键码而后者只是尾随基数序列中的某个值。 因此我们不妨直接借助后者来实现前者。事实上很有意思的是如果反过来考察此前我们已经确立的那四条准则无论是确定性、高效性、满射性还是均匀性它们恰好同时也是评判随机数发生器的重要标准。
既然每一个伪随机数发生器都可视作为一个散列函数我们也可以将散列函数的设计难题转交给伪随机数发生器的设计者我们可以直接套用他们的工作成果。当然事情还不是这么简单。
如果采用伪随机数法有一点是非常重要的。事实上在不同的平台和环境中所提供的伪随机数发生器所采用的算法不尽相同。即便在同一个平台环境中不同的历史版本也可能对应于不同的随机数发生算法。 因此你在特定时间、特定平台上所生成的散列表未必可以直接移植到其他的平台。对这一点你应该保持足够的谨慎。
9. 多项式 当然在实际应用中原始数据的关键码未必天生都是整数形式因此往往需要先做一个预处理将其转化为整数称作散列码 hashcode然后才可以将其进一步的转化为桶数组中的地址浮点数以及字符的 hashcode 转换并不困难。
因此接下来我们重点讨论一下字符串型关键码应该如何更好地完成这种转换。比如一种行之有效的方法就是所谓的多项式法。 比如这就是一个长度为 n 的字符串。
我们首先将其中的每一个字符分别转换为对应的整数。接下来再将这 n 个整数分别视作为一个 n 次多项式的 n 个系数并采用事先确定的某一个常数 a 计算出这个多项式的具体数值并将其作为散列地址。
请注意这样一个一元 n 次多项式可以在 On 而不是 n 平方的时间内计算得出。因为时间关系我们忽略掉具体的算法。如果你这句算法还不甚了解这个插图应该会对你有所帮助。当然这里的 On毕竟涉及较为复杂的乘法运算能否加以避免呢答案也是肯定的。
比如这就是一种可行而有效的方法。实验数据也表明这种散列码转换算法非常适用于英文字符串。可以看到这里也是通过一个 for 循环依次的处理串中的各个字符。对于每一个字符我们首先将其转换为整数并对其做累计而在每次这样的累计之前原有的累计值都要按这种方式做一个数位变换。
这图可以帮助我们理解整个变换的过程。如果这是此前累计值的二进制展开一般的取做32位那么调整的实际效果就是将前端的5个比特与此后的27个比特互换位置。这一不断调整、不断累加的过程实际上可以视作为是对以上多项式计算的近似只不过这里消除了相对费时的乘法计算。
至于如何来具体理解和解释这种近似的效果。当然无论是原始的多项式法还是变通之后的近似方法其计算过程都不明显的相对复杂。
你或许会质疑有这个必要吗答案是的确有。
10. Vorldmort 针对字符串关键码的hashcode转化最自然的方法莫过于此。具体的与多项式法一样这里也将每一个字符事先与某一个数值对应起来。而所有字符所对应数值的总和也自然就是所对应的 hashcode。
这个方法与此前所介绍的折叠法类似。但这里的情况却有所不同以至于这种方法将会导致频繁地冲突。
来看这样一个字符串—— Tom Marvel Riddle。 如果你熟悉 Harry Potter 的故事那么对 Tom Marvel Riddle 就不会陌生。是的它是伏地魔的一个化身而这个名字也是伏地魔的一个化名。 你也应该会记得这样一句话——I am Load voldemort。 是的这是 Tom Marvel 在自认为已经掌控了Harry Potter 的生死时颇为得意地写出的一句话。而谜底恰好就藏在这两个字符串中。即便你不知道这个故事现在也不难看出这两个字符串实际上是由同一组字符构成的只不过排列次序不同而已。 如果按照我们直观的想法将该字符串中的所有字符所对应的整数累积起来就会得到一个 hashcode 196。那么 I am Load voldemort不难理解尽管次序有所调整但因为加法满足交换率所以同样应该得到196。
当然既然这两个串都是由同一组字符构成的所以 hashcode 相同也毫不奇怪。然而事实是即便是由不同的一组数字所构成的英文字符串按照这种映射方法也同样会有很高的概率发生冲突。
继续刚才的故事应该还记得第七集。是的在那集中我们终于得知 Harry Potter 居然也是 voldemort 化身或者死亡魂器之一。那么在冥冥之中Harry Potter 是否真的与伏地魔有某种因果联系呢我们不妨来做一次散列如果还不是占卜的话来看这样字符串。
既然 Tom Marvel与 voldemort 的联系是源自其名字的巧合那么 Harry Potter 与 voldemort也应该是如此。嗯必须的。
