搜索引擎技术之数据结构

《搜索引擎技术之数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、搜索应用技术冲出宇宙2008.11预备知识如果只是给一个普通项目提供搜索支持，你不需要多少预备知识，可以跳过本节。如果你想把搜索作好，建议你看本节。本节假定读者已经具备计算机专业本科水平。本预备知识包含了搜索引擎一般需要使用的而普通课本上面又没有详细描述的数据结构和压缩算法。1.1数据结构1.1.1Hash函数定义：Hash函数把任意范围的key映射到一个相对较小的整数范围内。比如，md5hash算法就是把任意字节数组映射到128位的整数上。Hash函数在很多领域都有应用，比如，模式匹配、密码学。它们都额外的定义了Hash函数的其他特点，如密码学要求Hash函数接近于单向函

2、数。我们这里只讨论Hash函数在Hashtable结构里面的应用。1.1.1.1常用Hash函数介绍Hash函数一般会分为2种，即Hashtable用的hash和密码学上面应用的Hash。这里分开介绍。1.1.1.1.1Hashtable的Hash函数应用在Hashtable上的Hash函数的一个主要特点是输出一般为32或者64位。常见的算法有很多种，有关这些Hash算法的实现代码，可以参考笔者博客上的文章：Hash算法实现。1.1.1.1.2密码学上的Hash函数密码学上的Hash函数第一重要的是其伪单向性。故一般其计算都特别复杂，结果位数也很长。我们常见的Hash函数有

3、如下几个：Adler-32：定义在rfc1950里面，是一种乘法Hash算法，结果是32位整数；CRC32：循环冗余码，结果是32位整数；MD系列：md3,md4,md5等，结果都是128位整数；考虑到md5冲突的易构造性，建议不要用它做重要消息签名；1搜索应用技术冲出宇宙2008.1RipedMd系列：有128/160/256/320位4种规范，但RipedMd-256/320没有被认真设计，其安全度和128/160这2种规范一样；SHA系列：有160/256/384/512位4种规范；Tiger：192位，专门为64位机器优化；WhirlPool：512位

4、。这里，需要注意的是，美国的国家标准推荐使用如下几个Hash算法：RipedMd系列，SHA系列，Tiger和WhirlPool。具体的说明大家可以去看密码学相关书籍（推荐《密码学基础（英文版）》和《现代密码学理论与研究》）或者学习著名的开源库Crypto++或者参考笔者的博客：Hash散列算法详细解析。1.1.1.2Hashtable处理碰撞的技术Openaddressing（closedhashing）：探测方式。通过选择不同的位置来存放数据。线形探测：计算公式为next_pos=(cur_pos+m)modN；其中m为常数，N为Hashtable数组长度；平方探

5、测：常用计算公式为next_pos=(cur_pos+cur_pos^2)modN；二次Hash：常用计算公式为next_pos=(cur_pos+Hash2(key))modN；Hash2表示第二个Hash函数。Chaining：链表方式。即把冲突的key串在一起。以上两种碰撞处理技术很多数据结构书籍都详细描述过，本处不在赘述。下面看看其他的方法：Coalescedhashing：结合了Openaddressing和Chaining方法，把Chaining的链表融合到Hashtable的数组里面，从而减少了空间使用。下面用一个例子说明这种方式。输入key序列为{“q

6、ur”,“qrj”,“ofu”,“gcl”,“clq”,“ecd”,“aty”,“rhv”,“qus”}，左边图是基本Chaining方式的结果，右边图是本方式的结果：Null“clq”“qur”Null“dim”“aty”“qsu”“rhv”“qrj”“ofu”“gcl”“ecd”NullNull2搜索应用技术冲出宇宙2008.1Coalescedhashing方式的处理方法为：利用线形探测找到一个空位，填入key，然后把这个空位链接到相同映射值组成的链表上面。需要注意的是，Coalescedhashing对定长的key才真正有用。Cuckoohashing：基本思想是

7、使用2个hash函数来处理碰撞，从而每个key都可以对应到2个位置。其具体的处理方式为：如果key对应的2个位置中有一个为空，key就可以插入到那个位置；否则，任选一个位置，key插入，把已经在那个位置的key踢出来；被踢出来的key需要重新插入；直到没有key被踢出为止。显然，这种方式是可能产生无限循环的，当出现无限循环的时候，就需要重新选择hash函数。Cuckoohashing有2个主要的变形：1）增加hash函数的个数；2）每个位置可以放2个key。这2个的目的都是为了增加Hashtable数组的利