搜尋中常見資料結構與演算法探究_歐子有話說

1 前言

ES 現在已經被廣泛的使用在日常的搜尋中，Lucene 作為它的核心值得我們深入研究，比如 FST，下面就用兩篇分享來介紹一些本文的主題：

第一篇主要介紹資料結構和演算法基礎和分析方法，以及一些常用的典型的資料結構；
第二篇主要介紹圖論，以及自動機，KMP，FST 等演算法；
下面開始第一篇

2 引言

“演算法是電腦科學領域最重要的基石之一 “
“程式語言雖然該學，但是學習計算機演算法和理論更重要，因為計算機演算法和理論更重要，因為計算機語言和開發平臺日新月異，但萬變不離其宗的是那些演算法和理論，例如資料結構、演算法、編譯原理、計算機體系結構、關係型資料庫原理等等。“——《演算法的力量》

2.1 提出問題

2.1.1 案例一

設有一組 N 個數而要確定其中第 k 個最大者，我們稱之為選擇問題。常規的解法如下：

該問題的一種解法就是將這 N 個數讀進一個數組中，在通過某種簡單的演算法，比如氣泡排序法，以遞減順序將陣列排序，然後返回位置 k 上的元素。
稍微好一點的演算法可以先把前 k 個元素讀入陣列並對其排序。接著，將剩下的元素再逐個讀入。當新元素被讀到時，如果它小於陣列中的第 k 個元素則忽略之，否則就將其放到陣列中正確的位置上，同時將陣列中的一個元素擠出陣列。當演算法終止時，位於第 k 個位置上的元素作為答案返回。

這兩種演算法編碼都很簡單，但是我們自然要問：哪個演算法更好？哪個演算法更重要？還是兩個演算法都足夠好？使用 N=30000000 和 k=15000000 進行模擬將發現，兩個演算法在合理的時間量內均不能結束；每一種演算法都需要計算機處理若干時間才能完成。
其實還有很多可以解決這個問題，比如二叉堆，歸併演算法等等。

2.2.2 案例二

輸入是由一些字母構成的一個二維陣列以及一組單片語成。目標是要找出字謎中的單詞，這些單詞可能是水平、垂直、或沿對角線上任何方向放置。下圖所示的字謎由單詞 this、two、fat 和 that 組成。

現在至少也有兩種直觀的演算法來求解這個問題：

對單詞表中的每個單詞，我們檢查每一個有序三元組（行，列，方向）驗證是否有單詞存在。這需要大量巢狀的 for 迴圈，但它基本上是直觀的演算法。
對於每一個尚未越出迷板邊緣的有序四元組（行，列，方向，字元數）我們可以測試是否所指的單詞在單詞表中。這也導致使用大量巢狀的 for 迴圈。

上述兩種方法相對來說都不難編碼，但如果增加行和列的數量，則上面提出的兩種解法均需要相當長的時間。

以上兩個案例中，我們可以看到要寫一個工作程式並不夠。如果這個程式在巨大的資料集上執行，那麼執行時間就變成了重要問題。

那麼，使用自動機理論可以快速的解決這個問題，下一篇中給大家詳細的分析。

3 資料結構與演算法基礎

3.1 資料結構基礎

3.1.1 什麼是資料結構

在計算機領域中，資料是資訊的載體，是能夠輸入到計算機中並且能被計算機識別、儲存和處理的符號的總稱。資料結構是指資料元素和資料元素之間的相互關係或資料的組織形式。資料元素是資料的的基本單位，資料元素有若干基本項組成。

3.1.2 資料之間的關係

資料之前的關係分為兩類：
1) 邏輯關係
表示資料之間的抽象關係，按每個元素可能具有的前趨數和直接後繼數將邏輯結構分為線性結構和非線性結構。邏輯關係或邏輯結構有如下特點：

只是描述資料結構中資料元素之間的聯絡規律；
是從具體問題中抽象出來的數學模型，是獨立於計算機儲存器的（與硬體無關）

邏輯結構的分類如下：

線性結構
樹形結構
圖狀結構
其他結構

2) 物理關係
邏輯關係在計算中的具體實現方法，分為順序儲存方法、鏈式儲存方法、索引儲存方法、雜湊儲存方法。物理關係或物理結構有如下特點：

是資料的邏輯結構在計算機儲存其中的映像；
儲存結構是通過計算機程式來實現，因而是依賴於具體的計算機語言的；

物理結構分類如下：

順序結構
鏈式結構
索引結構

3.2 演算法基礎

3.2.1 基礎概念

演算法是為求解一個問題需要遵循的、被清楚指定的簡單指令的集合。對於一個問題，一旦某種演算法給定並且被確定是正確的，那麼重要的一步就是確定該演算法將需要多少諸如時間或空間等資源量的問題。如果一個問題的求解演算法竟然需要長達一年時間，那麼這種演算法就很難能有什麼用處。同樣，一個需要若干個 GB 的記憶體的演算法在當前的大多數機器上也是無法使用的。

3.2.2 數學基礎

一般來說，估算演算法資源消耗所需的分析是一個理論問題，因此需要一套數學分析法，我們先從數學定義開始。

定理 1：如果存在正常數 c 和 n0，使得當 N>= n0 時，T (N) <= cf (N)，則記為 T (N) = O (f (N))。
定理 2：如果存在正常數 c 和 n0，使得當 N>=n0 時，T (N) <= cg (N)，則記為 T (N) = Ω(g (N))。
定理 3：T (N) = θ(h (N)) 當且僅當 T (N) = O (h (N)) 和 T (N) = Ω(h (N))。
定理 4：如果對每一個正常數 c 都存在常數 n0 使得當 N>n0 時，T (N) < cp (N)，則 T (N) = o (p (N))。

這些定義的目的是要在函式間建立一種相對的級別。給定兩個函式，通常存在一些點，在這些點上一個函式的值小於另一個函式的值，因此，一般宣稱 f (N)<g (N)，是沒有什麼意義的。於是，我們比較他們的相對增長率。當將相對增長率應用到演算法分析時，會明白它是重要的度量。

如果用傳統的不等式來計算增長率，那麼第一個定義 T (N) = O (f (N)) 是說 T (N) 的增長率小於或者等於 f (N) 的增長率。第二個定義 T (N) = Ω(g (N)) 是說 T (N) 增長率大於或者等於 g (N) 的增長率。第三個定義 T (N) = θ(h (N)) 是說 T (N) 的增長率等於 h (N) 的增長率。最後一個定義 T (N) = o (p (N)) 說的則是 T (N) 的增長率小於 p (N) 的增長率。他不同於大 O，因為大 O 包含增長率相同的可能性。

要證明某個函式 T (N) = O (f (N)) ，通常不是形式的使用這些定義，而是使用一些已知的結果（比如說 T (N) = O (log (N))）。一般來說，這就意味著證明是非常簡單的計算而不應涉及微積分，除非遇到特殊情況。如下是常見的已知函式結果

c（常數函式）
logN（對數函式）
logN^2（對數平方函式）
N（線性函式）
NlogN
N^2（二次函式）
N^3（三次函式）
2^N（指數函式）

在使用已知函式結果時，有幾點需要注意：

首先，將常數或低階項放進大 O 是非常壞的習慣。不要寫成 T (N) = O (2*N^2) 或 T (N) = O (N^2 + N)。這兩種情形下，正確的形式是 T (N) = O (N^2)。也就是說低階項一般可以被忽略，而常數也可以棄掉。
其次，我們總能夠通過計算極限 limN→∞f (N)/g (N)（極限公式）來確定兩個函式 f (N) 和 g (N) 的相對增長率。該極限可以有四種可能的值：
極限是 0：這意味著 f (N) = o (g (N))。
極限是 c != 0：這意味著 f (N) = θ(g (N))。
極限是∞ ：這意味著 g (N) = o (f (N))。
極限擺動：二者無關。

3.2.3 複雜度函式

正常情況下的複雜度函式包含如下兩種：
時間複雜度
空間複雜度

時間和空間的度量並沒有一個固定的標準，但是在正常情況下，時間複雜度的單位基本上是以一次記憶體訪問或者一次 IO 來決定。空間複雜度是指在演算法執行過程中需要佔用的儲存空間。對於一個演算法來說，時間複雜度和空間複雜度往往是相互影響，當追求一個好的時間複雜度時，可能會使空間複雜度變差，即可能佔用更多的儲存空間；反之，當追求一個較好的空間複雜度時，可能會使時間複雜度變差，即可能佔用較長的運算時間。

3.3 知識儲備

3.3.1 質數分辨定理（HashTree 的理論基礎）

簡單的說就是，n 個不同的質數可以分辨的連續數的個數和他們的乘機相同。分辨是指這些連續的整數不可能有相同的餘數序列。

3.3.2 Hash 演算法

1)Hash
Hash 一般翻譯成雜湊，也可以直接音譯成雜湊，就是把任意長度的輸入，通過雜湊演算法變換成固定長度的輸出，該輸入就是雜湊值。不同的輸入可能雜湊成相同的值，確定的雜湊值不可能確定一個輸入。

2) 常見的 Hash 演算法

MD4：訊息摘要演算法；
MD5：訊息摘要演算法，MD4 的升級版本；
SHA-1：SHA-1 的設計和 MD4 相同原理，並模仿該演算法
自定義 HASH 演算法：程式設計者可以自定義 HASH 演算法，比如 java 中重寫的 hashCode () 方法

3) Hash 碰撞
解決 Hash 碰撞常見的方法有一下幾種：

分離連結法（連結串列法）：做法是將雜湊到同一個值的所有元素保留在一個表中，例如 JDK 中的 HashMap；
探測散列表：當發生 Hash 碰撞時，嘗試尋找另外一個單元格，直到知道到空的單元為止。包括：線性探測法，平方探測法，雙雜湊。

3.3.3 樹結構的基本概念

樹的遞迴定義：一棵樹是一些節點的集合。這個集合可以是空集；若不是空集，則樹由根節點 root 以及 0 個或多個非空的子樹組成，這些子樹中每一棵的根都被來自根 root 的一條有向的邊所連線；
樹葉節點：沒有兒子節點稱為樹葉；
深度：對於任意節點 ni，ni 的深度為從根到 ni 的唯一路徑的長；
高度：對於任意節點 ni，ni 的高度為從 ni 到一片樹葉的最長路徑的長。
樹的遍歷：樹的遍歷分為兩種，先序遍歷和後續遍歷；

3.3.4 二叉搜尋樹

二叉搜尋樹是一棵二叉樹，其中每個節點都不能有多於兩個子節點。
對於二叉查詢樹的每一個節點 X，它的左子樹中所有項的值都小於 X 節點中的項，而它的右子樹中所有項的值大於 X 中的項；

4 常見資料結構與演算法分析

4.1 線性資料結構

4.1.1 HashMap

1) 總述
HashMap 是開發中最常用的資料結構之一，資料常駐於記憶體中，對於小的資料量來說，HashMap 的增刪改查的效率都非常高，複雜度接近於 O (1)。

2) 資料結構和演算法

HashMap 由一個 hash 函式和一個數組組成；
資料插入，當進入到 map 的時候，根據 hash (key) 找到對應點位置，如果位置為空，直接儲存，如果位置不為空，則使用連結串列的方式處理；為了解決遍歷連結串列所增加的時間，JDK 中的連結串列在大小增大到 8 時，將會演變成紅黑樹以降低時間複雜度。為什麼開始使用連結串列，後面使用紅黑樹：
- 資料量較小的時候，連結串列的查詢效率相對來說也比較高，使用紅黑樹佔用空間比連結串列要大；
- 為什麼選擇 8，請參考泊松分佈；
查詢和刪除的過程，同插入的過程類似；
HashMap 可以支援自動擴容，擴容機制需要看具體的實現；

3) 優缺點

優點：動態可變長儲存資料，快速的查詢速度，查詢複雜度接近 O (1);
缺點：只支援小資料量的記憶體查詢；

4) 使用場景

在記憶體中小資料量的資料儲存和快速查詢；

4.1.2 Bloom Filter（布隆過濾器）

1) 總述
布隆過濾器演算法為大資料量的查詢提供了快速的方法，時間複雜度為 O (k)，布隆過濾器的語義為：

布隆過濾器的輸出為否定的結果一定為真；
布隆過濾器的輸出為肯定的結果不一定為真；

2) 資料結構和演算法
布隆過濾器的具體結構和演算法為：

布隆過濾器包含 k 個 hash 函式，每個函式可以把 key 雜湊成一個整數（下標）；
布隆過濾器包含了一個長度為 n 的 bit 陣列（向量陣列），每個 bit 的初始值為 0；
當某個 key 加入的時候，用 k 個 hash 函式計算出 k 個雜湊值，並把陣列中對應的位元置為 1；
判斷某個 key 是否在集合時，用 k 個 hash 函式算出 k 個值，並查詢陣列中對應的位元位，如果所有的 bit 位都為 1，認為在集合中；
布隆過濾器的大小需要提前評估，並且不能擴容；

布隆過濾器的插入過程如下：

判斷某個 key 是否在集合時，用 k 個 hash 函式算出 k 個值，並查詢陣列中對應的位元位，如果所有的 bit 位都為 1，認為在集合中

布隆過濾器無法刪除資料；
布隆過濾器查詢的時間複雜度為 O (k)；
布隆過濾器空間的佔用在初始化的時候已經固定不能擴容。

3) 優缺點

優點：布隆過濾器在時間和空間上都有巨大的優勢。布隆過濾器儲存空間和插入 / 查詢時間都是常數。布隆過濾器不需要儲存資料本身，節省空間。
缺點：布隆過濾器的缺點是有誤差。元素越多誤差越高。可以通過提高 hash 函式的個數和擴大 bit 陣列的長度來降低誤差率；

4) 場景

使用場景：快取擊穿，判斷有無。

4.1.3 SkipList（跳錶）

1) 總述
跳錶是一種特殊的連結串列，相比一般的連結串列有更高的查詢效率，可比擬二差查詢樹，平均期望的插入，查詢，刪除的時間複雜度都是 O (logN);

2) 資料結構和演算法
跳錶可視為水平排列（Level）、垂直排列（Row）的位置（Position）的二維集合。每個 Level 是一個列表 Si，每個 Row 包含儲存連續列表中相同 Entry 的位置，跳錶的各個位置可以通過以下方式進行遍歷。

After (P)：返回和 P 在同一 Level 的後面的一個位置，若不存在則返回 NULL；
Before (P)：返回和 P 在同一 Level 的前面的一個位置，若不存在則返回 NULL；
Below (P)：返回和 P 在同一 Row 的下面的一個位置，若不存在則返回 NULL；
Above (P)：返回和 P 在同一 Row 的上面的一個位置，若不存在則返回 NULL；

有順序關係的多個 Entry (K,V) 集合 M 可以由跳錶實現，跳錶 S 由一系列列表 {S0，S1，S2，……，Sh} 組成，其中 h 代表的跳錶的高度。每個列表 Si 按照 Key 順序儲存 M 項的子集，此外 S 中的列表滿足如下要求：

列表 S0 中包含了集合 M 的每個一個 Entry；
對於 i = 1 ，…… ，h-1 列表 Si 包含列表 Si-1 中 Entry 的隨機子集；

Si 中的 Entry 是從 Si-1 中的 Entry 集合中隨機選擇的，對於 Si-1 中的每一個 Entry，以 1/2 的概率來決定是否需要拷貝到 Si 中，我們期望 S1 有大約 n/2 個 Entry，S2 中有大約 n/4 個 Entry，Si 中有 n/2^i。跳錶的高度 h 大約是 logn。從一個列表到下一個列表的 Entry 數減半並不是跳錶的強制要求；
插入的過程描述，以上圖為例，插入 Entry58：

找到底層列表 S0 中 55 的位置，在其後插入 Entry58；
假設隨機函式取值為 1，緊著回到 20 的位置，在其後插入 58，並和底層列表 S0 的 - Entry58 連結起來形成 Entry58 的 Row；
假設隨機函式取值為 0，則插入過程終止；

下圖為隨機數為 1 的結果圖：

刪除過程：同查詢過程。

時間複雜度

查詢包括兩個迴圈，外層迴圈是從上層 Level 到底層 Level，內層迴圈是在同一個 Level，從左到右；
跳錶的高度大概率為 O (logn)，所以外層迴圈的次數大概率為 O (logn);
在上層查詢比對過的 key，不會再下層再次查詢比對，任意一個 key 被查詢比對的概率為 1/2，因此記憶體迴圈比對的期望次數是 2 也就是 O (1);
因此最終的時間複雜度函式 O (n) = O (1)*O (logn) 也就是 O (logn)；

空間複雜度

Level i 期望的元素個數為 n/2^i；
跳錶中所有的 Entry（包含同一個 Entry 的 Row 中的元素） Σ n/2^i = nΣ1/2^i，其中有級數公式得到 Σ1/2^i < 2；
期望的列表空間為 O (n)；

3) 優缺點

優點：快速查詢，演算法實現簡單；
缺點：跳錶在連結串列的基礎上增加了多級索引以提升查詢效率，使用空間來換取時間，必然會增加儲存的負擔。

4) 使用場景
許多開源的軟體都在使用跳錶：

Redis 中的有序集合 zset
LevelDB Hbase 中的 memtable
Lucene 中的 Posting List

4.2 簡單非線性資料結構

4.2.1 AVL

1) 總述
AVL 樹是帶有平衡條件的二叉查詢樹，這個平衡條件必須要容易保持，而且它保證樹的深度必須是 O (logN)。在 AVL 樹中任何節點的兩個子樹的高度最大差別為 1。

2) 資料結構和演算法
AVL 樹本質上還是一棵二叉查詢樹，有以下特點：

AVL 首先是一棵二叉搜尋樹；
帶有平衡條件：每個節點的左右子樹的高度之差的絕對值最多為 1；
當插入節點或者刪除節點時，樹的結構發生變化導致破壞特點二時，就要進行旋轉保證樹的平衡；

針對旋轉做詳細分析如下：
我們把必須重新平衡的節點叫做 a，由於任意節點最多有兩個兒子，因此出現高度不平衡就需要 a 點的兩棵子樹的高度差 2。可以看出，這種不平衡可能出現一下四種情況：

對 a 的左兒子的左子樹進行一次插入；
對 a 的左兒子的右子樹進行一次插入；
對 a 的右兒子的左子樹進行一次插入；
對 a 的右兒子的柚子樹進行一次插入；

情形 1 和 4 是關於 a 的對稱，而 2 和 3 是關於 a 點的對稱。因此理論上解決兩種情況。
第一種情況是插入發生在外側的情況，該情況通過對樹的一次單旋轉而完成調整。第二種情況是插入發生在內側的情況，這種情況通過稍微複雜些的雙旋轉來處理。

單旋轉的簡單示意圖如下：

雙旋轉的簡單示意圖如下：

3) 優缺點

優點：使用二叉查詢演算法時間複雜度為 O (logN)，結構清晰簡單；
缺點：插入和刪除都需要進行再平衡，浪費 CPU 資源；

4) 使用場景

少量資料的查詢和儲存；

.4.2.2 Red Black Tree

1) 總述
紅黑樹是一種自平衡的二叉查詢樹，是 2-3-4 樹的一種等同，它可以在 O (logN) 內做查詢，插入和刪除。

2) 資料結構和演算法
在 AVL 的基礎之上，紅黑樹又增加了如下特點：

每個節點或者是紅色，或者是黑色；
根節點是黑色；
如果一個節點時紅色的，那麼它的子節點必須是黑色的；
從一個節點到一個 null 引用的每一條路徑必須包含相同數目的黑色節點；

紅黑樹的示意圖如下（圖片來源於網路）：

那麼將一個節點插入到紅黑樹中，需要執行哪些步驟呢？

將紅黑樹當做一棵二叉搜尋樹，將節點插入；
將插入的節點著色為紅色；
通過一系列的旋轉和著色等操作，使之重新成為一棵紅黑樹；

在第二步中，被插入的節點被著為紅色之後，他會違背哪些特性呢

對於特性 1，顯然是不會違背；
對於特性 2，顯然也是不會違背；
對於特性 4，顯然也是不會違背；
對於特性 3，有可能會違背，我們將情況描述如下
- 被插入的節點是根節點：直接把此節點塗為黑色；
- 被插入的節點的父節點是黑色：什麼也不需要做。節點被插入後，仍然是紅黑樹；
- 被插入的節點的父節點是紅色：此種情況下與特性 3 違背，所以將情況分析如下：
- - 當前節點的父節點是紅色，且當前節點的祖父節點的另一個子節點也是紅色。處理策略為：將父節點置為黑色、將叔叔節點置為黑色、將祖父節點置為紅色；
- - 當前節點的父節點是紅色，叔叔節點時黑色，且當前節點是其父節點的右子節點。將父節點作為新的當前節點、以新的當前節點作為支點進行左旋；
- - 當前節點的父節點是紅色，叔叔節點時黑色，且當前節點時父節點的左子節點。將父節點置為黑色、將祖父節點置為紅色、以祖父節點為支點進行右旋；

定理：一棵含有 n 個節點的紅黑樹的高度至多為 2log (N+1)，證明過程請檢視參考資料。
由此定理可推論紅黑樹的時間複雜度為 log (N)；

3) 優缺點

優點：查詢效率高，插入和刪除的失衡的代銷比 AVL 要小很多；
缺點：紅黑樹不追求完全平衡；

4) 使用場景

紅黑樹的應用很廣泛，主要用來儲存有序的資料，時間複雜度為 log (N)，效率非常高。例如 java 中的 TreeSet、TreeMap、HashMap 等

4.2.3 B+Tree

1) 總述
提起 B+Tree 都會想到大名鼎鼎的 MySql 的 InnoDB 引擎，該引擎使用的資料結構就是 B+Tree。B+Tree 是 B-Tree（平衡多路查詢樹）的一種改良，使得更適合實現儲存索引結構，也是該篇分享中唯一一個與磁碟有關係的資料結構。首先我們先了解一下磁碟的相關東西。

系統從磁碟讀取資料到記憶體時是以磁碟塊（block）為基本單位，位於同一塊磁碟塊中的資料會被一次性讀取出來。InnoDB 儲存引擎中有頁（Page）的概念，頁是引擎管理磁碟的基本單位。

2) 資料結構和演算法
首先，先了解一下一棵 m 階 B-Tree 的特性：

每個節點最多有 m 個子節點；
除了根節點和葉子結點外，其他每個節點至少有 m/2 個子節點；
若根節點不是葉子節點，則至少有兩個子節點；
所有的葉子結點都是同一深度；
每個非葉子節點都包含 n 個關鍵字
關鍵字的個數的關係為 m/2-1 < n < m -1

B-Tree 很適合作為搜尋來使用，但是 B-Tree 有一個缺點就是針對範圍查詢支援的不太友好，所以才有了 B+Tree；
那麼 B+Tree 的特性在 B-Tree 的基礎上又增加了如下幾點：

非葉子節點只儲存鍵值資訊；
所有的葉子節點之間都有一個鏈指標（方便範圍查詢）；
資料記錄都存放在葉子節點中；

我們將上述特點描述整理成下圖（假設一個頁（Page）只能寫四個資料）：

這樣的資料結構可以進行兩種運算，一種是針對主鍵的範圍查詢和分頁查詢，另外一種是從根節點開始，進行隨機查詢；

3) 優缺點

優點：利用磁碟可以儲存大量的資料，簡單的表結構在深度為 3 的 B+Tree 上可以儲存大概上億條資料；B+Tree 的深度大概也就是 2~4，深度少就意味這 IO 會減少；B+Tree 的時間複雜度 log (m) N
缺點：插入或者刪除資料有可能會導致資料頁分裂；即使主鍵是遞增的也無法避免隨機寫，這點 LSM-Tree 很好的解決了；無法支援全文索引；

4) 使用場景

使用場景大多數資料庫的引擎，例如 MySql,MongoDB 等

4.2.4 HashTree

1) 總述
HashTree 是一種特殊的樹狀結構，根據質數分辨定理，樹每層的個數為 1、2、3、5、7、11、13、17、19、23、29…..

2) 資料結構和演算法
從 2 起的連續質數，連續 10 個質數接可以分辨大約 6464693230 個數，而按照目前 CPU 的計算水平，100 次取餘的整數除法操作幾乎不算什麼難事。

我們選擇質數分辨演算法來構建一顆雜湊樹。選擇從 2 開始的連續質數來構建一個 10 層的雜湊樹。第一層節點為根節點，根節點先有 2 個節點，第二層的每個節點包含 3 個子節點；以此類推，即每層節點的資料都是連續的質數。對質數進行取餘操作得到的資料決定了處理的路徑。下面我們以隨機插入 10 個數（442 9041 3460 3164 2997 3663 8250 908 8906 4005）為例，來圖解 HashTree 的插入過程，如下：

HashTree 的節點查詢過程和節點插入過程類似，就是對關鍵字用質數取餘，根據餘數確定下一節點的分叉路徑，知道找到目標節點。如上圖，在從物件中查詢所匹配的物件，比較次數不超過 10 次，也就是說時間複雜度最多是 o (1).

刪除的過程和查詢類似。

3) 優缺點：

優點：結構簡單，查詢迅速，結構不變。
缺點：非有序性。

4.2.5 其他資料結構