知識點梳理：資料結構與算法——檢索

線性表的檢索

二分檢索

mid-1/mid+1

成功的平均檢索長度：

（畫出樹來，第i層的元素經過i次檢索到）

ASL ⁡ = 1 n ( ∑ i = 1 j i ⋅ 2 i − 1 ) = n + 1 n log ⁡ 2 ( n + 1 ) − 1 ≈ log ⁡ 2 ( n + 1 ) − 1 \begin{aligned} \operatorname{ASL} &=\frac{1}{n}\left(\sum_{i=1}^{j} i \cdot 2^{i-1}\right) \\ &=\frac{n+1}{n} \log _{2}(n+1)-1 \\ & \approx \log _{2}(n+1)-1 \end{aligned} ASL​=n1​(i=1∑j​i⋅2i−1)=nn+1​log2​(n+1)−1≈log2​(n+1)−1​

使用條件：要排序、順序存儲；不易更新

分塊檢索

塊内無序，塊間有序

索引表：各塊中最大關鍵碼、各塊起始位置、塊中有效元素個數

A S L = A S L b + A S L w ASL=ASL_b+ASL_w ASL=ASLb​+ASLw​(塊間+塊内)

缺點：增加一個輔助索引表；初始有分塊排序；元素大量增删/分布不均勻

散清單的檢索（Hash)

重要概念：

負載因子： α = n / M \alpha=n/M α=n/M(n:散清單結點數，M:散清單空間大小)

沖突：将不同關鍵碼映射到相同的散列位址

同義詞：發生沖突的兩個關鍵碼

沖突解決方法：

• 開散列（拉鍊法）：

  同義詞都連結在同一連結清單 α \alpha α可>1

  • 拉鍊方法（适用于記憶體）

    處理沖突簡單

    缺點：同義詞表中的元素可能存儲在不同磁盤頁中，檢索一個關鍵碼值時可能引起多次磁盤通路，進而增加檢索時間（即元素數量超過了一個頁塊的儲存空間）

  • 桶式散列（适用于外存）

    散列檔案記錄分為若幹桶，每個桶包含若幹頁塊

    桶内各頁塊用指針連結

    h(K)表示具有關鍵碼K的記錄所在的桶号

    磁盤通路：調存儲桶目錄表進入記憶體（1次訪外）；逐個檢查桶内各頁塊（平均：頁塊數/2次訪外）【與拉鍊法對比，目的是盡量把同一個桶中出現的元素塞到同一個頁塊中】

• 閉散列（開位址法）：

  發生沖突的關鍵碼存儲在散清單中另一個空位址内

  d 0 = h ( K ) d_0=h(K) d0​=h(K)稱為基位址

  當沖突發生時，使用某種方法為關鍵碼K生成一個候選的散列位址序列，稱為探查序列

  d i = d 0 + p ( K , i ) d_i=d_0+p(K,i) di​=d0​+p(K,i)是後繼散列位址，p(K,i)為探查函數

  探查方法：

  • 線性探查法：缺點：對應連續的基位址，探查序列也是幾乎相同的

    聚集：基位址不同的記錄，争奪同一後繼位址序列

    成功/失敗查找ASL的計算：注意取模的散列函數基位址可能不會占整個散清單

  • 二次探查法：基本解決了不同基位址探查序列重合

    d 2 i − 1 = ( d + i 2 ) % M d_{2i-1}=(d+i^2)\%M d2i−1​=(d+i2)%M; d 2 i = ( d − i 2 ) % M d_{2i}=(d-i^2)\%M d2i​=(d−i2)%M

  • 僞随機數序列探查法：越随機越好，缺點：随機序列需要儲存

  基本聚集：基位址不同的關鍵碼，其探查序列的某些段重疊在一起【僞随機探查和二次探查可以消除基本聚集】

  二級聚集：如果兩個關鍵碼散列到同一個基位址，還是得到同樣的探查序列，所産生的聚集（探查序列隻是基位址的函數，與關鍵碼無關）

  • 雙散列探查法：同義詞的探查序列與同義詞本身關鍵碼有關（一個基位址上有不同的探查序列）

注意%M

注意失敗查找（各種樹那裡沒找到就是失敗，不用多一個，散清單區分開！！！

注意散清單非mod值基位址通路的計數！！！