① 查找、B树、哈希表、字符串模式匹配
一棵度为m的B树称为m阶B树，是一棵平衡的m路查找树，其定义是：
一棵m阶B树，或者是空树，或者是满足以下性质的m叉树：
(1)根结点或者是叶子结点，或者至少有两棵子树，至多有m棵子树；
(2)除根结点外，所有非叶子结点至少有⌈m/2⌉棵子树，至多有m棵子树；
(3)所有叶子结点都在树的同一层上。
(4)每个结点应包含如下信息：
其中n是结点中关键字的个数，且⌈m/2⌉-1≤n≤m-1，n+1为子树的棵树。
是关键字，且 ，即递增。
为指向孩子结点的指针，且 所指向的子树中所有结点的关键字都小于 ， 所指向的子树中的所有结点的关键字都大于 ；
类似二叉排序树的查找，所不同的是 B 树每个结点上是多关键码的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功;否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码，查找失败。即在 B 树上的查找过程是一个顺指针查找结点和在结点中查找关键码交叉进行的过程。
B树的生成也是从空树起，逐个插入关键字。
插入时不是每插入一个关键字就添加一个叶子结点，而是首先在最低层的某个叶子结点中添加一个关键字，然后有可能“分裂”。
(1)插入思想
①在B树种查找关键字K，若找到，表明关键字已存在，返回；否则，K的查找操作失败于某个叶子结点，转②
②将K插入到该叶子结点中，插入时，若
※叶子结点的关键字数<m-1，则直接插入；
※叶子结点的关键字数=m-1，将结点“分裂”
(2)分裂方法
设待分裂结点p包含信息为： ，从其中间位置分为两个结点： 。并将中间关键字 插入到p的父结点中，以分裂后的两个结点作为中间关键字 的两个子结点。
当把中间关键字 插入到p的父结点后，父结点可能也不满足m阶B树的要求，则必须对父结点进行分裂，一直进行下去，直到没有父结点或分裂后的父结点满足要求。
当根结点分裂时，因没有父结点，则建立一个新的根，B树增高一层。
一棵三阶 B 树(2-3 树)，(b) 插入 30 之后; (c) 、(d) 插入 26 之后;(e)~(g) 插入 85 之 后; (h)~(j) 插入 7 之后变化如下图：
如果想要在 B 树上删除一个关键字，首先需要找到这个关键字所在的结点，从中删去这个关键字。若 N 不是叶子结点，设 K 是 N 中的第 i 个关键字，则将指针 所指子树中的最大关键字(或最小关键字)K’放在(K)的位置，然后删除 K’，而 K’一定在叶子结点上。
从叶子结点中删除一个关键字的情况是：
(1)若结点N中的关键字个数>⌈m/2⌉-1，在结点中直接删除关键字K。
(2)若结点N中的关键字个数=⌈m/2⌉-1，若兄弟结点关键字个数>⌈m/2⌉-1，则将兄弟结点的最大(或最小)关键字上移到父结点中，再把父结点中下移一个到结点N。
下图为删除65借用兄弟结点示例：
下图演示了删除50(兄弟可借)和删除37(兄弟不可借且父结点兄弟也不可借)的删除过程：
在实际的文件系统中，基本上不使用B树，而是使用B树的一种变体，称为m阶 树。
它与B树的主要不同是叶子结点中存储记录，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键字”，用来界定某一关键字的记录所在的子树。
一棵 m 阶的 B+树和 m 阶的 B 树的差异在于:
(1)若一个结点有 n 棵子树，则必含有n个关键字；
(2)所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接。
(3)所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大(或最小)关键字。
基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。
哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。
哈希表：应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。
哈希查找(又叫散列查找)：利用哈希函数进行查找的过程叫哈希查找。
冲突：对于不同的关键字，哈希值相同的现象叫冲突。
同义词：具有相同函数值的两个不同的关键字，称为该哈希函数的同义词。
设计一个散列表应包括：
①散列表的空间范围，即确定散列函数的值域。
②构造合适的散列函数，使得对于所有可能的元素，函数值均在散列表的地址空间范围内，且出现冲突的可能尽量小。
③处理冲突的方法。
1.直接寻址法
取关键字或关键字的某个线性函数作哈希地址，即H(key) = key 或 H(key) = a * key + b。
特点：直接寻址法所得地址集合与关键字集合大小相等，不会发生重复，但实际中很少使用。
2.数字分析法
假设关键字集合中的每个关键字都是由 s 位数字组成(k1, k2, ..., kn)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。
此法仅适合于:能预先估计出全体关键字的每一位上各种数字出现的频度。
3.平方取中法
若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过“平方”扩大差别，同时平方值的中间几位受到整个关键字中各位的影响。
此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。
4.折叠法
若关键字的位数特别多，则可将其分割成几部分，然后取它们的叠加和为散列地址。可有:移位叠加和间界叠加两种处理方法。
(1)移位法:将各部分的最后一位对齐相加。
(2)间界叠加法:从一端向另一端沿各部分分界来回折叠后，最后一位对齐相加。此方法适合于:关键字的数字位数特别多。
5.除留余数法
H(key) = key % p p≤m (表长)
即取关键码除以 p 的余数作为散列地址。使用除留余数法，选取合适的 p 很重要，若散列表表长为 m，则要求 p≤m，且接近 m 或等于 m。p 一般选取质数，也可以是不包含小于 20 质因子的合数。
6.随机数法
H(key) = Random(key)，其中，Random 为伪随机函数。
通常，此方法用于对长度不等的关键字构造散列函数。实际造表时，采用何种构造散列函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。
冲突处理：出现冲突时，为冲突元素找到另一个存储位置。
1.开放寻址法
基本方法：当冲突发生时，形成某个探测序列，按此序列逐个探测散列表中的其它地址，直到找到给定的关键字或一个空地址为止，将发生冲突的记录放到该地址中。
①线性探测法
将散列表T看成循环向量。设初次发生冲突的地址是h，则依次探测T[h+1]、T[h+2]...，直到T[m-1]时又循环到表头，再次探测T[0],T[1]...。
计算公式是：
其中Hash(key)是哈希函数，m是散列表长度， 是第i次探测时的增量序列。
设散列表长为 7，记录关键字组为:15, 14, 28, 26, 56, 23，散列函数:H(key)=key MOD 7，冲突处理采用线性探测法。
H(15) = 15 % 7 = 1
H(14) = 14 % 7 = 0
H(28) = 28 % 7 = 0 冲突
又冲突
H(26) = 26 % 7 = 5
H(56) = 56 % 7 = 0 冲突
又冲突
又冲突
H(23) = 23 % 7 = 2 冲突
又冲突
线性探测法的特点
优点：只要散列表未满，总能找到一个不冲突的散列地址。
缺点：每个产生冲突的记录被散列到离冲突最近的空地址上，从而又增加了更多的冲突机会(称为冲突的“聚集”)。
②二次探测法
增长序列为:
上面例题采用二次探测法进行冲突处理
H(15) = 15 % 7 = 1
H(14) = 14 % 7 = 0
H(28) = 28 % 7 = 0 冲突
又冲突
又冲突
二次探测法的特点
优点：探测序列跳跃式地散列到整个表中，不易产生冲突的聚集现象。
缺点：不能保证探测到散列表的所有地址
③伪随机探测法
增长序列使用一个伪随机函数来产生一个落在闭区间[1,m-1]的随机序列。
2.再哈希法
构造若干个哈希函数，当发生冲突时，利用不同的哈希函数再计算下一个新哈希地址，直到不发生冲突为止。
优点：不易产生冲突的聚集现象。
缺点：计算时间增加。
3.链地址法
方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放链表的头指针。哈希值相同的元素插入时可以在表头或表尾插入。
优点:不易产生冲突的“聚集”;删除记录也很简单。
例: 已知一组关键字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) ，哈希函数为:H(key)=key % 13，用链地址法处理冲突 。
4.建立公共溢出区
方法：在基本散列表外，另外设立一个溢出表保存与基本表中记录冲突的所有记录。
设散列表长为 m，设立基本散列表 hashtable[m]，每个分量保存一个记录;溢出表overtable[m]，一旦某个记录的散列地址发生冲突，都填入溢出表中。
已知一组关键字(15, 4, 18, 7, 37, 47) ，散列表长度为 7 ，哈希函数为:H(key)=key % 7，用建立公共溢出区法处理冲突。
得到的基本表和溢出表如下:
串的基本概念:串是零个或多个字符组成的有限序列。一般为:S=“c1c2c3...cn”其 中，s 是串名;将一个串中若干个相连字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。
串的模式匹配:子串在主串中的定位称为模式匹配或串匹配(字符串匹配) 。模式匹配成功是指在主串 S 中能够找到模式串 T，否则，称模式串 T 在主串 S 中不存在。(注意算法描述都是从 1 开始，c 语言设计是从 0 开始)
KMP算法
例:设有串 s=“abacabab” ，t=“abab” 。则第一次匹配过程如图所示。
定义 next[j]函数为:
例:若模式串 P 为’ abaabc’，由定义可得 next 函数值(从头尾比较相等的串)
j = 1 next[1] = 0
j = 2 a next[2] = 1
j = 3 ab next[3] = 1
j = 4 aba next[4] = 2
j = 5 abaa next[5] = 2
j = 6 abaab next[6] = 3
主串 S = 'a c a b a a b a a b c a c a a b c'
模式串 P = 'a b a a b c'
② 线性表的散列方法是什么
散列表又叫做哈希表
1. 引言
哈希表（Hash Table）的应用近两年才在NOI中出现，作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。
哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。
哈希表又叫做散列表，分为“开散列” 和“闭散列”。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的“哈希表”仅指“闭散列”，关于其他方面读者可参阅其他书籍。
2. 基础操作
2.1 基本原理
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。
总的来说，“直接寻址”与“解决冲突”是哈希表的两大特点。
2.2 函数构造
构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：
a) 除余法：
选择一个适当的正整数 p ，令 h(k ) = k mod p
这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。
b) 数字选择法：
如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。
2.3 冲突处理
线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。
2.4 支持运算
哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。
设插入的元素的关键字为 x ，A 为存储的数组。
初始化比较容易，例如
const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素
p=9997; // 表的大小
procere makenull;
var i:integer;
begin
for i:=0 to p-1 do
A[i]:=empty;
End;
哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：
function h(x:longint):Integer;
begin
h:= x mod p;
end;
我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locate
function locate(x:longint):integer;
var orig,i:integer;
begin
orig:=h(x);
i:=0;
while (i<S)and(A[(orig+i)mod S]<>x)and(A[(orig+i)mod S]<>empty) do
inc(i);
//当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元
//素存储的单元，要么表已经满了
locate:=(orig+i) mod S;
end;
插入元素
procere insert(x:longint);
var posi:integer;
begin
posi:=locate(x); //定位函数的返回值
if A[posi]=empty then A[posi]:=x
else error; //error 即为发生了错误，当然这是可以避免的
end;
查找元素是否已经在表中
procere member(x:longint):boolean;
var posi:integer;
begin
posi:=locate(x);
if A[posi]=x then member:=true
else member:=false;
end;
这些就是建立在哈希表上的常用基本运算。
下文提到的所有程序都能在附录中找到。
3. 效率对比
3.1简单的例子与实验
下面是一个比较简单的例子：
===================================================================
集合 ( Subset )
问题描述：
给定两个集合A、B，集合内的任一元素x满足1 ≤ x ≤ 109，并且每个集合的元素个数不大于104 个。我们希望求出A、B之间的关系。只需确定在B 中但是不在 A 中的元素的个数即可。
这个题目是根据 OIBH NOIP 2002 模拟赛 # 1 的第一题改编的。
分析：我们先不管A 与 B 的具体关系如何，注意到这个问题的本质就是对于给定的集合A ，确定B 中的元素是否在 A 中。所以，我们使用哈希表来处理。至于哈希函数，只要按照除余法就行了，由于故意扩大了原题的数据规模， H(x) = x mod 15889;
当然本题可以利用别的方法解决，所以选取了速度最快的快速排序+二分查找，让这两种方法作效率对比。
我们假定 |A|=|B| ，对于随机生成的数据，计算程序重复运行50次所用时间。
对比表格如下：
哈希表（sec） 快速排序+二分查找(sec)
复杂度 O(N) (只有忽略了冲突才是这个结果。当然实际情况会比这个大，但是重复的几率与哈希函数有关，不容易估计) O(N log N+ N) = O(N log N)
测试数据规模 —— ——
500 0.957 0.578
1000 1.101 0.825
2500 1.476 1.565
5000 2.145 2.820
7500 2.905 4.203
10000 3.740 5.579
13500 7.775 7.753
15000 27.550 8.673
对于数据的说明：在 Celeron566 下用 TP 测试，为了使时间的差距明显，让程序重复运了行50次。同时哈希表中的P= 15889 ，下标范围 0..15888 。由于快速排序不稳定，因此使用了随机数据。
3．2 对试验结果的分析：
注意到两个程序的用时并不像我们期望的那样，总是哈希表快。设哈希表的大小为 P .
首先，当规模比较小的时候（大约为a< 10% * P，这个数据仅仅是通过若干数据估记出来的，没有严格证明，下同），第二种方法比哈希表快。这是由于，虽然每次计算哈希函数用O(1) 的时间，但是这个系数比较大。例如这道题的 H(x)=x mod 15589 ，通过与做同样次数的加法相比较，测试发现系数 > 12 ，因为 mod 运算本身与快速排序的比较大小和交换元素运算相比，比较费时间。所以规模小的时候，O(N)（忽略冲突）的算法反而不如 O(NlogN)。这一点在更复杂的哈希函数上会体现的更明显，因为更复杂的函数系数会更大。
其次，当规模稍大 （大约为 15%*P < a < 85%*P） 的时候，很明显哈希表的效率高。这是因为冲突的次数较少。
再次，当规模再大 （大约为 90%*P < a < P ）的时候，哈希表的效率大幅下降。这是因为冲突的次数大大提高了，为了解决冲突，程序不得不遍历一段都存储了元素的数组空间来寻找空位置。用白箱测试的方法统计，当规模为13500的时候，为了找空位置，线性重新散列平均做了150000 次运算；而当规模为15000 的时候，平均竟然高达2000000 次运算，某些数据甚至能达到4265833次。显然浪费这么多次运算来解决冲突是不合算的，解决这个问题可以扩大表的规模，或者使用“开散列”（尽管它是动态数据结构）。然而需要指出的是，冲突是不可避免的。
初步结论：
当数据规模接近哈希表上界或者下界的时候，哈希表完全不能够体现高效的特点，甚至还不如一般算法。但是如果规模在中央，它高效的特点可以充分体现。我们可以从图像直观的观察到这一点。
试验表明当元素充满哈希表的 90% 的时候，效率就已经开始明显下降。这就给了我们提示：如果确定使用哈希表，应该尽量使数组开大（由于竞赛中可利用内存越来越多，大数组通常不是问题，当然也有少数情况例外），但对最太大的数组进行操作也比较费时间，需要找到一个平衡点。通常使它的容量至少是题目最大需求的 120% ，效果比较好（这个仅仅是经验，没有严格证明）。
4. 应用举例
4.1 应用的简单原则
什么时候适合应用哈希表呢？如果发现解决这个问题时经常要询问：“某个元素是否在已知集合中？”，也就是需要高效的数据存储和查找，则使用哈希表是最好不过的了！那么，在应用哈希表的过程中，值得注意的是什么呢？
哈希函数的设计很重要。一个不好的哈希函数，就是指造成很多冲突的情况，从前面的例子已经可以看出来，解决冲突会浪费掉大量时间，因此我们的目标就是尽力避免冲突。前面提到，在使用“除余法”的时候，h(k)=k mod p ，p 最好是一个大素数。这就是为了尽力避免冲突。为什么呢？假设 p=1000 ，则哈希函数分类的标准实际上就变成了按照末三位数分类，这样最多1000类，冲突会很多。一般地说，如果 p 的约数越多，那么冲突的几率就越大。
简单的证明：假设 p 是一个有较多约数的数，同时在数据中存在 q 满足 gcd(p,q)=d >1 ，即有 p=a*d , q=b*d, 则有 q mod p= q – p* [q div p] =q – p*[b div a] . ① 其中 [b div a ] 的取值范围是不会超过 [0，b] 的正整数。也就是说， [b div a] 的值只有 b+1 种可能，而 p 是一个预先确定的数。因此 ① 式的值就只有 b+1 种可能了。这样，虽然mod 运算之后的余数仍然在 [0，p-1] 内，但是它的取值仅限于 ① 可能取到的那些值。也就是说余数的分布变得不均匀了。容易看出， p 的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越高。而素数的约数是最少的，因此我们选用大素数。记住“素数是我们的得力助手”。
另一方面，一味的追求低冲突率也不好。理论上，是可以设计出一个几乎完美，几乎没有冲突的函数的。然而，这样做显然不值得，因为这样的函数设计很浪费时间而且编码一定很复杂，与其花费这么大的精力去设计函数，还不如用一个虽然冲突多一些但是编码简单的函数。因此，函数还需要易于编码，即易于实现。
综上所述，设计一个好的哈希函数是很关键的。而“好”的标准，就是较低的冲突率和易于实现。
另外，使用哈希表并不是记住了前面的基本操作就能以不变应万变的。有的时候，需要按照题目的要求对哈希表的结构作一些改进。往往一些简单的改进就可以带来巨大的方便。
这些只是一般原则，真正遇到试题的时候实际情况千变万化，需要具体问题具体分析才行。