查找是在大量的信息中尋找一個特定的信息元素，在計算機應用中，查找是常用的基本運算，例如編譯程序中符號表的查找本文主要介紹比較難理解的樹表查找和哈希查找。

查找定義：根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的數據元素（或記錄）。

查找算法分類：

1）靜態查找和動態查找；

注：靜態或者動態都是針對查找表而言的。動態表指查找表中有刪除和插入操作的表。

2）無序查找和有序查找。

無序查找：被查找數列有序無序均可；

有序查找：被查找數列必須為有序數列。

平均查找長度（Average Search Length，ASL）：需和指定key進行比較的關鍵字的個數的期望值，稱為查找算法在查找成功時的平均查找長度。

對于含有n個數據元素的查找表，查找成功的平均查找長度為：ASL = Pi*Ci的和。

Pi：查找表中第i個數據元素的概率。

Ci：找到第i個數據元素時已經比較過的次數。

Btree創建過程詳細介紹

M階的Btree的幾個重要特性：

1.結點最多含有m顆子樹，m-1個關鍵字（m>=2）；

2.除根結點和葉子結點外，其它每個結點至少有ceil(m / 2)個子節點，ceil為上取整；

3.若根節點不是葉子節點，則至少有兩顆子樹。

例子：

創建一個5階的Btree。插入的數據有：

3 14 7 1 8 5 11 17 13 6 23 12 20 26 4 16 18 24 25 19

根據Btree特性，5階則一個磁盤空間最多有5個指針（存的查找路徑 ），4個關鍵字(mysql存的數據)。那么具體的插入如下所示：

插入3

插入14

插入7

插入1

插入8，此時發現空間不夠，這時會出現一個分裂，移動中間元素到根節點即得到如下圖：

插入5

插入11,17

插入13：需要注意，此時Btree又會進行一次分裂，這分裂需要注意下13會移到根節點

后面的插入就不一一舉例了，自己驗證下。最后得到的這棵樹如下所示：

以上操作為Btree的詳細構建過程，在構建的時候主要需要注意的就是分裂，分裂后一定要判定是否符合Btree的特性，是否是一顆有序的數，左邊一定小于右邊，葉子節點是否已經大于階數，葉子節點的最小數目為ceil(m(這里為5)/2)-1=2等。有時候一個數字插入的時候會進行多次分裂操作，需要特別注意。

B+Tree和BTree類似，只是B+Tree非葉子節點不會存儲數據，所有的數據都存儲在葉子節點，其目的主要增加了系統的穩定性。

B和B+樹的區別在于，B+樹的非葉子結點只包含導航信息，不包含實際的值，所有的葉子結點和相連的節點使用鏈表相連，便于區間查找和遍歷。

B+ 樹的優點在于：

由于B+樹在內部節點上不好含數據信息，因此在內存頁中能夠存放更多的key。 數據存放的更加緊密，具有更好的空間局部性。因此訪問葉子幾點上關聯的數據也具有更好的緩存命中率。

B+樹的葉子結點都是相鏈的，因此對整棵樹的便利只需要一次線性遍歷葉子結點即可。而且由于數據順序排列并且相連，所以便于區間查找和搜索。而B樹則需要進行每一層的遞歸遍歷。相鄰的元素可能在內存中不相鄰，所以緩存命中性沒有B+樹好。

但是B樹也有優點，其優點在于，由于B樹的每一個節點都包含key和value，因此經常訪問的元素可能離根節點更近，因此訪問也更迅速。

哈希查找

什么是哈希表（Hash）？

我們使用一個下標范圍比較大的數組來存儲元素。可以設計一個函數（哈希函數， 也叫做散列函數），使得每個元素的關鍵字都與一個函數值（即數組下標）相對應，于是用這個數組單元來存儲這個元素；也可以簡單的理解為，按照關鍵字為每一個元素"分類"，然后將這個元素存儲在相應"類"所對應的地方。但是，不能夠保證每個元素的關鍵字與函數值是一一對應的，因此極有可能出現對于不同的元素，卻計算出了相同的函數值，這樣就產生了"沖突"，換句話說，就是把不同的元素分在了相同的"類"之中。后面我們將看到一種解決"沖突"的簡便做法。

總的來說，"直接定址"與"解決沖突"是哈希表的兩大特點。

什么是哈希函數？

哈希函數的規則是：通過某種轉換關系，使關鍵字適度的分散到指定大小的的順序結構中，越分散，則以后查找的時間復雜度越小，空間復雜度越高。

算法思想：哈希的思路很簡單，如果所有的鍵都是整數，那么就可以使用一個簡單的無序數組來實現：將鍵作為索引，值即為其對應的值，這樣就可以快速訪問任意鍵的值。這是對于簡單的鍵的情況，我們將其擴展到可以處理更加復雜的類型的鍵。

算法流程：

1）用給定的哈希函數構造哈希表；

2）根據選擇的沖突處理方法解決地址沖突；

常見的解決沖突的方法：拉鏈法和線性探測法。詳細的介紹可以參見：淺談算法和數據結構: 十一 哈希表。

3）在哈希表的基礎上執行哈希查找。

哈希表是一個在時間和空間上做出權衡的經典例子。如果沒有內存限制，那么可以直接將鍵作為數組的索引。那么所有的查找時間復雜度為O(1)；如果沒有時間限制，那么我們可以使用無序數組并進行順序查找，這樣只需要很少的內存。哈希表使用了適度的時間和空間來在這兩個極端之間找到了平衡。只需要調整哈希函數算法即可在時間和空間上做出取舍。

復雜度分析：

單純論查找復雜度：對于無沖突的Hash表而言，查找復雜度為O(1)（注意，在查找之前我們需要構建相應的Hash表）。

使用Hash

我們在實際編程中存儲一個大規模的數據，最先想到的存儲結構可能就是map，也就是我們常說的KV pair，經常使用Python的博友可能更有這種體會。使用map的好處就是，我們在后續處理數據處理時，可以根據數據的key快速的查找到對應的value值。map的本質就是Hash表，那我們在獲取了超高查找效率的基礎上，我們付出了什么？

Hash是一種典型以空間換時間的算法，比如原來一個長度為100的數組，對其查找，只需要遍歷且匹配相應記錄即可，從空間復雜度上來看，假如數組存儲的是byte類型數據，那么該數組占用100byte空間。現在我們采用Hash算法，我們前面說的Hash必須有一個規則，約束鍵與存儲位置的關系，那么就需要一個固定長度的hash表，此時，仍然是100byte的數組，假設我們需要的100byte用來記錄鍵與位置的關系，那么總的空間為200byte,而且用于記錄規則的表大小會根據規則，大小可能是不定的。

歡迎關注轉發評論~~

Btree創建過程詳細介紹圖文演示效果不是很好，我錄制好有圖文加視頻配合講解更容易理解需要的請加QQ群938837867暗號回復“555”贈送一些Dubbo、Redis、Netty、zookeeper、Spring cloud、分布式資料

總結

以上是生活随笔為你收集整理的Java高级工程师必备数据结构算法高效查找算法原理分析与实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。