① 查找、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 的約數越多，發生這種余數分布不均勻的情況就越頻繁，沖突的幾率越高。而素數的約數是最少的，因此我們選用大素數。記住「素數是我們的得力助手」。
另一方面，一味的追求低沖突率也不好。理論上，是可以設計出一個幾乎完美，幾乎沒有沖突的函數的。然而，這樣做顯然不值得，因為這樣的函數設計很浪費時間而且編碼一定很復雜，與其花費這么大的精力去設計函數，還不如用一個雖然沖突多一些但是編碼簡單的函數。因此，函數還需要易於編碼，即易於實現。
綜上所述，設計一個好的哈希函數是很關鍵的。而「好」的標准，就是較低的沖突率和易於實現。
另外，使用哈希表並不是記住了前面的基本操作就能以不變應萬變的。有的時候，需要按照題目的要求對哈希表的結構作一些改進。往往一些簡單的改進就可以帶來巨大的方便。
這些只是一般原則，真正遇到試題的時候實際情況千變萬化，需要具體問題具體分析才行。