查找

查找表是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。
關(guān)鍵字是數(shù)據(jù)元素中某個數(shù)據(jù)項的值青责，也稱為鍵值均抽，用它可以標(biāo)識一個數(shù)據(jù)元素嫁赏。也可以標(biāo)識一個記錄的某個數(shù)據(jù)項，稱為關(guān)鍵碼到忽。若此關(guān)鍵字可以唯一標(biāo)識一個記錄橄教，則稱為該關(guān)鍵字為主關(guān)鍵字。主關(guān)鍵字所在的數(shù)據(jù)項稱為主關(guān)鍵碼喘漏。
對于那些可以識別的多個數(shù)據(jù)元素或記錄的關(guān)鍵字护蝶，稱之為次關(guān)鍵字。
查找就是根據(jù)給定的某個值翩迈，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或記錄持灰。
查找表按照操作方式來分由兩大種：靜態(tài)查找表和動態(tài)查找表。

靜態(tài)查找表
只作查找操作的查找表负饲。它的主要操作有：
（1） 查詢某個“特定的”數(shù)據(jù)元素是否在查找表中
（2）檢索某個“特定”的數(shù)據(jù)元素和各種屬性

動態(tài)查找表
在查找過程中同時插入查找表不存在的數(shù)據(jù)元素堤魁，或者從查找表中刪除已經(jīng)存在的某個數(shù)據(jù)元素。動態(tài)查找表的操作有：
（1）查找時插入數(shù)據(jù)元素
（2）查找時刪除數(shù)據(jù)元素

為了提高查找的效率返十，需要專門為查找操作設(shè)置數(shù)據(jù)結(jié)構(gòu)妥泉，這種面向查找的數(shù)據(jù)結(jié)構(gòu)稱為查找結(jié)構(gòu)。

邏輯上洞坑，查找所基于的數(shù)據(jù)結(jié)構(gòu)是集合盲链，集合中的記錄之間沒有本質(zhì)關(guān)聯(lián)。為了得到較高的查找性能迟杂，就需要改變數(shù)據(jù)元素之間的關(guān)系刽沾，在存儲時可以將查找集合組織成表、樹等結(jié)構(gòu)排拷。

順序表查找
順序查找又叫線性查找侧漓，是最基礎(chǔ)的查找技術(shù)，其查找過程： 從表中的第一個或最后一個記錄開始监氢，逐個查找記錄的關(guān)鍵字和給定值進(jìn)行比較布蔗，相等則查找成功，返回查找到的記錄忙菠；直到最后一個或第一個記錄幼东，其關(guān)鍵字都不能和給定值匹配，則表中不存在所查找的記錄卧波，查找不成功惹恃。
順序表查找的時間復(fù)雜度為O（n），當(dāng)n較大時傍睹，查找效率低隔盛。

有序表查找
有序表是指數(shù)據(jù)元素已經(jīng)按照某個順序進(jìn)行有序排列。在有序表的基礎(chǔ)上拾稳，分為折半查找吮炕、插值查找、斐波那契查找访得。
折半查找
折半查找技術(shù)龙亲，又稱為二分查找陕凹。前提是線性表中的記錄必須是關(guān)鍵碼有序，線性表必須采用順序存儲鳄炉。折半查找的基本思想： 在有序表中杜耙，取中間記錄作為比較對象，若給定值與中間記錄的關(guān)鍵字相等拂盯，則查找成功佑女，若給定值小于中間值，則在中間記錄左半?yún)^(qū)查找谈竿；若大于中間值团驱，則在中間記錄右半?yún)^(qū)繼續(xù)查找，不斷重復(fù)上述過程空凸，直到成功嚎花，或者所有區(qū)域?yàn)闊o記錄，則不存在呀洲。
折半查找的時間復(fù)雜度為O（logn）
插值查找
插值查找根據(jù)要查找的關(guān)鍵字與查找表中的最大最小紀(jì)錄的關(guān)鍵字比較之后的查找方法贩幻，根據(jù)要查找的值與最大最小值差的比例來分配下標(biāo)和查找區(qū)域，在折半查找的基礎(chǔ)上加以改進(jìn)：
mid=low+((key-a[low])/(a[high]-a[low]))*(high-low)
該算法從時間復(fù)雜度來說也是O（logn）两嘴，對于數(shù)據(jù)分布比較均勻的查找表其效率高于折半查找丛楚，但對于分布極不均勻的情況下并不太適合使用
斐波那契查找
斐波那契查找利用黃金分割原理實(shí)現(xiàn)。
其每次取的比較值的下標(biāo)按照黃金分割比切開憔辫，分別比較左側(cè)和右側(cè)區(qū)域趣些，因此首先根據(jù)查詢數(shù)組的長度n在斐波那契數(shù)列中的位置，確定分割點(diǎn)的下標(biāo)位置贰您，并補(bǔ)齊數(shù)組長度n的后續(xù)位置坏平，防止越界。如果比較結(jié)果給定值小于分割點(diǎn)下標(biāo)對應(yīng)值锦亦，則下一輪查詢在左半?yún)^(qū)舶替，查詢個數(shù)為F[k-1],k為n在斐波那契數(shù)列中位置對應(yīng)下標(biāo)，如果比較結(jié)果給定值大于分割點(diǎn)下標(biāo)位置杠园，則下一輪查詢在右半?yún)^(qū)進(jìn)行顾瞪，查詢個數(shù)為F[k-2]，因?yàn)镕[k]=F[k-1] +F[k-2]

線性索引查找
對于無序的大量數(shù)據(jù)查找抛蚁，通過索引快速查找所需數(shù)據(jù)陈醒。
索引是為了加快查找速度而設(shè)計的數(shù)據(jù)結(jié)構(gòu)，該過程通過把關(guān)鍵字與它對應(yīng)的記錄相關(guān)聯(lián)瞧甩。
一個索引由若干個索引項構(gòu)成钉跷，每個索引項至少應(yīng)包含關(guān)鍵字和其對應(yīng)的記錄在存儲器中的位置等信息。索引技術(shù)是組織大型數(shù)據(jù)庫以及磁盤文件的一種重要技術(shù)肚逸。
索引按照結(jié)構(gòu)可以分為：線性索引爷辙、樹形索引彬坏、多級索引。

線性索引是將索引項集合組織為線性結(jié)構(gòu)膝晾，也稱索引表苍鲜。
常見的三種線性索引：稠密索引、分塊索引玷犹、倒排索引。

稠密索引
稠密索引是指在線性索引中洒疚，將數(shù)據(jù)集中的每個記錄對應(yīng)一個索引項歹颓。

image

分塊索引
稠密索引因?yàn)樗饕椗c數(shù)據(jù)集的記錄個數(shù)相同，所以空間代價很大喊括。為了減少索引項的個數(shù)胧瓜，對數(shù)據(jù)集進(jìn)行分塊，使其分塊有序郑什，對每一塊建立索引項府喳，從而減少索引項的個數(shù)。
分塊有序蘑拯，將數(shù)據(jù)集的記錄分成若干塊钝满，并滿足：

• 塊內(nèi)無序，每一塊內(nèi)的記錄不要求有序申窘。
• 塊間有序弯蚜，第二塊的所有記錄的關(guān)鍵字均要大于第一塊的所有記錄的關(guān)鍵字，后續(xù)類推

對于分塊有序的數(shù)據(jù)集剃法，將每塊對應(yīng)一個索引項碎捺，這種索引方法叫做分塊索引。分塊索引的索引項分為三個數(shù)據(jù)項：

• 最大關(guān)鍵碼存儲每一塊數(shù)據(jù)集的最大關(guān)鍵字贷洲，使得下一塊中最小關(guān)鍵碼比這塊的最大關(guān)鍵碼要大
• 塊中記錄個數(shù)牵寺，便于循環(huán)時使用
• 指向塊首的數(shù)據(jù)指針便于開始對這一塊的數(shù)據(jù)進(jìn)行遍歷

image

分塊索引表中查找分兩步進(jìn)行：

1. 在分塊索引表中查找關(guān)鍵字所在的塊，分塊索引表是塊間有序的恩脂，因此可以利用折半帽氓、插值等算法查找
2. 根據(jù)塊首指針找到相應(yīng)塊，并在塊中順序查找關(guān)鍵碼俩块。塊內(nèi)可以是無序的黎休，因此使用順序查找浓领。

分塊索引的平均查找長度為 n^(1/2)+1 ,其搜索效率比起順序查找O(n)效率要高，不過比不上折半查找的log(n)效率势腮。

倒排索引
倒排索引的通用結(jié)構(gòu)：

• 次關(guān)鍵碼
• 記錄號表

記錄號表中存儲具有相同次關(guān)鍵字的所有記錄的記錄號（可以是指向記錄的指針或是該記錄的主關(guān)鍵字）联贩。使用這種方式的索引方法為倒排索引。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄地址捎拯，由于不是由地址來確定屬性值泪幌，而是由屬性值確定記錄的位置，因此稱為倒排索引署照。

二叉排序樹
又稱為二叉查找樹祸泪，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：

• 若它的左子樹不空建芙，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)構(gòu)的值
• 若它的右子樹不空没隘，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)構(gòu)的值
• 它的左右子樹也分別是二叉排序樹

二叉排序樹首先一顆二叉樹，采用遞歸的定義方法禁荸，它的結(jié)點(diǎn)間滿足一定的次序關(guān)系右蒲，左子樹結(jié)點(diǎn)一定比雙親結(jié)點(diǎn)值小，右子樹結(jié)點(diǎn)一定比雙親結(jié)點(diǎn)大
二叉排序樹的構(gòu)造赶熟，并不是為了排序瑰妄，而是為了提高查找、插入映砖、刪除關(guān)鍵字的效率翰撑。在一個有序數(shù)據(jù)集上的查找，其效率是要高于無序數(shù)據(jù)集的啊央，同時二叉樹這樣的非線性結(jié)構(gòu)眶诈，有利于插入和刪除的實(shí)現(xiàn)。

二叉排序樹通過鏈?zhǔn)酱鎯霞ⅲ３至随準(zhǔn)酱鎯υ趫?zhí)行插入或刪除時不用移動元素的優(yōu)點(diǎn)逝撬，找到合適的插入和刪除位置后，僅僅修改指針即可乓土。對于二叉排序樹的查找宪潮，走的是從根結(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑，比較次數(shù)為給定值的結(jié)點(diǎn)在二叉排序樹的層數(shù)趣苏，極端情況為根結(jié)點(diǎn)即為要查找結(jié)點(diǎn)狡相，這樣只需一次，最多不會超過樹的深度食磕。因此二叉排序樹的查找性能取決于二叉排序樹的形狀尽棕，如果是極端的左斜樹或右斜樹，那么其查找效率比不上左右相對平衡的二叉樹彬伦。因此滔悉，最好將二叉樹構(gòu)建為平衡二叉樹伊诵。

平衡二叉樹
平衡二叉樹是一種二叉排序樹，其中每一個節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1回官。平衡二叉樹是一種高度平衡的二叉排序樹曹宴。要么它是一棵空樹，要么左子樹和右子樹都是平衡二叉樹歉提，且左子樹和右子樹的深度差絕對值不超過1笛坦。將二叉樹上結(jié)點(diǎn)的左子樹減去右子樹深度的值稱為平衡因子BF（Balance Factor）那么平衡二叉樹的平衡因子只能是-1,0或1。也就是說苔巨，只要二叉樹上有一個結(jié)點(diǎn)的平衡因子絕對值大于1版扩，二叉樹就是不平衡的。平衡二叉樹的前提是：首先它是一顆二叉排序樹

image.png

距離插入點(diǎn)最近的恋拷，且平衡因子絕對值大于1的結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹，稱為最小不平衡子樹

image

平衡二叉樹實(shí)現(xiàn)原理
平衡二叉樹構(gòu)建的基本原理是在構(gòu)建二叉排序樹的過程中厅缺，每當(dāng)插入一個結(jié)點(diǎn)時蔬顾，檢查是否因?yàn)樾碌牟迦攵茐牧藰涞钠胶庑裕绻窍嫔樱页鲎钚〔黄胶庾訕渚骰怼Ｔ诒３侄媾判驑涞奶匦韵拢{(diào)整最小不平衡子樹的各個節(jié)點(diǎn)之間的關(guān)系窥妇，進(jìn)行相應(yīng)的旋轉(zhuǎn)舷胜，使之成為新的平衡子樹。

image

image

image

image

image

image

多路查找樹(B樹)
之前涉及的樹結(jié)構(gòu)峦树，都是一個節(jié)點(diǎn)可以有多個孩子，但自身只存儲一個元素旦事。而二叉樹的限制更多魁巩，結(jié)點(diǎn)最多只能有兩個孩子。一個結(jié)點(diǎn)只能存儲一個元素姐浮。在元素數(shù)量非常多的時候谷遂，樹的度要么很大，要么深度值很大卖鲤，這樣在數(shù)據(jù)的存取時埋凯，會成為時間效率上的瓶頸点楼，這樣需要打破一個結(jié)點(diǎn)只能存儲一個元素的限制，對此引入多路查找樹白对。
多路查找樹掠廓，其每一個節(jié)點(diǎn)的孩子樹可以多于兩個，每個結(jié)點(diǎn)可以存儲多個元素甩恼。而且它是查找樹蟀瞧，所有元素之間存在特定的排序關(guān)系。
對于每一個結(jié)點(diǎn)存儲多少個元素条摸，以及孩子樹的數(shù)量悦污，有4種常用的特殊形式：2-3樹、2-3-4樹钉蒲、B樹和B+樹切端。
2-3樹
2-3樹每一個節(jié)點(diǎn)都具有2個孩子（也稱為2結(jié)點(diǎn)）或3個孩子（也稱為3結(jié)點(diǎn)）。
一個2結(jié)點(diǎn)包含一個元素和兩個孩子（或沒有孩子）顷啼，與二叉排序樹類似踏枣，左子樹包含元素小于該元素，右子樹包含元素大于該元素钙蒙。2結(jié)點(diǎn)要么有2個孩子茵瀑，要么沒有孩子。
一個3結(jié)點(diǎn)包含一大一小兩個元素和三個孩子（或沒有孩子）躬厌，一個3結(jié)點(diǎn)要么有3個孩子马昨，要么沒孩子。如果3結(jié)點(diǎn)右孩子扛施，左子樹包含小于較小元素的元素鸿捧，右子樹包含大于較大元素的元素，中間子樹包含介于兩元素之間的元素疙渣。
2-3樹的所有葉子結(jié)點(diǎn)都在同一層次笛谦。

image

2-3-4樹
2-3-4樹是2-3樹的擴(kuò)展概念，包括了一個4結(jié)點(diǎn)昌阿，4結(jié)點(diǎn)包含小中大三個元素和4個孩子（或沒有孩子）饥脑，4結(jié)點(diǎn)有孩子的話，左子樹小于最小的元素懦冰，第二子樹大于最小元素小于中間元素灶轰，第三子樹大于中間元素小于最大元素，右子樹大于最大元素刷钢。

B樹（B-tree）
B樹是一種平衡的多路查找樹笋颤，2-3樹和2-3-4樹都是B樹的特例。結(jié)點(diǎn)最大的孩子數(shù)目稱為B樹的階，因此2-3樹是3階B樹伴澄，2-3-4樹是4階B樹赋除。
一個m階的B樹具有如下屬性：

• 如果根結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則其至少有兩顆子樹
• 每一個非根的分支結(jié)點(diǎn)都有k-1個元素和k個孩子非凌，其中[m/2]<=k<=m举农。每一個葉子結(jié)點(diǎn)n都有k-1個元素，其中[m/2]<=k<=m（結(jié)點(diǎn)少于[m/2]就需要合并了）
• 所有葉子結(jié)點(diǎn)都位于同一層次
• 所有分支節(jié)點(diǎn)包含下列信息數(shù)據(jù)（n,A0,K1,A1,K2......,An,Kn）敞嗡，其中：Ki為關(guān)鍵字颁糟，Ki<Ki-1，Ai為指向子樹根節(jié)點(diǎn)的指針喉悴，且指針Ai-1所指子樹中的所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki棱貌，An所指子樹的所有結(jié)點(diǎn)的關(guān)鍵字均小于Kn
  
  image
  
  關(guān)于n個結(jié)點(diǎn)的m階B樹，需要查找的最壞的的情況：
  
  image
  
  個人認(rèn)為查找不成功的結(jié)點(diǎn)為 n-1箕肃，而非是n+1

B+樹
在B樹結(jié)構(gòu)中婚脱，如果要遍歷B樹，假設(shè)每個結(jié)點(diǎn)屬于硬盤的不同頁面勺像，往返于每個結(jié)點(diǎn)之間意味著在硬盤的不同頁面之間進(jìn)行多次訪問障贸，如圖：

image

image

• 有n棵子樹的結(jié)點(diǎn)中包含有n個關(guān)鍵字（包含雙親的一個關(guān)鍵字）
• 葉子結(jié)點(diǎn)包含所有的關(guān)鍵字信息豺瘤，以及指向包含關(guān)鍵字記錄的指針吆倦，葉子結(jié)點(diǎn)本身根據(jù)關(guān)鍵字的大小從小到大進(jìn)行順序鏈接
• 所有的分支節(jié)點(diǎn)是索引，結(jié)點(diǎn)中僅包含其子樹中的最大（或最凶蟆）關(guān)鍵字 蚕泽，不會存關(guān)鍵字記錄的指針，所有的數(shù)據(jù)地址必須到葉子節(jié)點(diǎn)才能獲取到桥嗤，因此每次數(shù)據(jù)查詢次數(shù)一樣

散列表查找
散列技術(shù)是在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系f须妻，使得每個關(guān)鍵字key對應(yīng)一個存儲位置f（key）仔蝌。查找時，根據(jù)確定的對應(yīng)關(guān)系找到給定值key的映射f（key）,若查找集合中存在這個記錄荒吏，則必定在f（key）的位置上敛惊。
這種對應(yīng)關(guān)系f稱為散列函數(shù)，又稱為哈希函數(shù)（Hash）司倚。按照這個思想豆混，采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中，這塊連續(xù)的存儲空間稱為散列表或哈希表动知。關(guān)鍵字對應(yīng)的記錄存儲位置稱為散列地址皿伺。

散列過程

• 在存儲時，通過散列函數(shù)計算記錄的散列地址盒粮，并按照此散列地址存儲記錄
• 查找記錄時鸵鸥，通過同樣的散列函數(shù)計算記錄的散列地址，按照此散列地址訪問記錄丹皱。

散列技術(shù)既是一種存儲方法妒穴，又是一種查找方法。與線性表摊崭、樹讼油、圖等結(jié)構(gòu)不同的是，數(shù)據(jù)元素之間不存在某種邏輯關(guān)系呢簸，只與關(guān)鍵字關(guān)聯(lián)矮台。散列主要是面向查找的存儲結(jié)構(gòu)。
散列技術(shù)最適合的求解問題是查找與給定值相等的記錄根时。對于查找來說瘦赫，簡化了比較過程，效率會提高蛤迎。
散列技術(shù)不適合一個關(guān)鍵字對應(yīng)多條記錄的情況确虱，范圍查找，表中記錄排序等情況替裆。

散列函數(shù)構(gòu)造方法
兩個原則：

• 計算簡單
• 散列地址分布均勻

常用散列函數(shù)構(gòu)造方法：

• 直接定址法
  取關(guān)鍵字的某個線性函數(shù)值為散列地址：
  f(key)=a*key+b
  需要事先知道關(guān)鍵字的分布情況校辩，適合查找表較小且連續(xù)的情況。現(xiàn)實(shí)應(yīng)用中辆童，此法雖簡單宜咒，并不常用。

• 數(shù)字分析法
  數(shù)字分析法適合處理關(guān)鍵字位數(shù)較多的情況胸遇，如事先知道關(guān)鍵字的分布且關(guān)鍵字若干位分布均勻荧呐，可以考慮此法。

• 平方取中法
  比如關(guān)鍵字1234 平方 1522756 取中：227
  此法比較適合不知道關(guān)鍵字分布，位數(shù)又不是很大的情況

• 折疊法
  折疊法將關(guān)鍵字從左至右分割成相等幾部分疊加求和倍阐，按照散列表的長度概疆，取后幾位做為散列地址
  此法不需要知道關(guān)鍵字的分布，適合關(guān)鍵字位數(shù)較多的情況峰搪。

• 除留余數(shù)法
  該方法為最常用的構(gòu)造散列函數(shù)的方法岔冀，對于散列表長度為m的散列函數(shù)公式為：
  f(key)=key mode p(p<=m)
  若散列表長度為m，通常p為小于或等于表長（最好接近m）的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)概耻。

• 隨機(jī)數(shù)法
  選擇一個隨機(jī)數(shù)使套，取關(guān)鍵字的隨機(jī)函數(shù)值作為其散列地址。也就是f(key)=random(key)鞠柄。當(dāng)關(guān)鍵字的長度不等時侦高，可以采取此法。

處理散列沖突的方法

• 開放定址法
  一旦發(fā)生散列地址沖突厌杜，就去尋找下一個空的散列地址奉呛，只要散列表足夠大，空的散列地址總能找到夯尽，并將記錄存入瞧壮。其公式是：
  fi(key)=(f(key)+di) MOD m （di=1^2,-12...q^2,-q2,q<=m/2） 二次探測法
  fi(key)=(f(key)+di) MOD m （di是同一個隨機(jī)種子生成的隨機(jī)數(shù)） 隨機(jī)探測法

• 再散列函數(shù)法
  事先準(zhǔn)備多個散列函數(shù)：
  fi(key)=RHi(key) (i=1,2......k)
  RGi就是不同的散列函數(shù)，每次發(fā)生散列地址沖突時匙握，就換一個散列地址咆槽，相應(yīng)地會增加計算時間。

• 鏈地址法
  當(dāng)發(fā)生地址沖突時圈纺，將所有關(guān)鍵字的同義詞的記錄存儲在一個單鏈表中秦忿，這種表稱為同義詞子表，在散列表中只存儲所有同義詞表的頭指針赠堵。如對關(guān)鍵字集合{12,67,56,16,25,37,22,29,15,47,48,34}小渊，使用除留余數(shù)法褥，以12為除數(shù)茫叭，得到結(jié)構(gòu)：
  

  image

• 公共溢出區(qū)法
  將所有沖突的關(guān)鍵字建立一個公共溢出區(qū)來存放

  image
  
  對給定值通過散列函數(shù)計算散列地址后，先與基本表的相應(yīng)位置進(jìn)行比對半等，如果想等揍愁，則查找成功，如果不相等杀饵，到溢出表進(jìn)行順序查找莽囤。相對于基本表而言，在沖突數(shù)據(jù)較少的情況下切距，公共溢出區(qū)的結(jié)構(gòu)對查找性能來說還是較高朽缎。

散列查找表的性能分析
如果散列表中不存在沖突的情況，其查找效率是非常高效的，時間復(fù)雜度為O(1) 话肖。實(shí)際應(yīng)用中北秽，沖突不可避免，散列查找的平均查找長度與以下因素有關(guān)：

• 散列函數(shù)是否均勻
  散列函數(shù)的均勻程度影響沖突的頻繁程度

• 處理沖突的方法
  相同的關(guān)鍵字最筒，相同的散列函數(shù)贺氓，處理沖突的方法不同，平均查找長度不同床蜘。比如線性探測會產(chǎn)生堆積辙培，沒有二次探測好，而鏈地址法處理不會產(chǎn)生沖突

• 散列表的裝填因子
  裝填因子=記錄個數(shù)/散列表長度 邢锯，表示裝滿的程度扬蕊，不管記錄個數(shù)多大，選取合適的裝填因子可以使平均查找長度限定在一個范圍內(nèi)丹擎，通常散列表的空間設(shè)置比查找集合要大厨相，這樣沖突的可能性相對較小。