神马文学网第十三讲 散列表和基于属性的检索
来源：百度文库 编辑：神马文学网 时间：2024/05/23 11:25:33
1970年Bayer提出B-树，是多路平衡查找树。
1、B-树的定义：
一棵M阶的B-树满足下列条件：
（1）每个结点至多有m棵子树；
（2）若根结点不是叶子，至少有两棵子树；
（3）每个非终端结点至少有m-1棵子树；
（4）各结点包括下列信息：
（n,A0,K1,A1,K2,A2,…,Kn,An)
其中，Ki为关键字，且KiAi为指向子树的指针，且Ai-1(i=0,1,2,…,n-1)所指子树的关键字均小于Ki，An所指子树的关键字均大于Kn；
n为关键字个数，n>=「 -1,n<=m-1;
（5）所有叶子结点在同一层上，是查找失败的结点（外部结点）。
2、B-树的查找
首先查找关键字所在结点，然后在结点内查找（顺序和折半均可）。
3、B-树的插入
在最下一层非终端结点插入。
若该结点关键字个数小于m-1，则直接插入（包括子树指针）；
若该结点关键字个数等于m-1，则产生分裂：
m,A0,K1,A1,K2,A2,…,Km,Am)
P: 「 -1,A0,K1,A1,K2,A2,…,Km/2,Am/2 和
P’: m-「 ,A m/2,K m/2+1,A m/2+1,…,Km,Am
将K m/2和P’插入双亲结点中。
4、B-树的删除
在最下层非终点结点删除。
（1）结点的关键字数大于m/2-1;
（2）（1）结点的关键字数等于m/2-1;其左（或右）兄第结点的关键字数大于m/2-1；
（3）结点及其左、右兄弟的关键字数都等于m/2-1;
5、B-树的查找分析
第一层 1个
第二层 2个第三层 2*m/2个
第L+1层 2*「 L-1
N+1<= 2*「 L-1
9·4 散列表的检索
9·4·1 散列表的基本概念
1、 散列函数的提出
从前讲的检索，都是用待检索的关键字和各记录的关键字比较，若相等，则检索成功，否则，继续比较。我们希望找到一个函数，对关键字进行计算，把函数值解释为记录的存储地址，这就是散列检索。所用的函数就叫散列函数。用散列法存储的线性表叫散列表。查找时也用同样方法计算地址，到相应单元去找记录。若找到，则查找成功；若该单元无记录，则查找失败；若该单元有记录，但不是所找，要继续查找。这种方法也称关键字-地址转换法。
2、 散列检索的术语
（1） 碰撞（冲突）：两个关键字不同，但其散列函数值相同，即key1<>key2，f(key1)=f(key2)。冲突是不可避免的，举标识符的例子。1939年 davenport的“生日悖论”。
（2） 同义词：发生碰撞（冲突）的关键字称为同义词。
（3） 负载因子：定义为
a=（散列表中结点的数目）/（散列表的长度）
a一般取0.6~0.9
（4） 采用散列表着重考虑两个问题：
选择一个好的散列函数；
选择一种解决碰撞（冲突）的方法。
3、 对散列表较详细的叙述
根据设定的散列函数h(key)和处理冲突的方法，将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表称为散列表，这一映象过程叫散列（或哈希造表），所得存储地址称散列地址或哈希地址。
9·4·2 散列函数的构造方法
1、 数字选择法
分析关键字的各位，去掉分布不均匀的位，留下均匀的位作为地址。
2、 平方取中法
一个数平方后，结果的中间几位和数的各位都有关系，可以取中间几位作为地址。
3、 折叠法
关键字位数较多，分布均匀，用折叠法。折叠法又分为移位折叠和间界折叠。
4、 除余法
关键字除以p的余数作为地址：
h(key)=key mod p
通常p取小于散列表长的最大素数。
5、 基数转换法
将一个小基数的数看作大基数的数，再转换为小基数的数。如key=(215874)10,将其看作以13为基数，再转化为相应的十进制数。（215874）13=（783579）10，再进行数字分析，选2,3,4,5位，得h(215874)=8357。
6、 随机数法
H(key)=random(key)
9·4·3 处理冲突的方法
处理冲突的方法分两大类：拉链法和开放地址法。
1、 拉链法
拉链法的基本思想是，散列表（向量）的每个元素由两个域组成，一个域存放关键字，另一个域是一个地址指针，指向该关键字的同义词，若无同义词，该域为空。设关键字的个数是n，散列表长m，则同义词子表的平均长度为n/m，很短。同义词子表的建立有两种方法：一是在溢出区（动态）建立同义词子表，称为分离的同义词子表的方法；另一个是在基本区（散列表向量）建立同义词子表，称为结合的同义词子表的方法。
（1） 建立分离的同义词子表的方法：象从前动态建立单链表一样，将同义词建成单链表。例如，关键字序列为283,255,377,407,384,801,803,203,659,491,775,519,611,99，设向量空间为0—18，散列函数为h(key)=key mod 19。
其检索（查找）方法是，先计算关键字地址，若该地址处无关键字，则检索失败；若该地址正是要找的关键字，则检索成功；若该地址有关键字，但不是所找的关键字，则顺链查找，直到检索成功或链为空时失败。
（2） 建立结合的同义词子表的方法： 该方法不另动态开辟空间建立单链表，而是利用散列表向量空间，当遇到同义词时，要在向量空间中从后向前找尚未占用的空间，将同义词放入其中，并从关键字地址（下标）往该同义词处拉上链（静态链表）。这种方法易产生堆积（聚集），即同义词和非同义词争夺同一散列地址。解决方法用两遍处理：第一遍只插入同义词子表表头的关键字，第2遍插入其它关键字。
2、 开放地址法
开放地址法处理冲突的基本思想是：当发生冲突时，使用某种方法在散列表中形成一个探查序列，沿着此探查序列逐个单元的查找，直到找到给定的关键字或碰到一个开放的地址（即该单元为空）为止。若插入时碰到开放地址，则插入其中；若查找时碰到开放地址，则查找失败。
（1） 开放定址法
Hi=(H(key)+di) mod m (i=1,2,…,m-1)
其中，H(key)为散列函数，m为散列表长度，di为增量序列，有以下三种取法：
· di=1,2,…,m-1, 称为线性探查再散列，其探查单元序列为：d+1,d+2,…,m-1,0,…,d-1。
· di=12,- 12,22,- 22,32,…,+(-)k2,(k<=m/2),称为二次探查再散列。
· di=伪随机数序列，称伪随机探查再散列。
（2） 双散列函数探查法
就是当一个散列函数计算散列地址发生冲突时，使用第二个散列函数进行计算。设两个散列函数h1和h2，以关键字为自变量，设m为素数，可以取
h1(key)=key mod m
且
h2(key)=key mod (m-2)+1
或
h2(key)=[key/m] mod (m-2)+1
若h1(key)=d发生碰撞，双散列函数的探查序列为：
(d+h2(key)) mod m, (d+2h2(key)) mod m, (d+3h2(key)) mod m
双散列函数的探查法的检索过程，与其造表类似。
9·4·4 散列表的查找及分析
平均查找长度：
1、成功时的平均查找长度，论述相同；
2、失败时的平均查找长度论述不同：
（1）对线性探测再散列：除数是表长（陈小平P，还是散列地址（如26，字母序号作关键字）殷人昆 P306；
唐策善 P220
（2）链表
和空指针比较算否：严蔚敏/陈小平
1、B-树的定义：
一棵M阶的B-树满足下列条件：
（1）每个结点至多有m棵子树；
（2）若根结点不是叶子，至少有两棵子树；
（3）每个非终端结点至少有m-1棵子树；
（4）各结点包括下列信息：
（n,A0,K1,A1,K2,A2,…,Kn,An)
其中，Ki为关键字，且Ki
n为关键字个数，n>=「 -1,n<=m-1;
（5）所有叶子结点在同一层上，是查找失败的结点（外部结点）。
2、B-树的查找
首先查找关键字所在结点，然后在结点内查找（顺序和折半均可）。
3、B-树的插入
在最下一层非终端结点插入。
若该结点关键字个数小于m-1，则直接插入（包括子树指针）；
若该结点关键字个数等于m-1，则产生分裂：
m,A0,K1,A1,K2,A2,…,Km,Am)
P: 「 -1,A0,K1,A1,K2,A2,…,Km/2,Am/2 和
P’: m-「 ,A m/2,K m/2+1,A m/2+1,…,Km,Am
将K m/2和P’插入双亲结点中。
4、B-树的删除
在最下层非终点结点删除。
（1）结点的关键字数大于m/2-1;
（2）（1）结点的关键字数等于m/2-1;其左（或右）兄第结点的关键字数大于m/2-1；
（3）结点及其左、右兄弟的关键字数都等于m/2-1;
5、B-树的查找分析
第一层 1个
第二层 2个第三层 2*m/2个
第L+1层 2*「 L-1
N+1<= 2*「 L-1
9·4 散列表的检索
9·4·1 散列表的基本概念
1、 散列函数的提出
从前讲的检索，都是用待检索的关键字和各记录的关键字比较，若相等，则检索成功，否则，继续比较。我们希望找到一个函数，对关键字进行计算，把函数值解释为记录的存储地址，这就是散列检索。所用的函数就叫散列函数。用散列法存储的线性表叫散列表。查找时也用同样方法计算地址，到相应单元去找记录。若找到，则查找成功；若该单元无记录，则查找失败；若该单元有记录，但不是所找，要继续查找。这种方法也称关键字-地址转换法。
2、 散列检索的术语
（1） 碰撞（冲突）：两个关键字不同，但其散列函数值相同，即key1<>key2，f(key1)=f(key2)。冲突是不可避免的，举标识符的例子。1939年 davenport的“生日悖论”。
（2） 同义词：发生碰撞（冲突）的关键字称为同义词。
（3） 负载因子：定义为
a=（散列表中结点的数目）/（散列表的长度）
a一般取0.6~0.9
（4） 采用散列表着重考虑两个问题：
选择一个好的散列函数；
选择一种解决碰撞（冲突）的方法。
3、 对散列表较详细的叙述
根据设定的散列函数h(key)和处理冲突的方法，将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表称为散列表，这一映象过程叫散列（或哈希造表），所得存储地址称散列地址或哈希地址。
9·4·2 散列函数的构造方法
1、 数字选择法
分析关键字的各位，去掉分布不均匀的位，留下均匀的位作为地址。
2、 平方取中法
一个数平方后，结果的中间几位和数的各位都有关系，可以取中间几位作为地址。
3、 折叠法
关键字位数较多，分布均匀，用折叠法。折叠法又分为移位折叠和间界折叠。
4、 除余法
关键字除以p的余数作为地址：
h(key)=key mod p
通常p取小于散列表长的最大素数。
5、 基数转换法
将一个小基数的数看作大基数的数，再转换为小基数的数。如key=(215874)10,将其看作以13为基数，再转化为相应的十进制数。（215874）13=（783579）10，再进行数字分析，选2,3,4,5位，得h(215874)=8357。
6、 随机数法
H(key)=random(key)
9·4·3 处理冲突的方法
处理冲突的方法分两大类：拉链法和开放地址法。
1、 拉链法
拉链法的基本思想是，散列表（向量）的每个元素由两个域组成，一个域存放关键字，另一个域是一个地址指针，指向该关键字的同义词，若无同义词，该域为空。设关键字的个数是n，散列表长m，则同义词子表的平均长度为n/m，很短。同义词子表的建立有两种方法：一是在溢出区（动态）建立同义词子表，称为分离的同义词子表的方法；另一个是在基本区（散列表向量）建立同义词子表，称为结合的同义词子表的方法。
（1） 建立分离的同义词子表的方法：象从前动态建立单链表一样，将同义词建成单链表。例如，关键字序列为283,255,377,407,384,801,803,203,659,491,775,519,611,99，设向量空间为0—18，散列函数为h(key)=key mod 19。
其检索（查找）方法是，先计算关键字地址，若该地址处无关键字，则检索失败；若该地址正是要找的关键字，则检索成功；若该地址有关键字，但不是所找的关键字，则顺链查找，直到检索成功或链为空时失败。
（2） 建立结合的同义词子表的方法： 该方法不另动态开辟空间建立单链表，而是利用散列表向量空间，当遇到同义词时，要在向量空间中从后向前找尚未占用的空间，将同义词放入其中，并从关键字地址（下标）往该同义词处拉上链（静态链表）。这种方法易产生堆积（聚集），即同义词和非同义词争夺同一散列地址。解决方法用两遍处理：第一遍只插入同义词子表表头的关键字，第2遍插入其它关键字。
2、 开放地址法
开放地址法处理冲突的基本思想是：当发生冲突时，使用某种方法在散列表中形成一个探查序列，沿着此探查序列逐个单元的查找，直到找到给定的关键字或碰到一个开放的地址（即该单元为空）为止。若插入时碰到开放地址，则插入其中；若查找时碰到开放地址，则查找失败。
（1） 开放定址法
Hi=(H(key)+di) mod m (i=1,2,…,m-1)
其中，H(key)为散列函数，m为散列表长度，di为增量序列，有以下三种取法：
· di=1,2,…,m-1, 称为线性探查再散列，其探查单元序列为：d+1,d+2,…,m-1,0,…,d-1。
· di=12,- 12,22,- 22,32,…,+(-)k2,(k<=m/2),称为二次探查再散列。
· di=伪随机数序列，称伪随机探查再散列。
（2） 双散列函数探查法
就是当一个散列函数计算散列地址发生冲突时，使用第二个散列函数进行计算。设两个散列函数h1和h2，以关键字为自变量，设m为素数，可以取
h1(key)=key mod m
且
h2(key)=key mod (m-2)+1
或
h2(key)=[key/m] mod (m-2)+1
若h1(key)=d发生碰撞，双散列函数的探查序列为：
(d+h2(key)) mod m, (d+2h2(key)) mod m, (d+3h2(key)) mod m
双散列函数的探查法的检索过程，与其造表类似。
9·4·4 散列表的查找及分析
平均查找长度：
1、成功时的平均查找长度，论述相同；
2、失败时的平均查找长度论述不同：
（1）对线性探测再散列：除数是表长（陈小平P，还是散列地址（如26，字母序号作关键字）殷人昆 P306；
唐策善 P220
（2）链表
和空指针比较算否：严蔚敏/陈小平
第十三讲 散列表和基于属性的检索
基于内容的音频检索
基于内容的音频检索
基于内容的音频检索
易经的奥秘］第十三讲：易经与家庭
第十三讲 耳轮脚周围的穴位分布
第十三讲 老子智慧与交往的心灵淳朴(13)
css属性列表 和 属性值含义 - ccaakkee的专栏 - CSDNBlog
css属性列表 和 属性值含义 - ccaakkee的专栏 - CSDNBlog
脑算乘法第十三讲
脑算乘法第十三讲
第十三讲：《易经》与家庭
恒河大手印 第十三讲
［曾仕强百家讲坛讲稿］［易经的奥秘］第十三讲：易经与家庭..
养生23讲第十三讲越用越灵活的大脑——脑养生奥秘
第十三讲 质数与合数（2）
上古天真论篇第十三讲
脑算乘法第十三讲-------郜毛德推荐
上古天真论篇第十三讲
第三十三讲：创作过程中的旋律和语言的关系
基于Lucene/XML的站内全文检索解决方案
Lucene：基于Java的全文检索引擎简介
基于Lucene/XML的站内全文检索解决方案
Lucene：基于Java的全文检索引擎简介