資料結構/所有章節
   |
本作品採用知識共享 署名-相同方式共享 3.0 通用 許可協議授權。簡而言之：您可以在適當署名並僅在相同、相似或相容 許可協議下分發的條件下，共享和創作本作品的衍生作品。如果您獲得版權所有者的許可，上述任何條件都可以被免除。 |
感謝使用來自維基百科 的部分內容。
計算機可以儲存和處理大量資料。正式的資料結構使程式設計師能夠在思維上將大量資料結構化為概念上易於管理的關係。
有時我們使用資料結構來讓我們做更多的事情：例如，實現資料的快速搜尋或排序。其他時候，我們使用資料結構來讓我們做更少的事情：例如，棧的概念是更通用的資料結構的有限形式。這些限制為我們提供了保證，使我們能夠更輕鬆地推理我們的程式。資料結構還提供有關演算法複雜性的保證 - 為工作選擇合適的資料結構對於編寫良好的軟體至關重要。
由於資料結構是更高層次的抽象，它們為我們提供了對資料組的操作，例如向列表新增專案或查詢佇列中優先順序最高的專案。當資料結構提供操作時，我們可以將資料結構稱為抽象資料型別（有時縮寫為 ADT）。抽象資料型別可以最大限度地減少程式碼中的依賴關係，這在程式碼需要更改時很重要。由於您從較低級別細節中抽象出來，因此一個數據結構與另一個數據結構共享的某些更高級別共性可以用來將一個數據結構替換為另一個數據結構。
我們的程式語言配備了一組內建型別，例如整數和浮點數，這些型別使我們能夠使用機器處理器具有本機支援的資料物件。這些內建型別是對處理器實際提供的型別的抽象，因為內建型別隱藏了有關其執行和限制的詳細資訊。
例如，當我們使用浮點數時，我們主要關心它的值以及可以應用於它的操作。考慮計算斜邊的長度
let c := sqrt(a * a + b * b)
從上面生成的機器程式碼將使用計算這些值的通用模式並累積結果。實際上，這些模式是如此重複，以至於建立了高階語言來避免這種冗餘，並允許程式設計師思考什麼值被計算，而不是如何計算。
這裡有兩個有用的相關概念
- 封裝是指將通用模式分組在一起，放在一個名稱下，然後進行引數化，以實現對該模式的更高層次理解。例如，乘法運算需要兩個源值並將這兩個值的乘積寫入給定的目標。該操作透過源和單個目標引數化。
- 抽象是一種機制，可以將抽象的實現細節隱藏在抽象的使用者面前。例如，當我們乘以數字時，我們不需要知道處理器實際使用的技術，我們只需要知道它的屬性。
程式語言既是機器的抽象，又是封裝機器內部細節的工具。例如，當程式語言足夠封裝使用者以使其遠離任何一臺機器時，用程式語言編寫的程式可以編譯到幾個不同的機器架構中。
在這本書中，我們將程式語言提供的抽象和封裝更進一步：當應用程式變得更加複雜時，程式語言的抽象變得過於低階，無法有效管理。因此，我們在這些較低級別構造之上構建自己的抽象。我們甚至可以在這些抽象之上構建進一步的抽象。每次我們向上構建時，我們都會失去對較低級別實現細節的訪問許可權。雖然失去這種訪問許可權聽起來可能是一筆糟糕的交易，但實際上它是一個相當不錯的交易：我們主要關心的是解決手頭的問題，而不是任何微不足道的決策，這些決策本來就可以任意地用其他決策來代替。當我們能夠在更高層次上思考時，我們就能擺脫這些負擔。
我們在這本書中涵蓋的每個資料結構都可以被認為是一個單獨的單元，它有一組值和一組可以用來訪問或更改這些值的操作。資料結構本身可以理解為資料結構的操作集以及每個操作的屬性（即，操作的作用以及我們可以預期它需要多長時間）。
大O表示法是表示計算機程式碼效能的一種常用方法。該表示法建立了記憶體中專案數量與函式的平均效能之間的關係。對於一組專案， 表示特定函式將平均對集合執行操作。 表示函式始終執行恆定數量的操作，與專案數量無關。該表示法僅表示演算法複雜度，因此函式可能會執行更多操作，但 的常數倍數將被省略。
我們首先要檢視的資料結構是節點結構。節點只是一個值的容器，以及指向“下一個”節點的指標（可以是null）。
以上是結構的抽象
在某些語言中，結構被稱為記錄或類。其他一些語言不直接支援結構，而是允許它們從其他結構（例如元組或列表）構建。
這裡，我們只關心節點是否包含某種形式的值，因此我們簡單地說它的型別是“元素”，因為型別並不重要。在某些程式語言中，永遠不需要指定任何型別（如動態型別語言，如 Scheme、Smalltalk 或 Python）。在其他語言中，型別可能需要限制為整數或字串（如靜態型別語言，如 C）。在其他語言中，包含元素的型別的決策可以推遲到型別實際使用時（如支援泛型型別的語言，如 C++ 和 Java）。在任何這些情況下，將虛擬碼翻譯成您自己的語言都應該比較簡單。
可以很容易地實現每個指定的節點操作
// Create a new node, with v as its contained value and next as
// the value of the next pointer
function make-node(v, node next): node
let result := new node {v, next}
return result
end
// Returns the value contained in node n
function get-value(node n): element
return n.value
end
// Returns the value of node n's next pointer
function get-next(node n): node
return n.next
end
// Sets the contained value of n to be v
function set-value(node n, v)
n.value := v
end
// Sets the value of node n's next pointer to be new-next
function set-next(node n, new-next)
n.next := new-next
return new-next
end
我們主要關心的是操作和實現策略，而不是結構本身和底層實現。例如，我們更關心的是規定的時間要求，該要求指出所有操作的時間都為。以上實現滿足此標準，因為每個操作所需的時間是恆定的。另一種理解恆定時間操作的方式是將它們視為其分析不依賴於任何變數的操作。（符號 在下一章中有數學定義。目前，可以安全地假設它只表示恆定時間。）
因為節點只是一個容器，既包含值，也包含指向另一個節點的指標的容器，所以節點資料結構本身（及其實現）是多麼微不足道就不足為奇了。
從節點構建鏈
[edit | edit source]雖然節點結構很簡單，但它實際上允許我們計算一些我們無法僅僅使用固定大小的整數來計算的東西。
但首先，我們將看看一個不需要使用節點的程式。以下程式將從輸入流（可以來自使用者或檔案）中讀取一系列數字，直到遇到檔案末尾，然後輸出最大數字和所有數字的平均值
program(input-stream in, output-stream out)
let total := 0
let count := 0
let largest :=
while has-next-integer(in):
let i := read-integer(in)
total := total + i
count := count + 1
largest := max(largest, i)
repeat
println out "Maximum: " largest
if count != 0:
println out "Average: " (total / count)
fi
end
但現在考慮解決一個類似的任務：讀取一系列數字，直到遇到檔案末尾，然後輸出最大數字和所有能被最大數字整除的數字的平均值。這個問題有所不同，因為最大數字可能是最後輸入的數字：如果我們要計算所有能被該數字整除的數字的平均值，我們需要以某種方式記住所有這些數字。我們可以使用變數來記住之前的數字，但變數只會幫助我們在輸入的數字不太多的時候解決問題。
例如，假設我們要給自己 200 個變數來儲存使用者輸入的狀態。並且進一步假設每個變數都有 64 位。即使我們對我們的程式非常聰明，它也只可以計算 種不同型別的輸入的結果。雖然這是一個非常大的組合數，但一個包含 300 個 64 位數字的列表需要更多的組合才能被正確編碼。（一般來說，這個問題被稱為需要線性空間。所有隻需要有限數量變數的程式都可以用常數空間解決。）
我們可以利用節點抽象的屬性，而不是構建限制編碼的限制（比如只有恆定的數量的變數），從而允許我們記住計算機所能容納的任意數量的數字
program(input-stream in, output-stream out)
let largest :=
let nodes := null
while has-next-integer(in):
let i := read-integer(in)
nodes := make-node(i, nodes) // contain the value i,
// and remember the previous numbers too
largest := max(largest, i)
repeat
println out "Maximum: " largest
// now compute the averages of all factors of largest
let total := 0
let count := 0
while nodes != null:
let j := get-value(nodes)
if j divides largest:
total := total + j
count := count + 1
fi
nodes := get-next(nodes)
repeat
if count != 0:
println out "Average: " (total / count)
fi
end
上面，如果成功讀取了n個整數，將呼叫n次make-node。這將需要建立n個節點（這需要足夠的空間來儲存每個節點的值和下一個欄位，加上內部記憶體管理開銷），所以記憶體需求將是的量級。類似地，我們構建了這個節點鏈，然後再次遍歷該鏈，這將需要步來構建鏈，然後還需要步來遍歷它。
注意，當我們遍歷鏈中的數字時，我們實際上是在反向檢視它們。例如，假設輸入到我們程式中的數字是 4、7、6、30 和 15。在遇到檔案末尾後，節點鏈將看起來像這樣
這樣的鏈更常被稱為連結串列。但是，我們通常更喜歡從列表或序列的角度思考，因為它們不是那麼底層：連結的概念只是一個實現細節。雖然列表可以用鏈來建立，但在本書中，我們將介紹幾種其他建立列表的方法。目前，我們更關心節點的抽象能力，而不是它的一種使用方式。
上面的演算法只使用了 make-node、get-value 和 get-next 函式。如果我們使用 set-next，我們可以改變演算法來生成鏈，使其保持原始順序（而不是反轉它）。
program (input-stream in, output-stream out)
let largest :=
let nodes := null
let tail_node := null
while has-next-integer (in):
let i := read-integer (in)
if (nodes == null)
nodes := make-node(i, null) // construct first node in the list
tail_node := nodes //there is one node in the list=> first and last are the same
else
tail_node := set-next (tail_node, make-node (i, null)) // append new node to the end of the list
largest := max(largest, i)
repeat
println out "Maximum: " largest
// now compute the averages of all factors of largest
let total := 0
let count := 0
while nodes != null:
let j := get-value(nodes)
if j divides largest:
total := total + j
count := count + 1
fi
nodes := get-next(nodes)
repeat
if count != 0:
println out "Average: " (total / count)
fi
end
歸納原理
[edit | edit source]我們可以從節點構建的鏈是數學歸納原理的演示
數學歸納法
|
例如，設性質 是這樣的陳述："你可以製作一個可以容納 個數字的鏈條"。這是一個關於自然數的性質，因為這句話對 的特定值是有意義的。
- 你可以製作一個可以容納 5 個數字的鏈條。
- 你可以製作一個可以容納 100 個數字的鏈條。
- 你可以製作一個可以容納 1,000,000 個數字的鏈條。
與其證明我們可以製作長度為 5、100 和一百萬的鏈條，我們寧願證明一般性陳述 。上面第 2 步稱為 **歸納假設**；讓我們證明我們可以證明它。
- 假設 成立。也就是說，我們可以製作一個包含 個元素的鏈條。現在我們必須證明 成立。
- 假設
chain是 元素鏈條的第一個節點。假設i是我們想要新增到鏈條中的某個數字，以製作一個長度為 的鏈條。 - 以下程式碼可以為我們實現這一點。
let bigger-chain := make-node(i, chain)
- 這裡，我們有新的數字
i，它現在是bigger-chain的第一個連結所包含的值。如果chain包含 個元素，那麼bigger-chain必須包含 個元素。
上面第 3 步稱為 **基本情況**，讓我們證明我們可以證明它。
- 我們必須證明 成立。也就是說，我們可以製作一個包含一個元素的鏈條。
- 以下程式碼可以為我們實現這一點。
let chain := make-node(i, null)
歸納法原理指出，我們已經證明可以構建一個包含 個元素的鏈，對於所有 的值。這是怎麼回事呢？也許理解歸納法的最佳方式是將其視為建立描述無限個證明的公式的方法。在我們證明語句對於 （基本情況）為真之後，我們可以將歸納假設應用於該事實，以表明 成立。由於我們現在知道 成立，我們可以再次應用歸納假設來表明 必須成立。該原理指出，沒有什麼可以阻止我們反覆執行此操作，因此我們應該假設它適用於所有情況。
歸納法可能聽起來像一種奇怪的證明方法，但它是一種非常有用的技術。使這種技術如此有用的原因是，它可以將“證明 對所有 成立”這樣看起來很困難的語句分解成兩個更小、更容易證明的語句。通常情況下，基本情況很容易證明，因為它們根本不是一般性語句。大部分證明工作通常都在歸納假設中，這通常需要巧妙地重新表述語句以“附加”一個 情況的證明。
您可以將節點的包含值視為基本情況，將節點的下一個指標視為歸納假設。就像數學歸納法一樣，我們可以將儲存任意數量元素的難題分解成一個更簡單的難題，即僅儲存一個元素，然後有一個機制來附加其他元素。
歸納法求和
[edit | edit source]我們接下來考慮的歸納法的例子在本質上更具代數性
假設我們給出了公式 ，我們想證明該公式給出前 個數字的和。作為第一次嘗試，我們可能會嘗試僅表明這對於 1 為真
- ,
對於 2
- ,
對於 3
等等，但是我們很快就會意識到，我們的所謂證明將需要無限長的時間才能寫出來！即使您完成了這個證明，並且表明它對於前十億個數字都為真，但這並不一定意味著它對於十億零一個或甚至一百億也為真。這強烈暗示也許歸納法在這裡會很有用。
假設我們想使用歸納法證明給定的公式確實給出了前 n 個數字的和。第一步是證明基本情況；即我們必須表明當 n = 1 時它是正確的。這相對容易；我們只需用 1 代替變數 n，我們得到 ()，這表明當 n = 1 時該公式是正確的。
現在進行歸納步驟。我們必須證明如果公式對 j 成立，它對 j + 1 也成立。換句話說，假設我們已經證明了從 1 到 (j) 的總和為 ，我們想要證明從 1 到 (j+1) 的總和為 。注意這兩個公式只是透過將 n 分別替換為 (j) 和 (j+1) 而來的。
為了證明這個歸納步驟，首先要注意，要計算從 1 到 j+1 的總和，你只需要計算從 1 到 j 的總和，然後加上 j+1。我們已經有了從 1 到 j 的總和的公式，當我們將 j+1 加到那個公式時，我們得到這個新公式：。所以要真正完成證明，我們只需要證明 。
我們可以透過一些簡化步驟來證明上述方程成立。
漸進符號
[edit | edit source]介紹
[edit | edit source]沒有一種資料結構能在所有情況下都能提供最佳效能。為了選擇最適合特定任務的結構，我們需要能夠判斷特定解決方案的執行時間。或者，更準確地說，你需要能夠判斷兩種解決方案的執行時間，並選擇較好的一種。我們不需要知道它們會花費多少分鐘和秒，但我們需要一些方法來比較不同的演算法。
漸近複雜度是一種使用理想化（不可比較）的計算工作單位來表示演算法成本的主要部分的方法。例如，考慮對一副牌進行排序的演算法，該演算法透過反覆搜尋牌堆中最低的牌來進行排序。該演算法的漸近複雜度是牌堆中卡片數量的平方。這種二次行為是複雜度公式中的主要項，它表明，例如，如果你將牌堆的大小加倍，那麼工作量將大約增加四倍。
成本的精確公式更加複雜，它包含比我們理解演算法的本質複雜度所需的更多細節。對於我們的牌堆，在最壞的情況下，牌堆將從反向排序開始，因此我們的掃描必須一直進行到最後。第一次掃描將涉及掃描張牌，接下來將需要掃描張，等等。因此成本公式是。通常，用表示卡片數量，公式為，它等於。但是，項在表示式中占主導地位，這對於比較演算法成本至關重要。（事實上，這是一種昂貴的演算法；最佳排序演算法在亞二次時間內執行。）
從漸近的角度來說，當趨於無窮大時，越來越接近純粹的二次函式。在這樣的抽象級別上，的常數因子有什麼區別？因此，這種行為被稱為。
現在讓我們考慮如何比較兩種演算法的複雜度。設 是一個演算法在最壞情況下，以輸入大小 為函式的代價， 是另一個演算法的代價函式。例如，對於排序演算法， 和 將是演算法在一個包含 個專案的列表上可能執行的最大步數。如果對於所有 的值， 小於或等於 ，那麼複雜度函式為 的演算法嚴格更快。但是，一般來說，我們對計算成本的關注是針對大輸入的情況；因此，比較 和 對於 的較小值並不像 和 對於大於某個閾值的 的“長期”比較那麼重要。
注意，我們一直在討論演算法效能的邊界，而不是給出確切的速度。對我們的一副牌進行排序（使用我們的樸素二次演算法）所需的實際步數將取決於牌的初始順序。執行每一步的實際時間將取決於我們的處理器速度、處理器快取的狀態等等。在具體細節上，一切都非常複雜，而且與演算法的本質無關。
O 符號
[edit | edit source]定義
[edit | edit source]O（讀作“大 O”）是用來表達演算法執行時間上限的正式方法。它是衡量演算法完成可能需要的最長時間的一種度量。我們可以假設它代表程式的“最壞情況”。
更正式地說，對於非負函式， 和 ，如果存在一個整數 和一個常數 ，使得對於所有整數 ，，那麼 是 的大 O。這表示為 。如果繪製圖表， 作為您正在分析的曲線 的上限。
請注意，如果 只能取有限值（通常情況下應該如此），那麼這個定義意味著存在某個常數 （可能大於 ），使得對於所有 的值， 。 的適當值是 和 的最大值。
那麼，讓我們舉一個大 O 的例子。假設 ，以及 。我們能找到一個常數 ，使得 嗎？數字 在這裡有效，使我們得到 。對於任何大於 的數字 ，這仍然有效。由於我們試圖將此泛化到 的較大值，而較小值 並不那麼重要，我們可以說 通常比 快；也就是說， 受 約束，並且始終小於它。
然後可以說 在 時間內執行：“f-of-n 在 n 平方的時間內執行”。
為了找到上限 - Big-O 時間 - 假設我們知道 等於（精確） ，我們可以採取一些捷徑。例如，我們可以從執行時間中刪除所有常數；最終，在 的某個值時，它們就變得無關緊要了。這使得 。同樣為了方便比較，我們刪除常數乘數；在本例中為 。這使得 。也可以說 在 時間內執行；這使我們能夠對估計值設定更嚴格（更接近）的上限。
實際示例
[edit | edit source]：將包含 個專案的列表列印到螢幕上，每個專案只看一次。
：獲取一個包含 個專案的列表，反覆將它分成兩半，直到只剩下一個專案為止。
：獲取一個包含 個專案的列表，並將每個專案與其他所有專案進行比較。
Big-Omega 符號
[edit | edit source]對於非負函式， 和 ，如果存在整數 和常數 使得對於所有整數 ，，則 是 。這記作 。
這與大O符號的定義幾乎相同，只是 ，這使得 是一個下界函式，而不是上界函式。它描述了給定資料大小下 **可能發生的最佳情況**。
Theta 符號
[edit | edit source]對於非負函式， 和 ， 是 的theta當且僅當 且 。這記作 。
這基本上是在說函式 在上面和下面都被同一個函式 限制。
Theta 符號用 Q 表示。
對於非負函式 和 ， 是 的小 o 當且僅當 ，但 。這表示為 。
這表示 Big O 的鬆散邊界版本。 從上面進行限制，但它沒有對下面進行限制。
對於非負函式， 和 ， 是 的小 omega 當且僅當 ，但是 。這表示為 .
就像小 o 一樣，這是大 Omega 的等價形式。 是函式 的一個鬆散的下界；它從底部約束，但不是從頂部約束。
漸進符號如何與分析複雜度相關
[edit | edit source]時間比較不是演算法中唯一的因素。還有空間問題。通常，在演算法中會注意到時間和空間之間的權衡。漸進符號使您能夠進行這種權衡。如果您將演算法使用的時間和空間量視為資料隨時間或空間的變化的函式（時間和空間通常分別進行分析），您可以分析在向程式中引入更多資料時如何處理時間和空間。
這在資料結構中很重要，因為您希望資料結構在處理的資料量增加時能夠高效地執行。但請記住，對於大量資料高效的演算法並不總是對於少量資料簡單且高效的。因此，如果您知道您只處理少量資料，並且您擔心速度和程式碼空間，那麼可以對一個對於大量資料行為不佳的函式進行權衡。
漸進符號的一些例子
[edit | edit source]通常，我們使用漸進符號作為一種方便的方法來檢查函式在最壞情況下或最佳情況下可能發生的情況。例如，如果您想編寫一個函式，該函式搜尋一個數字陣列並返回最小的數字
function find-min(array a[1..n])
let j :=
for i := 1 to n:
j := min(j, a[i])
repeat
return j
end
無論陣列的大小如何，每次執行find-min 時，我們都必須初始化i 和j 整數變數，並在最後返回j。因此，我們可以簡單地將函式的這些部分視為常數並忽略它們。
那麼，我們如何使用漸進符號來討論find-min 函式呢？如果我們搜尋一個包含 87 個元素的陣列，那麼for 迴圈會迭代 87 次，即使我們遇到的第一個元素就是最小值。同樣，對於 個元素，for 迴圈會迭代 次。因此，我們說該函式在 時間內執行。
這個函式怎麼樣
function find-min-plus-max(array a[1..n]) // First, find the smallest element in the array let j := ; for i := 1 to n: j := min(j, a[i]) repeat let minim := j // Now, find the biggest element, add it to the smallest and j := ; for i := 1 to n: j := max(j, a[i]) repeat let maxim := j // return the sum of the two return minim + maxim; end
find-min-plus-max 的執行時間是多少？有兩個 for 迴圈，每個迴圈迭代 次，因此執行時間顯然是 。因為 是一個常數，我們可以將其丟棄並將執行時間寫為 。為什麼可以這樣做？如果你回憶大 O 符號的定義，你正在測試其邊界的函式可以乘以某個常數。如果 ，我們可以看到，如果 ，則大 O 條件成立。因此 。此規則對於各種漸近符號都是通用的。
陣列是一個集合，主要包含相似的資料型別，儲存在一個公共變數中。該集合形成一個數據結構，其中物件以線性方式儲存，在記憶體中一個接一個地儲存。有時陣列甚至被複制到記憶體硬體中。
該結構也可以定義為儲存帶索引資料的 元素 的特定方法。資料元素在邏輯上按順序儲存在陣列內的塊中。每個元素都由一個 索引 或下標引用。
索引通常是一個用於定址陣列中元素的數字。例如，如果你要儲存有關 8 月份每一天的資訊，你需要建立一個能夠定址 31 個值的陣列，每個值代表一個月中的每一天。索引規則取決於語言，但大多數語言使用 0 或 1 作為陣列的第一個元素。
陣列的概念對於初學者來說可能令人望而生畏，但實際上非常簡單。想象一本筆記本，其頁面從 1 到 12 編號。每個頁面可能包含或不包含資訊。筆記本就是一個 陣列，包含頁面。每個頁面都是陣列“筆記本”的 元素。在程式設計中，你可以透過引用頁碼或 下標 來檢索頁面上的資訊，例如，notebook(4) 將引用陣列筆記本中第 4 頁的內容。
筆記本（陣列）包含 12 頁（元素）
陣列也可以是多維的——與訪問一維列表的元素不同，元素可以透過兩個或多個索引訪問，例如矩陣或張量。
多維陣列與我們上面提到的筆記本示例一樣簡單。為了想象一個多維陣列，可以想象一個日曆。日曆的每一頁，從 1 到 12，都是一個元素，代表一個月，它包含大約 30 個元素，代表天數。每一天可能包含或不包含資訊。在程式設計中，calendar(4,15) 將引用第 4 個月、第 15 天。因此我們得到一個二維陣列。為了想象一個三維陣列，可以將每一天分解成 24 個小時。現在 calendar(4,15,9) 將引用第 4 個月、第 15 天、第 9 個小時。
一個簡單的 6 元素×4 元素陣列
Array<Element> 操作
make-array(整數 n): Array
- 建立一個從 到 （包括）的元素索引。陣列中的元素數量，也稱為陣列的大小，是 n。
get-value-at(Array a, 整數 index): Element
- 返回給定 index 處元素的值。index 的值必須在範圍內：0 <= index <= (n - 1)。此操作也稱為 下標操作。
set-value-at(Array a, 整數 index, Element new-value)
- 將陣列中給定 index 處的元素設定為等於 new-value。
陣列保證 常數 時間讀寫訪問，，但是元素例項的許多查詢操作（find_min、find_max、find_index）是 線性 時間，。在大多數語言中，陣列非常高效，因為操作透過基於陣列的基地址元素的簡單公式來計算元素的地址。
陣列實現因語言而異：一些語言允許自動調整陣列大小，甚至包含不同型別元素（如 Perl）。其他語言則非常嚴格，要求在執行時知道陣列的型別和長度資訊（如 C）。
陣列通常直接對映到計算機記憶體中的連續儲存位置，因此它們是大多數高階語言的“自然”儲存結構。
簡單的線性陣列是大多數其他資料結構的基礎。許多語言不允許你分配除陣列以外的任何結構，其他所有內容都必須在陣列之上實現。唯一的例外是連結串列，它通常實現為單獨分配的物件，但也可以在陣列內實現連結串列。
陣列索引需要是某種型別。通常，使用該語言的標準整數型別，但也有 Ada 和 Pascal 等語言允許任何離散型別作為陣列索引。指令碼語言通常允許任何型別作為索引（關聯陣列）。
邊界
[edit | edit source]陣列索引由具有下界和上界的取值範圍組成。
在一些程式語言中，只有上界可以被選擇，而下界固定為 0 (C, C++, C#, Java) 或 1 (FORTRAN 66, R).
在其他程式語言 (Ada, PL/I, Pascal) 中，上下界都可以自由選擇 (甚至為負數).
邊界檢查
[edit | edit source]陣列索引的第三個方面是檢查有效範圍以及訪問無效索引時會發生什麼。這一點非常重要，因為大多數 計算機蠕蟲 和 計算機病毒 透過使用無效的陣列邊界進行攻擊。
有三種選擇
- 大多數語言 (Ada, PL/I, Pascal, Java, C#) 將檢查邊界，並在訪問不存在的元素時引發錯誤條件。
- 少數語言 (C, C++) 不會檢查邊界，並在訪問有效範圍之外的元素時返回或設定一些任意值。
- 指令碼語言通常在向之前無效的索引寫入資料時自動擴充套件陣列。
宣告陣列型別
[edit | edit source]陣列型別的宣告取決於特定語言中陣列具有多少功能。
當語言具有固定下界和固定索引型別時，最簡單的宣告是。如果您需要一個數組來儲存每月收入，您可以在 C 中宣告
typedef double Income[12];
這為您提供了一個範圍從 0 到 11 的陣列。有關 C 中陣列的完整描述，請參閱 C Programming/Arrays。
如果您使用的是可以同時選擇下界和索引型別的語言，那麼聲明當然會更加複雜。以下是 Ada 中的兩個示例
type Month is range 1 .. 12;
type Income is array(Month) of Float;
或者更短的
type Income is array(1 .. 12) of Float;
有關 Ada 中陣列的完整描述，請參閱 Ada Programming/Types/array。
陣列訪問
[edit | edit source]我們通常用名稱、索引在一些括號中（方括號 '[]' 或圓括號 '()'）來寫陣列。例如，August[3]是 C 程式語言中用於引用月份中特定日期的方法。
因為 C 語言從零開始索引，August[3]是陣列中的第 4 個元素。august[0]實際上指的是此陣列的第一個元素。從零開始索引對於計算機來說是自然的，因為計算機對數字的內部表示從零開始，但對於人類來說，這種不自然的編號系統會導致在訪問陣列中的資料時出現問題。在使用基於零的索引的語言中獲取元素時，請記住陣列的真實長度，以免您獲取了錯誤的資料。這是在具有固定下界的語言中程式設計的缺點，程式設計師必須始終記住“"[0]" 表示“第一個”，並在需要時新增或減去 1。具有可變下界的語言將從程式設計師的肩上卸下這一負擔。
我們使用索引來儲存相關資料。如果我們的 C 語言陣列名為august，並且我們希望儲存我們將在第一天去超市的資訊，我們可以說，例如
august[0] = "Going to the shops today"
這樣，我們就可以遍歷從 0 到 30 的索引，並獲得每個日期在august.
列表結構和迭代器
[edit | edit source]我們現在已經看到了兩種不同的資料結構，它們允許我們儲存元素的有序序列。但是，它們具有兩種截然不同的介面。陣列允許我們使用 get-element() 和 set-element() 函式來訪問和更改元素。節點鏈要求我們使用 get-next() 直到找到所需的節點，然後我們可以使用 get-value() 和 set-value() 來訪問和修改其值。現在，如果您編寫了一些程式碼，然後意識到您應該使用另一個序列資料結構，會怎麼樣？您必須遍歷您已經編寫的所有程式碼，並將一組訪問器函式更改為另一組。真麻煩！幸運的是，有一種方法可以將此更改限制在一個地方：使用List 抽象資料型別 (ADT)。
List<item-type> ADT
get-begin():List Iterator<item-type>- 返回表示列表第一個元素的列表迭代器（我們很快就會定義它）。執行時間為 。
get-end():List Iterator<item-type>- 返回表示列表最後一個元素後面的一個元素的列表迭代器。執行時間為 。
prepend(new-item:item-type)- 在列表的開頭新增一個新元素。執行時間為 。
insert-after(iter:List Iterator<item-type>, new-item:item-type)- 在 iter 之後立即新增一個新元素。執行時間為 。
remove-first()- 刪除列表開頭的元素。執行時間為 。
remove-after(iter:List Iterator<item-type>)- 刪除iter後的元素。在 時間內執行。
is-empty():Boolean- 如果列表中沒有元素，則為 True。具有預設實現。在 時間內執行。
get-size():Integer- 返回列表中的元素數量。具有預設實現。在 時間內執行。
get-nth(n:Integer):item-type- 返回列表中第 n 個元素，從 0 開始計數。具有預設實現。在 時間內執行。
set-nth(n:Integer, new-value:item-type)- 將新值分配給列表中第 n 個元素，從 0 開始計數。具有預設實現。在 時間內執行。
迭代器是另一種抽象，它封裝了對單個元素的訪問以及在列表中進行增量移動的能力。它的介面與引言中介紹的節點介面非常相似，但由於它是一個抽象型別，不同的列表可以以不同的方式實現它。
List Iterator<item-type> ADT
get-value():item-type- 返回此迭代器所指的列表元素的值。
set-value(new-value:item-type)- 將新值分配給此迭代器所指的列表元素。
move-next()- 使此迭代器指向列表中的下一個元素。
equal(other-iter:List Iterator<item-type>):Boolean- 如果另一個迭代器指向與該迭代器相同的列表元素，則為 True。
所有操作都在 時間內執行。
List ADT 定義中還有其他幾個方面需要進一步解釋。首先，請注意 get-end() 操作返回一個指向列表“末尾之後”的迭代器。這使得它的實現稍微複雜一些，但允許您編寫類似於以下的迴圈：
var iter:List Iterator := list.get-begin() while(not iter.equal(list.get-end())) # Do stuff with the iterator iter.move-next() end while
其次，每個操作都給出了最壞情況下的執行時間。任何 List ADT 的實現都保證至少能夠以這種速度執行該操作。大多數實現將以更快的速度執行大多數操作。例如，List 的節點鏈實現可以在 時間內執行 insert-after()。
第三，一些操作說它們具有預設實現。這意味著這些操作可以用其他更基本的操作來實現。它們被包含在 ADT 中，以便某些實現能夠以更快的速度實現它們。例如，get-nth() 的預設實現是在 時間內執行，因為它必須遍歷第 n 個元素之前的所有元素。然而，List 的陣列實現可以使用它的 get-element() 操作在 時間內實現它。其他預設實現是：
abstract type List<item-type> method is-empty() return get-begin().equal(get-end()) end method method get-size():Integer var size:Integer := 0 var iter:List Iterator<item-type> := get-begin() while(not iter.equal(get-end())) size := size+1 iter.move-next() end while return size end method helper method find-nth(n:Integer):List Iterator<item-type> if n >= get-size() error "The index is past the end of the list" end if var iter:List Iterator<item-type> := get-begin() while(n > 0) iter.move-next() n := n-1 end while return iter end method method get-nth(n:Integer):item-type return find-nth(n).get-value() end method method set-nth(n:Integer, new-value:item-type) find-nth(n).set-value(new-value) end method end type
語法糖
[edit | edit source]在這本書中，我們會不時地引入一個縮寫，使我們能夠編寫更少的虛擬碼，並使您更容易閱讀。現在，我們將介紹一種更簡單的方法來比較迭代器，並提供一種專門用於遍歷序列的迴圈。
我們將過載 == 運算子，而不是使用 equal() 方法來比較迭代器。確切地說，以下兩個表示式是等效的：
iter1.equal(iter2) iter1 == iter2
其次，我們將使用 for 關鍵字來表達列表遍歷。以下兩個程式碼塊是等效的：
var iter:List Iterator<item-type> := list.get-begin() while(not iter == list.get-end()) operations on iter iter.move-next() end while
for iter in list operations on iter end for
實現
[edit | edit source]為了實際使用 List ADT，我們需要編寫一個具體資料型別來實現它的介面。有兩個標準資料型別自然地實現了 List：引言中描述的節點鏈，通常稱為單鏈表；以及陣列型別的擴充套件，稱為向量，它會自動調整大小以容納插入的節點。
單鏈表
[edit | edit source]type Singly Linked List<item-type> implements List<item-type>
head 指向列表中的第一個節點。當它為 null 時，列表為空。
data head:Node<item-type>
最初，列表為空。
constructor()
head := null
end constructor
method get-begin():Sll Iterator<item-type>
return new Sll-Iterator(head)
end method
“末尾之後”的迭代器只是一個空節點。要了解原因，請考慮當您擁有指向列表中最後一個元素的迭代器並呼叫 move-next() 時會發生什麼。
method get-end():Sll Iterator<item-type>
return new Sll-Iterator(null)
end method
method prepend(new-item:item-type)
head = make-node(new-item, head)
end method
method insert-after(iter:Sll Iterator<item-type>, new-item:item-type)
var new-node:Node<item-type> := make-node(new-item, iter.node().get-next())
iter.node.set-next(new-node)
end method
method remove-first()
head = head.get-next()
end method
這會將迭代器持有的節點指向兩個節點後的節點。
method remove-after(iter:Sll Iterator<item-type>)
iter.node.set-next(iter.node.get-next().get-next())
end method
end type
如果我們想讓get-size()成為一個操作，我們可以新增一個整數資料成員，它始終跟蹤列表的大小。否則，預設的實現也能正常工作。
單鏈表的迭代器僅僅包含一個指向節點的引用。
type Sll Iterator<item-type>
data node:Node<item-type>
constructor(_node:Node<item-type>)
node := _node
end constructor
大多數操作只是傳遞到節點。
method get-value():item-type
return node.get-value()
end method
method set-value(new-value:item-type)
node.set-value(new-value)
end method
method move-next()
node := node.get-next()
end method
對於相等性測試，我們假設底層系統知道如何比較節點以確定相等性。在幾乎所有語言中，這將是指標比較。
method equal(other-iter:List Iterator<item-type>):Boolean
return node == other-iter.node
end method
end type
向量
[edit | edit source]讓我們先編寫向量的迭代器。它將使向量的實現更加清晰。
type Vector Iterator<item-type>
data array:Array<item-type>
data index:Integer
constructor(my_array:Array<item-type>, my_index:Integer)
array := my_array
index := my_index
end constructor
method get-value():item-type
return array.get-element(index)
end method
method set-value(new-value:item-type)
array.set-element(index, new-value)
end method
method move-next()
index := index+1
end method
method equal(other-iter:List Iterator<item-type>):Boolean
return array==other-iter.array and index==other-iter.index
end method
end type
我們使用基本陣列資料型別來實現向量。始終保持陣列完全正確的大小效率低下（想想你必須進行多少次調整大小），所以我們儲存了size（向量中邏輯元素的數量）和capacity（陣列中的空間數量）這兩個值。陣列的有效索引將始終位於0到capacity-1的範圍內。
type Vector<item-type> data array:Array<item-type> data size:Integer data capacity:Integer
我們用 10 的容量初始化向量。選擇 10 是相當隨意的。如果我們想讓它看起來不那麼隨意，我們會選擇一個 2 的冪，而像你這樣的天真讀者會認為，這種選擇有一些深刻的、與二進位制相關的理由。
constructor()
array := create-array(0, 9)
size := 0
capacity := 10
end constructor
method get-begin():Vector-Iterator<item-type>
return new Vector-Iterator(array, 0)
end method
結束迭代器的索引為size。這比最高有效索引多 1。
method get-end():List Iterator<item-type>
return new Vector-Iterator(array, size)
end method
我們將使用此方法來幫助我們實現插入例程。呼叫它之後，陣列的capacity保證至少為new-capacity。一個簡單的實現將簡單地分配一個具有正好new-capacity個元素的新陣列，並將舊陣列複製過來。要了解為什麼這是低效的，想想如果我們開始在迴圈中追加元素會發生什麼。一旦我們超過了原始容量，每個新元素都需要我們複製整個陣列。這就是為什麼這個實現至少在每次需要增長時將底層陣列的大小加倍。
helper method ensure-capacity(new-capacity:Integer)
如果當前容量已經足夠大，則快速返回。
if capacity >= new-capacity
return
end if
現在，找到我們需要的新容量，
var allocated-capacity:Integer := max(capacity*2, new-capacity)
var new-array:Array<item-type> := create-array(0, allocated-capacity - 1)
複製舊陣列，
for i in 0..size-1
new-array.set-element(i, array.get-element(i))
end for
並更新向量的狀態。
array := new-array
capacity := allocated-capacity
end method
此方法使用了一個通常是非法的迭代器，該迭代器引用了向量開始之前的專案，以欺騙insert-after()做正確的事情。透過這樣做，我們避免了重複程式碼。
method prepend(new-item:item-type)
insert-after(new Vector-Iterator(array, -1), new-item)
end method
insert-after()需要複製iter和向量末尾之間的所有元素。這意味著通常情況下，它在時間內執行。但是，在iter引用向量中的最後一個元素的特殊情況下，我們不需要複製任何元素來為新元素騰出空間。追加操作可以在時間內執行，加上ensure-capacity()呼叫所需的時間。ensure-capacity()有時需要複製整個陣列，這需要時間。但更常見的是，它根本不需要做任何事情。
攤銷分析
實際上，如果你考慮一系列追加操作，這些操作從ensure-capacity()增加向量容量的時刻開始（在此處將容量稱為），並在容量下一次增加的時刻結束，你可以看到將有正好個追加操作。在容量下一次增加時，它將需要將個元素複製到新陣列中。所以這整個個函式呼叫的序列總共進行了次操作。我們將這種在個函式呼叫中進行了次操作的情況稱為“攤銷時間”。
method insert-after(iter:Vector Iterator<item-type>, new-item:item-type)
ensure-capacity(size+1)
此迴圈將向量中的所有元素複製到索引高一位的位置。我們從後向前迴圈，以便在複製每個後續元素之前為其騰出空間。
for i in size-1 .. iter.index+1 step -1
array.set-element(i+1, array.get-element(i))
end for
現在陣列中間有一個空位，我們可以將新元素放在那裡。
array.set-element(iter.index+1, new-item)
並更新向量的尺寸。
size := size+1 end method
同樣，也稍微作弊，以避免重複程式碼。
method remove-first() remove-after(new Vector-Iterator(array, -1)) end method
與insert-after()類似，remove-after需要複製iter和向量末尾之間的所有元素。因此，通常情況下，它在時間內執行。但在iter引用向量中的最後一個元素的特殊情況下，我們可以簡單地將向量的尺寸減 1，而無需複製任何元素。刪除最後一個元素的操作在時間內執行。
method remove-after(iter:List Iterator<item-type>)
for i in iter.index+1 .. size-2
array.set-element(i, array.get-element(i+1))
end for
size := size-1
end method
該方法有一個預設實現，但我們已經儲存了大小，因此可以在 時間內實現，而不是預設的
method get-size():Integer
return size
end method
由於陣列允許對元素進行常數時間訪問，因此可以在 時間內實現 get- 和 set-nth()，而不是預設實現的
method get-nth(n:Integer):item-type
return array.get-element(n)
end method
method set-nth(n:Integer, new-value:item-type)
array.set-element(n, new-value)
end method
end type
雙向列表
[edit | edit source]
有時我們希望 Data Structures/All Chapters 在列表中向後移動。雙向列表允許列表向前和向後搜尋。雙向列表實現了一個額外的 迭代器 函式，move-previous()。
Bidirectional List<item-type> ADT
get-begin():Bidirectional List Iterator<item-type>- 返回表示列表第一個元素的列表迭代器（我們很快就會定義它）。執行時間為 。
get-end():Bidirectional List Iterator<item-type>- 返回表示列表最後一個元素後面的一個元素的列表迭代器。執行時間為 。
insert(iter:Bidirectional List Iterator<item-type>, new-item:item-type)- 在 iter 之前新增一個新元素。執行時間為 。
remove(iter:Bidirectional List Iterator<item-type>)- 刪除 iter 指向的元素。在此呼叫之後，iter 將指向列表中的下一個元素。執行時間為 。
is-empty():Boolean- 如果列表中沒有元素，則為真。有一個預設實現。執行時間為 。
get-size():Integer- 返回列表中的元素數量。具有預設實現。在 時間內執行。
get-nth(n:Integer):item-type- 返回列表中第 n 個元素，從 0 開始計數。具有預設實現。在 時間內執行。
set-nth(n:Integer, new-value:item-type)- 將新值分配給列表中第 n 個元素，從 0 開始計數。具有預設實現。在 時間內執行。
Bidirectional List Iterator<item-type> ADT
get-value():item-type- 返回此迭代器指向的列表元素的值。如果迭代器超過末尾，則未定義。
set-value(new-value:item-type)- 為此迭代器指向的列表元素分配一個新值。如果迭代器超過末尾，則未定義。
move-next()- 使此迭代器指向列表中的下一個元素。如果迭代器超過末尾，則未定義。
move-previous()- 使此迭代器指向列表中的前一個元素。如果迭代器指向第一個列表元素，則未定義。
equal(other-iter:List Iterator<item-type>):Boolean- 如果另一個迭代器指向與該迭代器相同的列表元素，則為真。
所有操作都在 時間內執行。
雙向連結串列實現
[edit | edit source]
向量實現
[edit | edit source]我們已經見過的向量有一個非常合適的實現來成為一個雙向列表。我們所要做的就是為它及其迭代器新增額外的成員函式；舊的函式不需要更改。
type Vector<item-type> ... # already-existing data and methods
用原始的 insert-after() 方法來實現它。該方法執行完畢後，我們必須調整 iter 的索引，以便它仍然指向同一個元素。
method insert(iter:Bidirectional List Iterator<item-type>, new-item:item-type)
insert-after(new Vector-Iterator(iter.array, iter.index-1))
iter.move-next()
end method
還可以用舊函式來實現它。remove-after() 執行完畢後，索引將已經正確。
method remove(iter:Bidirectional List Iterator<item-type>)
remove-after(new Vector-Iterator(iter.array, iter.index-1))
end method
end type
權衡
[edit | edit source]
為了選擇適合工作的正確資料結構，我們需要了解我們打算對資料 *做什麼*。
- 我們是否知道在任何時候都不會超過 100 個數據，或者我們需要偶爾處理千兆位元組的資料？
- 我們將如何讀取資料？始終按時間順序？始終按名稱排序？隨機訪問記錄號？
- 我們是否總是將資料新增到末尾或開頭？或者我們會在中間執行很多插入和刪除操作？
我們必須在各種要求之間取得平衡。如果我們需要以 3 種不同的方式頻繁地讀取資料，請選擇一個允許我們以不太慢的速度執行這 3 種操作的資料結構。不要選擇一個對 *一種* 方式速度慢得無法忍受的資料結構，無論它對其他方式的速度有多快。
通常，某些任務的最短、最簡單的程式設計解決方案將使用線性 (1D) 陣列。
如果我們將資料保留為 ADT，那麼可以更容易地臨時切換到其他底層資料結構，並客觀地衡量它是否更快或更慢。
優點/缺點
[edit | edit source]在大多數情況下，陣列的優點是連結串列的缺點，反之亦然。
- 陣列優點（相對於連結串列）
- 索引 - 對陣列中任何元素的索引訪問速度很快；連結串列必須從開頭遍歷才能到達所需元素。
- 更快 - 通常，訪問陣列中的元素比訪問連結串列中的元素更快。
- 連結串列優點（相對於陣列）
- 調整大小 - 連結串列可以輕鬆地透過新增元素來調整大小，而不會影響列表中的其他元素；陣列只能透過分配新的記憶體塊並將所有元素複製到該塊來擴大。
- 插入 - 可以輕鬆地將元素插入到連結串列的中間：建立一個指向它後面的連結的新連結，並將前面的連結指向新連結。
旁註： - **如何在陣列中間插入元素**。如果陣列未滿，您可以將要插入的陣列位置或索引後的所有元素向前移動 1 位，然後插入您的元素。如果陣列已滿，並且您想插入元素，則需要“調整陣列大小”。需要建立一個比原始陣列大一個尺寸的新陣列來插入您的元素，然後將原始陣列的所有元素複製到新陣列中，同時考慮插入元素的位置或索引，然後插入您的元素。
棧是一種基本的資料結構，在邏輯上可以認為是線性結構，用真實的物理棧或堆來表示，在這種結構中，專案的插入和刪除發生在稱為棧頂的一個端點。基本概念可以透過將您的資料集想象成一堆盤子或書來闡明，您只能從棧頂拿取物品來移除東西。這種結構在整個程式設計過程中都有使用。
棧的基本實現也稱為 LIFO（後進先出），以說明它訪問資料的順序，因為正如我們將看到的，棧的實現方式有很多變化。
棧上可以執行三種基本操作。它們是 1) 將專案插入到棧中（push）。2) 從棧中刪除專案（pop）。3) 顯示棧的內容（peek 或 top）。
以下是一些 **棧資料型別** 通常支援的操作
Stack<item-type> 操作
push(new-item:item-type)- 將專案新增到棧頂。
top():item-type- 返回壓入棧的最後一個專案。
pop()- 從棧中刪除最晚壓入的專案。
is-empty():Boolean- 如果不再有專案可以彈出，並且沒有棧頂專案，則為真。
is-full():Boolean- 如果不再有專案可以壓入，則為真。
get-size():Integer- 返回棧中元素的數量。
除了 get-size() 之外的所有操作都可以在 時間內完成。get-size() 最壞情況下執行在
基本連結串列實現是您可以執行的最簡單的棧實現之一。從結構上來說，它是一個連結串列。
type Stack<item_type>
data list:Singly Linked List<item_type>
"stack follows the LIFO (last in first out) operation"
"queue follows the FIFO (first in first out) operation"
constructor()
list := new Singly-Linked-List()
end constructor
大多數操作都是透過將它們傳遞到底層連結串列來實現的。當您想將某個東西 **push** 到列表中時，您只需將其新增到連結串列的開頭。然後，之前的頂點從新增的專案中成為“next”，並且列表的 front 指標指向新專案。
method push(new_item:item_type)
list.prepend(new_item)
end method
要檢視 **top** 專案，您只需檢查連結串列中的第一個專案。
method top():item_type
return list.get-begin().get-value()
end method
當您想將某個東西 **pop** 出列表時，只需從連結串列中刪除第一個專案。
method pop()
list.remove-first()
end method
檢查是否為空很容易。只需檢查列表是否為空。
method is-empty():Boolean
return list.is-empty()
end method
檢查是否已滿很簡單。連結串列被認為是無限大小的。
method is-full():Boolean
return False
end method
檢查大小也會傳遞到列表中。
method get-size():Integer
return list.get-size()
end method
end type
釋出庫中的真實棧實現可能會重新實現連結串列，以便透過刪除不需要的功能來從實現中擠出最後一滴效能。上述實現為您提供了相關想法，您可以透過內聯連結串列程式碼來完成任何需要的最佳化。
在連結串列中，訪問第一個元素是一個 操作。列表包含一個指標，用於檢查空/滿狀態，如這裡所做的那樣，也是 （取決於做出了什麼樣的時間/空間權衡）。大多數情況下，棧的使用者不使用 getSize() 操作，因此可以透過不最佳化它來節省一些空間。
由於所有操作都在棧頂進行，因此陣列實現現在好得多。
public class StackArray implements Stack
{
protected int top;
protected Object[] data;
...
}
陣列實現將棧底保持在陣列的開頭。它向陣列的末尾增長。唯一的問題是，如果您在陣列已滿時嘗試壓入元素。如果是這樣
Assert.pre(!isFull(),"Stack is not full.");
將失敗，並丟擲異常。因此，使用 Vector（參見 StackVector）來實現更有意義，因為它允許無限制增長（以偶爾的 O(n) 延遲為代價）。
複雜度
除了偶爾的 push 和 clear 之外，所有操作都是 O(1)，push 和 clear 應該將所有條目替換為 null，以便它們被垃圾回收。陣列實現不會替換 null 條目。Vector 實現會...
使用棧，我們可以解決許多應用，其中一些列在下面。
將十進位制數轉換為二進位制數的邏輯如下所示
* Read a number
* Iteration (while number is greater than zero)
1. Find out the remainder after dividing the number by 2
2. Print the remainder
3. Divide the number by 2
* End the iteration
但是，這種邏輯存在問題。假設我們要找到二進位制形式的數字是 23。使用這種邏輯，我們得到的結果是 11101，而不是 10111。
為了解決這個問題，我們使用棧。我們利用棧的 LIFO 屬性。最初，我們將形成的二進位制位 push 到棧中，而不是直接列印它。在將整個數字轉換為二進位制形式後，我們一次 pop 一個數字，從棧中取出並打印出來。因此，我們得到十進位制數轉換為正確的二進位制形式。
演算法
1. Create a stack
2. Enter a decimal number which has to be converted into its equivalent binary form.
3. iteration1 (while number > 0)
3.1 digit = number % 2
3.2 Push digit into the stack
3.3 If the stack is full
3.3.1 Print an error
3.3.2 Stop the algorithm
3.4 End the if condition
3.5 Divide the number by 2
4. End iteration1
5. iteration2 (while stack is not empty)
5.1 Pop digit from the stack
5.2 Print the digit
6. End iteration2
7. STOP
棧最有趣的應用之一是在解決一個名為漢諾塔的謎題中找到的。根據一個古老的婆羅門故事，宇宙的存在是根據一群和尚花費的時間來計算的，這些和尚一直在工作，將 64 個圓盤從一個柱子移動到另一個柱子上。但是，關於如何執行此操作有一些規則，即
- 您一次只能移動一個圓盤。
- 為了臨時儲存，可以使用第三個柱子。
- 您不能將直徑更大的圓盤放在直徑更小的圓盤上。[1]
這裡我們假設 A 是第一個塔，B 是第二個塔，C 是第三個塔。
輸出：(當有 3 個圓盤時)
令 1 為最小的圓盤，2 為中等大小的圓盤，3 為最大的圓盤。
| 移動圓盤 | 從樁 | 到樁 |
|---|---|---|
| 1 | A | C |
| 2 | A | B |
| 1 | C | B |
| 3 | A | C |
| 1 | B | A |
| 2 | B | C |
| 1 | A | C |
輸出：(當有 4 個圓盤時)
| 移動圓盤 | 從樁 | 到樁 |
|---|---|---|
| 1 | A | B |
| 2 | A | C |
| 1 | B | C |
| 3 | A | B |
| 1 | C | A |
| 2 | C | B |
| 1 | A | B |
| 4 | A | C |
| 1 | B | C |
| 2 | B | A |
| 1 | C | A |
| 3 | B | C |
| 1 | A | B |
| 2 | A | C |
| 1 | B | C |
該解決方案的 C++ 程式碼可以用兩種方法實現
這裡我們假設 A 是第一個塔，B 是第二個塔，C 是第三個塔。(B 是中間塔)
void TowersofHanoi(int n, int a, int b, int c)
{
//Move top n disks from tower a to tower b, use tower c for intermediate storage.
if(n > 0)
{
TowersofHanoi(n-1, a, c, b); //recursion
cout << " Move top disk from tower " << a << " to tower " << b << endl ;
//Move n-1 disks from intermediate(b) to the source(a) back
TowersofHanoi(n-1, c, b, a); //recursion
}
}
// Global variable, tower [1:3] are three towers
arrayStack<int> tower[4];
void TowerofHanoi(int n)
{
// Preprocessor for moveAndShow.
for (int d = n; d > 0; d--) //initialize
tower[1].push(d); //add disk d to tower 1
moveAndShow(n, 1, 2, 3); /*move n disks from tower 1 to tower 3 using
tower 2 as intermediate tower*/
}
void moveAndShow(int n, int a, int b, int c)
{
// Move the top n disks from tower a to tower b showing states.
// Use tower c for intermediate storage.
if(n > 0)
{
moveAndShow(n-1, a, c, b); //recursion
int d = tower[a].top(); //move a disc from top of tower a to top of
tower[a].pop(); //tower b
tower[b].push(d);
showState(); //show state of 3 towers
moveAndShow(n-1, c, b, a); //recursion
}
}
然而，上面實現的複雜度是 O()。因此，很明顯，這個問題只能針對較小的 n 值解決（通常 n <= 30）。對於僧侶來說，按照上述規則，移動 64 個圓盤所花費的步數將是 18,446,744,073,709,551,615，這無疑需要花費大量的時間！！
採用 逆波蘭表示法 的計算器使用堆疊結構來儲存值。表示式可以用字首、字尾或中綴表示法表示。使用堆疊可以完成從一種表示式形式到另一種形式的轉換。許多編譯器使用堆疊來解析表示式、程式塊等的語法，然後翻譯成低階程式碼。大多數程式語言是 上下文無關語言，允許它們使用基於堆疊的機器進行解析。
輸入 (((2 * 5) - (1 * 2)) / (9 - 7))
輸出 4
分析: 五種型別的輸入字元
* Opening bracket * Numbers * Operators * Closing bracket * New line character
資料結構要求: 字元堆疊
演算法
1. Read one input character
2. Actions at end of each input
Opening brackets (2.1) Push into stack and then Go to step (1)
Number (2.2) Push into stack and then Go to step (1)
Operator (2.3) Push into stack and then Go to step (1)
Closing brackets (2.4) Pop it from character stack
(2.4.1) if it is opening bracket, then discard it, Go to step (1)
(2.4.2) Pop is used three times
The first popped element is assigned to op2
The second popped element is assigned to op
The third popped element is assigned to op1
Evaluate op1 op op2
Convert the result into character and
push into the stack
Go to step (2.4)
New line character (2.5) Pop from stack and print the answer
STOP
結果: 對完全括號化的中綴表示式的求值將以以下方式列印在顯示器上
輸入字串 (((2 * 5) - (1 * 2)) / (9 - 7))
| 輸入符號 | 堆疊（從底部到頂部） | 操作 |
|---|---|---|
| ( | ( | |
| ( | ( ( | |
| ( | ( ( ( | |
| 2 | ( ( ( 2 | |
| * | ( ( ( 2 * | |
| 5 | ( ( ( 2 * 5 | |
| ) | ( ( 10 | 2 * 5 = 10 & 壓入 |
| - | ( ( 10 - | |
| ( | ( ( 10 - ( | |
| 1 | ( ( 10 - ( 1 | |
| * | ( ( 10 - ( 1 * | |
| 2 | ( ( 10 - ( 1 * 2 | |
| ) | ( ( 10 - 2 | 1 * 2 = 2 & 壓入 |
| ) | ( 8 | 10 - 2 = 8 & 壓入 |
| / | ( 8 / | |
| ( | ( 8 / ( | |
| 9 | ( 8 / ( 9 | |
| - | ( 8 / ( 9 - | |
| 9 | ( 8 / ( 9 - 7 | |
| ) | ( 8 / 2 | 9 - 7 = 2 & 壓入 |
| ) | 4 | 8 / 2 = 4 & 壓入 |
| 新行 | 空 | 彈出 & 列印 |
C 程式
int main (int argc, char
struct ch *charactop;
struct integer *integertop;
char rd, op;
int i = 0, op1, op2;
charactop = cclearstack();
integertop = iclearstack();
while(1)
{
rd = argv[1][i++];
switch(rd)
{
case '+':
case '-':
case '/':
case '*':
case '(': charactop = cpush(charactop, rd);
break;
case ')': integertop = ipop (integertop, &op2);
integertop = ipop (integertop, &op1);
charactop = cpop (charactop, &op);
while(op != '(')
{
integertop = ipush (integertop, eval(op, op1, op2));
charactop = cpop (charactop, &op);
if (op != '(')
{
integertop = ipop(integertop, &op2);
integertop = ipop(integertop, &op1);
}
}
break;
case '\0': while (! cemptystack(charactop))
{
charactop = cpop(charactop, &op);
integertop = ipop(integertop, &op2);
integertop = ipop(integertop, &op1);
integertop = ipush(integertop, eval(op, op1, op2));
}
integertop = ipop(integertop, &op1);
printf("\n The final solution is: %d\n", op1);
return 0;
default: integertop = ipush(integertop, rd - '0');
}
}
}
int eval(char op, int op1, int op2)
{
switch (op)
{
case '+': return op1 + op2;
case '-': return op1 - op2;
case '/': return op1 / op2;
case '*': return op1 * op2;
}
}
程式的輸出
在命令列輸入的輸入: (((2 * 5) - (1 * 2)) / (9 - 7)) [3]
輸入 (2 * 5 - 1 * 2) / (11 - 9)
輸出 4
分析: 有五種型別的輸入字元，它們是
* Opening brackets
* Numbers
* Operators
* Closing brackets
* New line character (\n)
如果將運算子讀作輸入字元，我們不知道該怎麼辦。透過實現運算子的優先順序規則，我們對這個問題有一個解決方案。
優先順序規則 我們應該在讀入運算子時執行比較優先順序檢查，然後壓入它。如果堆疊的 頂部 包含優先順序高於或等於輸入運算子優先順序的運算子，那麼我們就 彈出 它並列印它。我們不斷執行優先順序檢查，直到堆疊的 頂部 或者包含優先順序較低的運算子，或者不包含運算子。
此問題的資料結構要求: 字元堆疊和整數堆疊
演算法
1. Read an input character
2. Actions that will be performed at the end of each input
Opening brackets (2.1) Push it into stack and then Go to step (1)
Digit (2.2) Push into stack, Go to step (1)
Operator (2.3) Do the comparative priority check
(2.3.1) if the character stack's top contains an operator with equal
or higher priority, then pop it into op
Pop a number from integer stack into op2
Pop another number from integer stack into op1
Calculate op1 op op2 and push the result into the integer
stack
Closing brackets (2.4) Pop from the character stack
(2.4.1) if it is an opening bracket, then discard it and Go to
step (1)
(2.4.2) To op, assign the popped element
Pop a number from integer stack and assign it op2
Pop another number from integer stack and assign it
to op1
Calculate op1 op op2 and push the result into the integer
stack
Convert into character and push into stack
Go to the step (2.4)
New line character (2.5) Print the result after popping from the stack
STOP
結果: 對非完全括號化的中綴表示式的求值將以以下方式列印
輸入字串 (2 * 5 - 1 * 2) / (11 - 9)
| 輸入符號 | 字元堆疊（從底部到頂部） | 整數堆疊（從底部到頂部） | 執行的操作 |
|---|---|---|---|
| ( | ( | ||
| 2 | ( | 2 | |
| * | ( * | 壓入 因為 * 優先順序更高 | |
| 5 | ( * | 2 5 | |
| - | ( * | 由於 - 優先順序較低，我們執行 2 * 5 = 10 | |
| ( - | 10 | 我們壓入 10，然後壓入 - | |
| 1 | ( - | 10 1 | |
| * | ( - * | 10 1 | 壓入 * 因為它優先順序更高 |
| 2 | ( - * | 10 1 2 | |
| ) | ( - | 10 2 | 執行 1 * 2 = 2 並壓入它 |
| ( | 8 | 彈出 - 和 10 - 2 = 8 並壓入，彈出 ( | |
| / | / | 8 | |
| ( | / ( | 8 | |
| 11 | / ( | 8 11 | |
| - | / ( - | 8 11 | |
| 9 | / ( - | 8 11 9 | |
| ) | / | 8 2 | 執行 11 - 9 = 2 並壓入它 |
| 新行 | 4 | 執行 8 / 2 = 4 並壓入它 | |
| 4 | 列印輸出，即 4 |
C 程式
int main (int argc, char *argv[])
{
struct ch *charactop;
struct integer *integertop;
char rd, op;
int i = 0, op1, op2;
charactop = cclearstack();
integertop = iclearstack();
while(1)
{
rd = argv[1][i++];
switch(rd)
{
case '+':
case '-':
case '/':
case '*': while ((charactop->data != '(') && (!cemptystack(charactop)))
{
if(priority(rd) > (priority(charactop->data))
break;
else
{
charactop = cpop(charactop, &op);
integertop = ipop(integertop, &op2);
integertop = ipop(integertop, &op1);
integertop = ipush(integertop, eval(op, op1, op2);
}
}
charactop = cpush(charactop, rd);
break;
case '(': charactop = cpush(charactop, rd);
break;
case ')': integertop = ipop (integertop, &op2);
integertop = ipop (integertop, &op1);
charactop = cpop (charactop, &op);
while(op != '(')
{
integertop = ipush (integertop, eval(op, op1, op2);
charactop = cpop (charactop, &op);
if (op != '(')
{
integertop = ipop(integertop, &op2);
integertop = ipop(integertop, &op1);
}
}
break;
case '\0': while (!= cemptystack(charactop))
{
charactop = cpop(charactop, &op);
integertop = ipop(integertop, &op2);
integertop = ipop(integertop, &op1);
integertop = ipush(integertop, eval(op, op1, op2);
}
integertop = ipop(integertop, &op1);
printf("\n The final solution is: %d", op1);
return 0;
default: integertop = ipush(integertop, rd - '0');
}
}
}
int eval(char op, int op1, int op2)
{
switch (op)
{
case '+': return op1 + op2;
case '-': return op1 - op2;
case '/': return op1 / op2;
case '*': return op1 * op2;
}
}
int priority (char op)
{
switch(op)
{
case '^':
case '$': return 3;
case '*':
case '/': return 2;
case '+':
case '-': return 1;
}
}
程式的輸出
在命令列輸入的輸入 (2 * 5 - 1 * 2) / (11 - 9)
輸出: 4 [3]
輸入: x + 6 * ( y + z ) ^ 3
輸出:' 4
分析: 有三種類型的輸入字元
* Numbers
* Operators
* New line character (\n)
資料結構要求: 字元堆疊和整數堆疊
演算法
1. Read one character input at a time and keep pushing it into the character stack until the new
line character is reached
2. Perform pop from the character stack. If the stack is empty, go to step (3)
Number (2.1) Push in to the integer stack and then go to step (1)
Operator (2.2) Assign the operator to op
Pop a number from integer stack and assign it to op1
Pop another number from integer stack
and assign it to op2
Calculate op1 op op2 and push the output into the integer
stack. Go to step (2)
3. Pop the result from the integer stack and display the result
結果: 字首表示式的求值將以以下方式列印
輸入字串 / - * 2 5 * 1 2 - 11 9
| 輸入符號 | 字元堆疊（從底部到頂部） | 整數堆疊（從底部到頂部） | 執行的操作 |
|---|---|---|---|
| / | / | ||
| - | / | ||
| * | / - * | ||
| 2 | / - * 2 | ||
| 5 | / - * 2 5 | ||
| * | / - * 2 5 * | ||
| 1 | / - * 2 5 * 1 | ||
| 2 | / - * 2 5 * 1 2 | ||
| - | / - * 2 5 * 1 2 - | ||
| 11 | / - * 2 5 * 1 2 - 11 | ||
| 9 | / - * 2 5 * 1 2 - 11 9 | ||
| \n | / - * 2 5 * 1 2 - 11 | 9 | |
| / - * 2 5 * 1 2 - | 9 11 | ||
| / - * 2 5 * 1 2 | 2 | 11 - 9 = 2 | |
| / - * 2 5 * 1 | 2 2 | ||
| / - * 2 5 * | 2 2 1 | ||
| / - * 2 5 | 2 2 | 1 * 2 = 2 | |
| / - * 2 | 2 2 5 | ||
| / - * | 2 2 5 2 | ||
| / - | 2 2 10 | 5 * 2 = 10 | |
| / | 2 8 | 10 - 2 = 8 | |
| 堆疊為空 | 4 | 8 / 2 = 4 | |
| 堆疊為空 | 列印 4 |
C 程式
int main (int argc, char *argv[])
{
struct ch *charactop = NULL;
struct integer *integertop = NULL;
char rd, op;
int i = 0, op1, op2;
charactop = cclearstack();
integertop = iclearstack();
rd = argv[1][i];
while(rd != '\0')
{
charactop = cpush(charactop, rd);
rd = argv[1][i++];
}
while(!emptystack(charactop))
{
charactop = cpop(charactop, rd);
switch(rd)
{
case '+':
case '-':
case '/':
case '*':
op = rd;
integertop = ipop(integertop, &op2);
integertop = ipop(integertop, &op1);
integertop = ipush(integertop, eval(op, op1, op2));
break;
default: integertop = ipush(integertop, rd - '0');
}
}
}
int eval(char op, int op1, int op2)
{
switch (op)
{
case '+': return op1 + op2;
case '-': return op1 - op2;
case '/': return op1 / op2;
case '*': return op1 * op2;
}
}
int priority (char op)
{
switch(op)
{
case '^':
case '$': return 3;
case '*':
case '/': return 2;
case '+':
case '-': return 1;
}
}
程式的輸出
在命令列輸入的輸入: / - * 2 5 * 1 2 - 11 9
輸出: 4 [3]
輸入 (((8 + 1) - (7 - 4)) / (11 - 9))
輸出 8 1 + 7 4 - - 11 9 - /
分析: 有五種型別的輸入字元，它們是
* Opening brackets
* Numbers
* Operators
* Closing brackets
* New line character (\n)
要求: 字元堆疊
演算法
1. Read an character input
2. Actions to be performed at end of each input
Opening brackets (2.1) Push into stack and then Go to step (1)
Number (2.2) Print and then Go to step (1)
Operator (2.3) Push into stack and then Go to step (1)
Closing brackets (2.4) Pop it from the stack
(2.4.1) If it is an operator, print it, Go to step (1)
(2.4.2) If the popped element is an opening bracket,
discard it and go to step (1)
New line character (2.5) STOP
因此，將中綴表示式轉換為字尾表示式後的最終輸出如下所示
| 輸入 | 操作 | 堆疊（操作後） | 顯示器上的輸出 |
|---|---|---|---|
| ( | (2.1) 將運算元壓入堆疊 | ( | |
| ( | (2.1) 將運算元壓入堆疊 | ( ( | |
| ( | (2.1) 將運算元壓入堆疊 | ( ( ( | |
| 8 | (2.2) 列印它 | 8 | |
| + | (2.3) 將運算子壓入堆疊 | ( ( ( + | 8 |
| 1 | (2.2) 列印它 | 8 1 | |
| ) | (2.4) 從堆疊中彈出: 由於彈出的元素是 +，所以列印它 | ( ( ( | 8 1 + |
| (2.4) 從堆疊中彈出: 由於彈出的元素是 (，所以我們忽略它並讀取下一個字元 | ( ( | 8 1 + | |
| - | (2.3) 將運算子壓入堆疊 | ( ( - | |
| ( | (2.1) 將運算元壓入堆疊 | ( ( - ( | |
| 7 | (2.2) 列印它 | 8 1 + 7 | |
| - | (2.3) 將運算子壓入堆疊 | ( ( - ( - | |
| 4 | (2.2) 列印它 | 8 1 + 7 4 | |
| ) | (2.4) 從堆疊中彈出: 由於彈出的元素是 -，所以列印它 | ( ( - ( | 8 1 + 7 4 - |
| (2.4) 從堆疊中彈出: 由於彈出的元素是 (，所以我們忽略它並讀取下一個字元 | ( ( - | ||
| ) | (2.4) 從堆疊中彈出: 由於彈出的元素是 -，所以列印它 | ( ( | 8 1 + 7 4 - - |
| (2.4) 從堆疊中彈出: 由於彈出的元素是 (，所以我們忽略它並讀取下一個字元 | ( | ||
| / | (2.3) 將運算元壓入堆疊 | ( / | |
| ( | (2.1) 壓入堆疊 | ( / ( | |
| 11 | (2.2) 列印它 | 8 1 + 7 4 - - 11 | |
| - | (2.3) 將運算元壓入堆疊 | ( / ( - | |
| 9 | (2.2) 列印它 | 8 1 + 7 4 - - 11 9 | |
| ) | (2.4) 從堆疊中彈出: 由於彈出的元素是 -，所以列印它 | ( / ( | 8 1 + 7 4 - - 11 9 - |
| (2.4) 從堆疊中彈出: 由於彈出的元素是 (，所以我們忽略它並讀取下一個字元 | ( / | ||
| ) | (2.4) 從堆疊中彈出: 由於彈出的元素是 /，所以列印它 | ( | 8 1 + 7 4 - - 11 9 - / |
| (2.4) 從堆疊中彈出: 由於彈出的元素是 (，所以我們忽略它並讀取下一個字元 | 堆疊為空 | ||
| 換行符 | (2.5) 停止 |
這是一個關於堆疊的非常好的應用。假設一列貨運列車有 n 節車廂，每節車廂都將在不同的車站卸貨。它們從 1 到 n 編號，貨運列車按照從 n 到 1 的順序訪問這些車站。顯然，火車車廂按其目的地進行標記。為了方便從列車中卸下車廂，我們必須將它們按其編號（即從 1 到 n）的升序排列。當車廂按此順序排列時，它們可以在每個車站被分離。我們在一個有 輸入軌道、輸出軌道 和 k 個位於輸入和輸出軌道之間的中間軌道（即 中間軌道）的調車場重新排列車廂。
為了重新排列車廂，我們從前到後檢查輸入軌道上的車廂。如果正在檢查的車廂是輸出排列中的下一個車廂，那麼我們將它直接移動到 輸出軌道。如果不是，我們將它移動到 中間軌道 並將它留在那裡，直到將它放到 輸出軌道 上。中間軌道以 LIFO 的方式執行，因為車廂從頂部進入和離開這些軌道。當重新排列車廂時，只允許以下移動
- 車廂可以從輸入軌道的最前端（即右端）移動到中間軌道的頂部，也可以移動到輸出軌道的左端。
- 車廂可以從中間軌道的頂部移動到輸出軌道的左端。
圖中顯示了一個 k = 3 的調車場，中間軌道為 H1、H2 和 H3，n = 9。貨運列車的 n 節車廂從輸入軌道開始，最終以從右到左的順序 1 到 n 排列在輸出軌道上。車廂最初以從後到前的順序為 5、8、1、7、4、2、9、6、3。後續的車廂將以所需的順序進行重新排列。
- 考慮圖中的輸入排列，我們注意到汽車 3 在最前面，所以它還不能輸出，因為它需要先於汽車 1 和 2 輸出。所以，汽車 3 被分離並移動到保持軌道 H1 上。
- 下一輛汽車 6 無法輸出，它被移動到保持軌道 H2 上。因為我們必須先輸出汽車 3 才能輸出汽車 6，如果我們將汽車 6 移動到保持軌道 H1 上，這是不可能的。
- 現在很明顯，我們將汽車 9 移動到 H3 上。
對保持軌道上汽車進行重新排列的要求是，汽車應按從上到下的升序排列。
- 因此，現在將汽車 2 移動到保持軌道 H1 上，以滿足前面的語句。如果我們將汽車 2 移動到 H2 或 H3 上，那麼我們將沒有地方移動汽車 4、5、7 或 8。當新的汽車 λ 被移動到保持軌道上時，對未來汽車放置的限制最小，該保持軌道的頂部有一個標籤為 Ψ 的汽車，其中 λ < Ψ。我們可以稱其為分配規則，用於決定特定汽車是否屬於特定保持軌道。
- 當考慮汽車 4 時，有三個地方可以移動汽車：H1、H2 和 H3。這些軌道頂部分別是 2、6 和 9。所以使用上述分配規則，我們將汽車 4 移動到 H2 上。
- 汽車 7 被移動到 H3 上。
- 下一輛汽車 1 的標籤最小，所以它被移動到輸出軌道上。
- 現在是時候輸出汽車 2 和 3 了，它們來自 H1（簡而言之，來自 H1 的所有汽車都被附加到輸出軌道上的汽車 1 上）。
汽車 4 被移動到輸出軌道上。此時，沒有其他汽車可以被移動到輸出軌道上。
- 下一輛汽車，汽車 8，被移動到保持軌道 H1 上。
- 汽車 5 從輸入軌道輸出。汽車 6 從 H2 移動到輸出軌道，汽車 7 從 H3 移動到輸出軌道，汽車 8 從 H1 移動到輸出軌道，汽車 9 從 H3 移動到輸出軌道。
排序意味著以特定順序排列一組元素。無論是升序還是降序，按基數還是字母順序，或其變體。產生的排序可能性將僅受源元素型別的限制。
快速排序是一種分治型別的演算法。在這種方法中，為了對一組數字進行排序，我們將它縮減為兩個更小的集合，然後對這兩個更小的集合進行排序。
這可以用以下示例來解釋
假設A是以下數字的列表
在縮減步驟中，我們找到其中一個數字的最終位置。在本例中，假設我們必須找到 48 的最終位置，它是列表中的第一個數字。
為了實現這一點，我們採用以下方法。從最後一個數字開始，從右到左移動。將每個數字與 48 進行比較。如果數字小於 48，我們停止在該數字處並將它與 48 進行交換。
在我們的例子中，數字是 24。因此，我們將 24 和 48 進行交換。
48 右側的數字 96 和 72 大於 48。現在從 24 開始，以相反的方向掃描數字，即從左到右。將每個數字與 48 進行比較，直到找到一個大於 48 的數字。
在本例中，它是 60。因此，我們將 48 和 60 進行交換。
注意，48 左側的數字 12、24 和 36 都小於 48。現在，從 60 開始，從右到左方向掃描數字。一旦找到較小的數字，就將其與 48 進行交換。
在本例中，它是 44。將其與 48 進行交換。最終結果是
現在，從 44 開始，從左到右掃描列表，直到找到一個大於 48 的數字。
這樣一個數字是 84。將其與 48 進行交換。最終結果是
現在，從 84 開始，從右到左遍歷列表，直到到達小於 48 的數字。在到達 48 之前，我們沒有找到這樣的數字。這意味著列表中的所有數字都已掃描並與 48 進行比較。此外，我們注意到所有小於 48 的數字都在它左側，所有大於 48 的數字都在它右側。
最終分割槽如下所示
因此，48 已被放置到其正確的位置，現在我們的任務減少到對兩個分割槽進行排序。這個建立分割槽的步驟可以對每個包含 2 個或多個元素的分割槽重複進行。因為我們一次只能處理一個分割槽，所以我們應該能夠跟蹤其他分割槽，以便將來進行處理。
這是透過使用兩個名為 LOWERBOUND 和 UPPERBOUND 的堆疊來臨時儲存這些分割槽來完成的。分割槽的第一個和最後一個元素的地址分別被推入 LOWERBOUND 和 UPPERBOUND 堆疊。現在，只有在從堆疊中彈出其邊界值後，才會將上述縮減步驟應用於分割槽。
我們可以從以下示例中理解這一點
以包含 12 個元素的上述列表 A 為例。該演算法首先將 A 的邊界值，即 1 和 12，分別推入 LOWERBOUND 和 UPPERBOUND 堆疊。因此，堆疊如下所示
LOWERBOUND: 1 UPPERBOUND: 12
為了執行縮減步驟，堆疊頂部的值將從堆疊中彈出。因此，兩個堆疊都變為空。
LOWERBOUND: {empty} UPPERBOUND: {empty}
現在，縮減步驟導致 48 被固定到第 5 個位置，並建立了兩個分割槽，一個是從位置 1 到 4，另一個是從位置 6 到 12。因此，值 1 和 6 被推入 LOWERBOUND 堆疊，4 和 12 被推入 UPPERBOUND 堆疊。
LOWERBOUND: 1, 6 UPPERBOUND: 4, 12
為了再次應用縮減步驟，堆疊頂部的值將被彈出。因此，值 6 和 12 被彈出。因此，堆疊如下所示
LOWERBOUND: 1 UPPERBOUND: 4
現在將縮減步驟應用於第二個分割槽，即從第 6 個到第 12 個元素。
縮減步驟之後，98 被固定在第 11 個位置。因此，第二個分割槽只有一個元素。因此，我們將第一個分割槽的上界和下界值推入堆疊。因此，堆疊如下所示
LOWERBOUND: 1, 6 UPPERBOUND: 4, 10
處理以以下方式進行，並在堆疊不包含要處理的任何分割槽的上界和下界值，並且列表被排序後結束。
在股票跨度問題中，我們將藉助堆疊解決一個金融問題。
假設對於一隻股票，我們有一系列n天的每日價格報價，股票價格在某一天的跨度定義為股票價格在當前天小於或等於其價格的連續天數的最大值。
輸入：一個包含n個元素的陣列P
輸出：一個包含n個元素的陣列S，使得 S[i] 是最大的整數 k，使得 k <= i + 1 且 P[j] <= P[i] 對於 j = i - k + 1,.....,i
演算法
1. Initialize an array P which contains the daily prices of the stocks
2. Initialize an array S which will store the span of the stock
3. for i = 0 to i = n - 1
3.1 Initialize k to zero
3.2 Done with a false condition
3.3 repeat
3.3.1 if (P[i - k] <= P[i]) then
Increment k by 1
3.3.2 else
Done with true condition
3.4 Till (k > i) or done with processing
Assign value of k to S[i] to get the span of the stock
4. Return array S
現在，分析該演算法的執行時間，我們觀察到
- 我們在開始時初始化了陣列 S，並在結束時返回它。這是一個常數時間操作，因此需要O(n) 時間。
- repeat 迴圈巢狀在for 迴圈中。for 迴圈，其計數器為i，執行了 n 次。不在 repeat 迴圈中，而在 for 迴圈中的語句執行了n次。因此，這些語句以及 i 的遞增和條件測試需要O(n) 時間。
- 在外部 for 迴圈的 i 重複中，內部repeat 迴圈的主體最多執行 i + 1 次。在最壞情況下，元素 S[i] 大於所有之前的元素。因此，測試 if 條件、該條件後的語句以及測試 until 條件將在外部 for 迴圈的迭代 i 中執行 i + 1 次。因此，內部迴圈的總時間為O(n(n + 1)/2)，即O()
所有這些步驟的執行時間是透過將所有這三個步驟所花費的時間相加來計算的。前兩項是O()，而最後一項是O()。因此，該演算法的總執行時間為O()。
為了更有效地計算跨度，我們發現，如果我們知道在i之前最近的日期，使得該日期的股票價格高於當前日期的股票價格，則可以很容易地計算出特定日期的跨度。如果存在這樣的日期，我們可以用 h(i) 來表示它，並將 h(i) 初始化為 -1。
因此，特定日期的跨度由以下公式給出：s = i - h(i)。
為了實現此邏輯，我們使用堆疊作為抽象資料型別來儲存日期 i、h(i)、h(h(i)) 等等。當我們從第 i-1 天到第 i 天時，我們將彈出會彈出股票價格小於或等於 p(i) 的日期，然後將日期 i 的值壓回堆疊。
這裡，我們假設堆疊是透過佔用O(1)（即常數時間）的操作來實現的。該演算法如下：
輸入：一個包含n個元素的陣列 P 和一個空的堆疊 N
輸出：一個包含n個元素的陣列S，使得 P[i] 是最大的整數 k，滿足 k <= i + 1 且對於 j = i - k + 1,.....,i，P[y] <= P[i]。
演算法
1. Initialize an array P which contains the daily prices of the stocks
2. Initialize an array S which will store the span of the stock
3. for i = 0 to i = n - 1
3.1 Initialize k to zero
3.2 Done with a false condition
3.3 while not (Stack N is empty or done with processing)
3.3.1 if ( P[i] >= P[N.top())] then
Pop a value from stack N
3.3.2 else
Done with true condition
3.4 if Stack N is empty
3.4.1 Initialize h to -1
3.5 else
3.5.1 Initialize stack top to h
3.5.2 Put the value of h - i in S[i]
3.5.3 Push the value of i in N
4. Return array S
現在，分析該演算法的執行時間，我們觀察到
- 我們在開始時初始化了陣列 S，並在結束時返回它。這是一個常數時間操作，因此需要O(n) 時間。
- while 迴圈巢狀在for 迴圈中。for 迴圈的計數器是i，執行 n 次。不在重複迴圈中，但在 for 迴圈中的語句執行n 次。因此，這些語句以及 i 的遞增和條件測試需要O(n) 時間。
- 現在，觀察for 迴圈的i 次重複期間的內部 while 迴圈。語句done with a true condition 最多執行一次，因為它會導致退出迴圈。假設 t(i) 是語句Pop a value from stack N 執行的次數。因此，很明顯，while not (Stack N is empty or done with processing) 最多被測試 t(i) + 1 次。
- 將 while 迴圈中所有操作的執行時間相加，我們得到
- 一旦從堆疊 N 中彈出元素，就永遠不會再壓回堆疊。因此，
因此，while 迴圈中所有語句的執行時間為O()
透過將所有這些步驟所花費的時間相加，可以計算出演算法中所有步驟的執行時間。每個步驟的執行時間為O()。因此，該演算法的執行時間複雜度為O()。
相關連結
[edit | edit source]佇列
[edit | edit source]佇列是一種基本的資料結構，在整個程式設計中使用。您可以將其視為雜貨店裡的隊伍。排在隊伍最前面的人是最先得到服務的人，就像佇列一樣。
佇列也稱為 FIFO（先進先出），以展示其訪問資料的方式。
Queue<item-type> 操作
enqueue(new-item:item-type)- 將一個專案新增到佇列的末尾。
front():item-type- 返回佇列最前面的專案。
dequeue()- 從佇列中移除最前面的專案。
is-empty():Boolean- 如果不再有專案可以出隊，並且沒有最前面的專案，則為真。
is-full():Boolean- 如果不再有專案可以入隊，則為真。
get-size():Integer- 返回佇列中的元素數量。
除了 get-size() 之外的所有操作都可以在 時間內完成。get-size() 最壞情況下執行在
連結串列實現
[edit | edit source]基本連結串列實現使用單鏈表，並使用尾指標跟蹤佇列的尾部。
type Queue<item_type>
data list:Singly Linked List<item_type>
data tail:List Iterator<item_type>
constructor()
list := new Singly-Linked-List()
tail := list.get-begin() # null
end constructor
當您想要入隊某些內容時，只需將其新增到尾指標所指向的專案後面即可。因此，與新增的專案相比，之前的尾部被視為下一個，並且尾指標指向新專案。如果列表為空，則此方法不適用，因為尾部迭代器不引用任何內容。
method enqueue(new_item:item_type)
if is-empty()
list.prepend(new_item)
tail := list.get-begin()
else
list.insert_after(new_item, tail)
tail.move-next()
end if
end method
佇列中的最前面的專案只是連結串列的頭部指標所引用的專案。
method front():item_type
return list.get-begin().get-value()
end method
當您想要從列表中出隊某些內容時，只需將頭部指標指向頭部專案的 previous 即可。舊的頭部專案是您從列表中移除的專案。如果列表現在為空，我們必須修復尾部迭代器。
method dequeue()
list.remove-first()
if is-empty()
tail := list.get-begin()
end if
end method
檢查是否為空很容易。只需檢查列表是否為空。
method is-empty():Boolean
return list.is-empty()
end method
檢查是否已滿很簡單。連結串列被認為是無限大小的。
method is-full():Boolean
return False
end method
檢查大小也會傳遞到列表中。
method get-size():Integer
return list.get-size()
end method
end type
效能分析
[edit | edit source]在連結串列中，訪問第一個元素是一個 操作，因為列表包含一個指向它的指標。因此，入隊、最前面和出隊都是快速 操作。
這裡所做的空/滿檢查也是。
getSize() 的效能取決於連結串列實現中相應操作的效能。它可能是 ，或 ，取決於所做的時間/空間權衡。大多數情況下，佇列的使用者不使用 getSize() 操作，因此可以透過不最佳化它來節省一些空間。
迴圈陣列實現
[edit | edit source]效能分析
[edit | edit source]優先佇列實現
[edit | edit source]
相關連結
[edit | edit source]雙端佇列
[edit | edit source]雙端佇列是一種同構元素列表，其中在兩端都執行插入和刪除操作。
由於這種特性，它被稱為雙端佇列，即雙端佇列。
雙端佇列有兩種型別
- 輸入受限佇列：它只允許在一端插入
- 輸出受限佇列：它只允許在一端刪除
參考文獻
[edit | edit source]樹
[edit | edit source]樹是一個非空集合，其中一個元素被指定為樹的根，而剩餘元素被劃分成非空集合，每個集合都是根的子樹。
樹節點具有許多有用的屬性。節點的深度是從根到該節點的路徑的長度（或邊的數量）。節點的高度是從該節點到其葉子的最長路徑。樹的高度是根的高度。葉節點沒有子節點——它唯一的路徑是向上到其父節點。
請參閱樹的公理化發展及其後果以獲取更多資訊。
樹的型別
二叉樹：每個節點有零個、一個或兩個子節點。此斷言使許多樹操作變得簡單高效。
二叉搜尋樹：二叉樹，其中任何左子節點的值都小於其父節點，任何右子節點的值都大於或等於其父節點的值。
遍歷
[edit | edit source]許多問題需要我們以一種系統的方式訪問樹的節點：例如計算存在多少個節點或找到最大元素的任務。對於二叉樹，有三種不同的方法：前序、後序和中序，它們都執行相同的三個操作：遞迴遍歷左子樹和右子樹並訪問當前節點。不同之處在於演算法訪問當前節點的時間
前序：當前節點、左子樹、右子樹（DLR）
後序：左子樹、右子樹、當前節點（LRD）
中序：左子樹、當前節點、右子樹（LDR）
層序：從根節點開始，逐層從左到右。
- 訪問意味著執行一些涉及樹中當前節點的操作，比如增加計數器或檢查當前節點的值是否大於任何其他記錄的值。
樹遍歷的示例實現
[edit | edit source]preorder(node) visit(node) if node.left ≠ null then preorder(node.left) if node.right ≠ null then preorder(node.right)
inorder(node) if node.left ≠ null then inorder(node.left) visit(node) if node.right ≠ null then inorder(node.right)
postorder(node) if node.left ≠ null then postorder(node.left) if node.right ≠ null then postorder(node.right) visit(node)
levelorder(root) queue<node> q q.push(root) while not q.empty do node = q.pop visit(node) if node.left ≠ null then q.push(node.left) if node.right ≠ null then q.push(node.right)
對於對堆疊要求較低的演算法，請參閱執行緒樹。
樹遍歷的示例
[edit | edit source]
preorder: 50,30, 20, 40, 90, 100 inorder: 20,30,40,50, 90, 100 postorder: 20,40,30,100,90,50
平衡
[edit | edit source]當已經排序的條目儲存在樹中時，所有新記錄都將走相同的路線，樹看起來更像一個列表（這樣的樹稱為退化樹）。因此，樹需要平衡例程，確保所有分支下都有相同數量的記錄。這將使樹中的搜尋保持最佳速度。具體來說，如果具有n個節點的樹是退化樹，則透過樹的最長路徑將是 n 個節點；如果它是平衡樹，則最長路徑將是log n個節點。
Algorithms/左旋: 本文展示瞭如何在 樹堆 中應用平衡操作來建立優先堆不變式。樹堆是一種資料結構，它具有堆的佇列效能和樹的關鍵查詢效能。平衡操作可以在保持另一種排序（即二叉樹排序）的同時改變樹的結構。二叉樹排序的順序是從左到右，左節點的鍵小於右節點的鍵，而優先順序排序是從上到下，較高級別的節點的優先順序高於較低級別的節點。或者，優先順序可以被看作另一個排序鍵，只是查詢特定鍵的過程更加複雜。
平衡操作可以在不影響左右順序的情況下將節點上下移動。
AVL 樹: 按照以下規範進行平衡的二叉搜尋樹：任何節點的兩個子樹的高度差最多為 1。
紅黑樹: 一種平衡的二叉搜尋樹，使用基於分配給節點的顏色以及附近節點的顏色進行平衡演算法。
AA 樹: 一種平衡樹，實際上是紅黑樹的一種更嚴格的變體。
典型的二叉搜尋樹如下所示
節點 儲存在樹中的任何項。根節點 樹中最頂端的項。（上圖中的樹為 50）子節點 當前節點下方的節點。（上圖中的樹為 30 的子節點為 20 和 40）父節點 當前節點正上方的節點。（上圖中的樹為 100 的父節點為 90）葉節點 沒有子節點的節點。（上圖中的樹為 20 是葉節點）
要在二叉樹中搜索專案，請執行以下操作
- 從根節點開始
- 如果您要搜尋的專案小於根節點，則移至根節點的左子節點；如果您要搜尋的專案大於根節點，則移至根節點的右子節點；如果它等於根節點，則表示您已經找到了要查詢的專案。
- 現在檢查您要搜尋的專案是否等於、小於或大於您當前所在的節點。同樣地，如果要搜尋的專案小於當前節點，則移至左子節點；如果要搜尋的專案大於當前節點，則移至右子節點。
- 重複此過程，直到找到要搜尋的專案，或直到節點在正確的分支上沒有子節點，在這種情況下，樹不包含您要查詢的專案。
例如，要查詢節點 40...
- 根節點是 50，它大於 40，因此您移至 50 的左子節點。
- 50 的左子節點是 30，它小於 40，因此您接下來移至 30 的右子節點。
- 30 的右子節點是 40，因此您已經找到了要搜尋的專案 :)
.........
- 要新增專案，您首先必須搜尋樹以找到應放置它的位置。您可以按照上面的步驟進行操作。
- 當您到達在正確分支上沒有子節點的節點時，請在該位置新增新節點。
例如，要新增節點 25...
- 根節點是 50，它大於 25，因此您移至 50 的左子節點。
- 50 的左子節點是 30，它大於 25，因此您移至 30 的左子節點。
- 30 的左子節點是 20，它小於 25，因此您移至 20 的右子節點。
- 20 的右子節點不存在，因此您在該位置新增 25 :)
假設您已經使用上面描述的搜尋技術找到了要刪除的節點。
例如，要刪除 40...
- 只需刪除節點！
- 將要刪除的節點的子節點直接連線到要刪除的節點的父節點。
例如，要刪除 90...
- 刪除 90，然後將 100 設為 50 的子節點。
一種非標準方法是將節點旋轉到選定的子樹中，並嘗試從該子樹中遞迴刪除鍵，直到出現情況 1 或情況 2 為止。這可能會使樹失去平衡，因此隨機選擇向右或向左旋轉可能會有所幫助。
標準方法是選擇左子樹或右子樹，例如右子樹，然後透過從右子樹開始一直向左移動，直到下一個左節點為空，從而獲取右子樹的最左側後代。然後刪除右子樹的這個最左側後代，用它的右子樹（它有一個空的左子樹）來替換它。然後使用這個以前右子樹的最左側後代的內容來替換要刪除的節點的鍵和值，以便它的值現在位於要刪除的節點（右子樹的父節點）中。這仍然可以保持所有節點的鍵排序。示例 Java 程式碼在下面的樹堆示例程式碼中。
以下示例使用標準演算法，即後繼節點是待刪除節點的右子樹中的最左側節點。
例如，要刪除 30
- 要刪除的節點的右節點是 40。
- （從現在開始，我們一直移至左節點，直到沒有另一個節點……）40 的第一個左節點是 35。
- 35 沒有左節點，因此 35 是後繼節點！
- 35 替換了原始右節點的 30，並且包含 35 的節點被刪除，用具有根節點 37 的右子樹來替換它。
- 將待刪除節點右側的子節點直接移至待刪除節點的位置。
- 由於新節點沒有左子節點，因此您可以將待刪除節點的左子樹的根節點連線為它的左子節點。
例如，要刪除 30
- 用後繼節點的內容（40）替換要刪除的內容（30）。
- 刪除後繼節點（內容為 40），用它的右子樹（頭節點內容為 45）來替換它。
這最好用一個例子來解釋。
要刪除 30...
- 將要刪除的內容（30）替換為後繼節點的內容（35）。
- 將後繼節點（35）替換為它的右子樹（37）。因為後繼節點是最左邊的節點，所以沒有左子樹。
private Treap1<K, V>.TreapNode deleteNode(K k, Treap1<K, V>.TreapNode node, Deleted del) {
if (node == null) {
return null;
} else if (k.compareTo(node.k) < 0) {
node.left = deleteNode(k, node.left, del);
} else if (k.compareTo(node.k) > 0) {
node.right = deleteNode(k, node.right, del);
// k.compareTo(node.k) == 0
} else if ( node.left == null ) {
del.success = true;
return node.right;
} else if ( node.right == null) {
del.success = true;
return node.left;
} else if (node.left !=null && node.right != null){
/*
// non-standard method,
// left rotate and all delete on left subtree
TreapNode tmp = node.right;
node.right = node.right.left;
tmp.left = node;
node = tmp;
node.left = deleteNode(k , node.left, del);
*/
// more standard method ? doesn't disturb tree structure as much
// find leftmost descendant of the right child node and replace contents
TreapNode n2 = node.right;
TreapNode previous2 = null;
while (n2.left != null) {
previous2 = n2;
n2 = n2.left;
}
if (previous2 != null) {
previous2.left = n2.right;
//n2 has no parent link, orphaned
} else {
node.right = n2.right;
//n2 has no parent link, orphaned
}
node.k = n2.k;
node.val = n2.val;
del.success = true;
// once n2 out of scope, the orphaned node at n2 will be garbage collected,
}
return node;
}
紅黑樹是一種自平衡樹結構，它為每個節點分配一個顏色。紅黑樹的結構必須遵守一套規則，這些規則規定了不同顏色節點的排列方式。當樹以某種方式修改時，會應用這些規則，導致在插入新節點或刪除舊節點時，某些節點旋轉和重新著色。這保持了紅黑樹的平衡，保證了 O(log n) 的搜尋複雜度。
紅黑樹必須遵守的規則如下：
- 每個節點必須是紅色或黑色。
- 根節點始終是黑色的。
- 樹中的所有葉子節點都是黑色的（葉子節點不包含資料，在大多數程式語言中可以建模為 null 或 nil 引用）。
- 每個紅色節點必須有兩個黑色子節點。
- 從給定節點到其任何後代葉節點的每條路徑必須包含相同數量的黑色節點。
紅黑樹可以建模為 2-3-4 樹，它是 B 樹（見下文）的一個子類。一個黑色節點帶有一個紅色節點可以看作是連結在一起的 3 節點，一個黑色節點帶兩個紅色子節點可以看作是 4 節點。
4 節點會被 拆分，生成兩個節點，並將中間節點變為紅色，這會將中間節點的父節點（沒有紅色子節點）從 2 節點變為 3 節點，並將具有一個紅色子節點的父節點變為 4 節點（但這不會發生在始終是左邊的紅色節點的情況下）。
兩個紅色節點的內聯排列會被 旋轉 成一個具有兩個紅色子節點的父節點，即一個 4 節點，然後會 拆分，如前所述。
A right rotate 'split 4-node' |red
red / \ --> B ---> B
B red/ \red / \
red / \ C A C A
C D / /
D D
Sedgewick 提到的一個最佳化是，所有右插入的紅色節點都會被左旋轉成左紅色節點，因此只有內聯的左紅色節點需要在拆分之前進行右旋轉。Arne Anderson 提出的 AA 樹（見上文），在 1993 年的一篇論文中描述了這種簡化的早期闡述，但他建議使用右傾斜的“紅色標記”，而不是 Sedgewick 建議的左傾斜，但 AA 樹似乎優先於左傾斜的紅黑樹。如果 Linux CFS 排程程式在將來被描述為“基於 AA 的”，這將是一個相當大的衝擊。
總之，紅黑樹是一種檢測對同一側進行兩次插入並使樹在情況變得更糟之前進行平衡的方法。兩次左側插入將被旋轉，兩次右側插入看起來像是兩次左側插入，因為左旋轉會移除右傾斜的紅色節點。兩次對同一個父節點的平衡插入會導致 4 節點拆分而無需旋轉，因此出現了一個問題：紅黑樹是否可以被 a < P < b 形式的單側三元組的序列插入所攻擊，然後是下一個三元組的 P' < a。
以下為 Python 示例程式碼
RED = 1
BLACK = 0
class Node:
def __init__(self, k, v):
# all newly inserted node's are RED
self.color = RED
self.k = k
self.v = v
self.left = None
self.right = None
class RBTree:
def __init__(self):
self.root = None
def insert(self, k, v) :
self.root = self._insert(self.root, k,v)
def _insert(self, n , k, v):
if n is None:
return Node(k,v)
if k < n.k :
n.left = self._insert(n.left, k , v)
elif k > n.k :
n.right = self._insert(n.right, k, v)
if n.right.color is RED:
#always on the left red's
#left rotate
tmp = n.right
n.right = tmp.left
tmp.left = n
n = tmp
#color rotation is actually a swap
tmpcolor = n.color
n.color = n.left.color
n.left.color = tmpcolor
if n.left <> None and n.left.left <> None and n.left.left.color == RED and n.left.color == RED:
# right rotate in-line reds
print "right rotate"
tmp = n.left
n.left = tmp.right
tmp.right = n
n = tmp
#color rotation is actually a swap
tmpcolor = n.color
n.color = n.right.color
n.right.color = tmpcolor
if n.left <> None: print n.left.color, n.color, n.right.color
#no need to test, because after right rotation, will need to split 3-node , as right rotation has
#brought red left grandchild to become left red child, and left red child is now red right child
#so there are two red children.
#if n.left <> None and n.right <> None and n.left.color == RED and n.right.color == RED:
print "split"
n.color = RED
n.left.color = BLACK
n.right.color = BLACK
return n
def find(self, k):
return self._find_rb(k, self.root)
def _find_rb(self, k, n):
if n is None:
return None
if k < n.k:
return self._find_rb( k, n.left)
if k > n. k:
return self._find_rb( k, n.right)
return n.v
def inorder(self):
self.inorder_visit(self.root, "O")
def inorder_visit(self, node,label=""):
if node is None: return
self.inorder_visit(node.left, label+"/L")
print label, "val=", node.v
self.inorder_visit(node.right, label+"/R")
def test1(N):
t = RBTree()
for i in xrange(0,N):
t.insert(i,i)
l = []
t.inorder()
for i in xrange(0,N):
x =t.find(i)
if x <> None:
l.append((x, i) )
print "found", len(l)
if __name__ == "__main__":
import random
test1(100000)
test1(1000)
test1(100)
test1(10)
- 二叉樹的節點有兩個子節點，左子節點及其所有後代節點都小於節點的“值”，右子節點及其所有後代節點都大於節點的“值”，而 B 樹是對此的概括。
- 概括在於，節點不是儲存一個值，而是儲存一個值列表，該列表的長度為 n（n > 2）。n 被選擇以最佳化儲存，以便節點的大小對應於一個塊的大小。這發生在 SSD 驅動器出現之前的時代，但搜尋儲存在 SSD RAM 上的二叉節點仍然比搜尋 SSD RAM 上的塊資料、載入到普通 RAM 和 CPU 快取以及搜尋載入的列表要慢。
- 在列表的開頭，第一個元素的左子節點的值小於第一個元素，其所有子節點也是如此。第一個元素的右邊是一個子節點，它的值大於第一個元素的值，其所有子節點也是如此，但小於第二個元素的值。可以使用歸納法，對於元素 1 和 2 之間的子節點，2 和 3 之間的子節點，以此類推，直到 n-1 和第 n 個節點都是如此。
- 要插入到一個非滿的 B 樹節點中，需要對一個排序的列表進行插入操作。
- 在 B+ 樹中，插入操作只能在葉節點中進行，非葉節點儲存的是相鄰子節點之間分隔值的副本，例如，某個元素的右子節點列表中最左邊的值。
- 當一個列表變得滿時（例如，有 n 個節點），該節點會被“拆分”，這意味著建立兩個新節點並將分隔值傳遞給父節點。
B 樹最初被描述為二叉搜尋樹的概括，其中二叉樹是一個 2 節點 B 樹，2 代表兩個子節點，有一個 2-1 = 1 個鍵用於分隔這兩個子節點。因此，3 節點有兩個值用於分隔 3 個子節點，N 節點有 N 個子節點被 N-1 個鍵分隔。
經典的 B 樹可以具有 N 節點內部節點和空的 2 節點葉節點，或者更方便地，子節點可以是值或指向下一個 N 節點的指標，因此它是一個聯合。
B 樹的主要思想是，首先建立一個根 N 節點，它可以容納 N-1 個條目，但在第 N 個條目時，節點的鍵數量將用完，該節點可以拆分為兩個大小為 N/2 的 N 節點，它們被一個單獨的鍵 K 分隔，該鍵 K 等於右節點的最左鍵，因此任何鍵 K2 大於或等於 K 的條目都將進入右節點，小於 K 的條目都將進入左節點。當根節點拆分時，會建立一個新的根節點，它包含一個鍵以及一個左子節點和一個右子節點。由於有 N 個子節點，但只有 N-1 個條目，因此最左邊的子節點被儲存為一個單獨的指標。如果最左邊的指標拆分，則左半部分將成為新的最左邊的指標，右半部分和分隔鍵將插入條目的開頭。
另一種方法是 B+ 樹，它在資料庫系統中最常用，因為只有葉節點儲存值，而內部節點只儲存鍵和指向其他節點的指標，這限制了資料值的大小，因為指標的大小有限。這通常允許內部節點包含更多條目，從而能夠適應一定大小的塊，例如 4K 是一個常見的物理磁碟塊大小。因此，如果一個 B+ 樹內部節點與物理磁碟塊對齊，那麼由於它沒有被快取在記憶體塊列表中，所以從磁碟讀取一個大索引塊的主要速率限制因素將減少到一個塊讀取。
B+ 樹具有更大的內部節點，因此在理論上比等效的 B 樹更寬且更短，B 樹必須將所有節點都放入給定的物理塊大小中，因此，總的來說，它是一個更快的索引，因為它的扇出更大，並且平均而言到達鍵的高度更低。
顯然，這種扇出非常重要，也可以對塊進行壓縮，以增加在給定底層塊大小中可以容納的條目數量（底層層通常是檔案系統塊）。
大多數資料庫系統使用 B+ 樹演算法，包括 postgresql、mysql、derbydb、firebird、許多 Xbase 索引型別等等。
許多檔案系統也使用 B+ 樹來管理它們的塊佈局（例如，xfs、NTFS 等等）。
Transwiki 提供了一個使用傳統陣列作為鍵列表和值列表的 B+ 樹的 Java 實現。
下面是一個帶有測試驅動程式的 B 樹的示例，以及一個帶有測試驅動程式的 B+ 樹的示例。記憶體/磁碟管理沒有包含在內，但可以在 雜湊記憶體檢查示例 中找到一個可用的駭客示例。
這個 B+ 樹實現是基於 B 樹實現的，它與 transwiki B+ 樹的區別在於，它試圖使用標準 Java 集合庫中已經存在的 SortedMap 和 SortedSet 的語義。
因此，這個 B+ 實現的平面葉塊列表不能包含不包含任何資料的塊，因為排序依賴於條目的第一個鍵，所以需要建立一個葉塊，並使用第一個條目填充它。
package btreemap;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
/** can't work without setting a comparator */
public class BTreeMap<K, V> implements SortedMap<K, V> {
private static final int NODE_SIZE = 100;
@Override
public Comparator<? super K> comparator() {
// TODO Auto-generated method stub
return comparator;
}
Comparator< ? super K> defaultComparator = new
Comparator< K>() {
@Override
public int compare(K o1, K o2) {
// TODO Auto-generated method stub
Comparable c1 = (Comparable)o1;
Comparable c2 = (Comparable)o2;
return c1.compareTo(c2);
}
};
Comparator<? super K> comparator = defaultComparator;
BTBlock<K, V> root = new BTBlock<K, V>(NODE_SIZE, comparator);
/**
*
* @param comparator
* - this is mandatory for the tree to work
*/
public void setComparator(Comparator<? super K> comparator) {
this.comparator = comparator;
root = new BTBlock<K, V>(NODE_SIZE, comparator);
}
/**
*
*
*
* @param <K>
* @param <V>
* the entry is associated with a right child block.
*
*/
static class BlockEntry<K, V> {
K k;
V v;
BTBlock left;
BlockEntry() {
}
BlockEntry(K k, V v) {
left = null;
this.k = k;
this.v = v;
}
}
/**
*
* - this represents the result of splitting a full block into
* a left block, and a right block, and a median key, the right
* block and the median key held in a BlockEntry structure as above.
* @param <K>
* @param <V>
* @param <V>g
*/
static class SplitRootEntry<K, V> {
BTBlock<K, V> right;
BlockEntry<K, V> entry;
SplitRootEntry(BlockEntry<K, V> entry, BTBlock<K, V> right) {
this.right = right;
this.entry = entry;
}
SplitRootEntry() {
super();
}
}
/**
* this is used to return a result of a possible split , during recursive
* calling.
*
*
*
* @param <K>
* @param <V>
*/
static class resultAndSplit<K, V> {
/**
* null , if there is no split.
*/
SplitRootEntry<K, V> splitNode;
V v;
resultAndSplit(V v) {
this.v = v;
}
resultAndSplit(SplitRootEntry<K, V> entry, V v) {
this.v = v;
this.splitNode = entry;
}
}
/**
* used to represent the insertion point after searching a block if compare
* is zero, then a match was found, and pos is the insertion entry if
* compare < 0 and pos == 0 , then the search ended up less than the
* leftmost entry else compare > 0 , and the search will be to the immediate
* right of pos.
*
*
*
*/
static class PosAndCompare {
int pos = 0;
int compare = 0;
}
static class BTBlock<K, V> {
List<BlockEntry<K, V>> entries;
BTBlock<K, V> rightBlock = null;
private int maxSz = 0;
Comparator<? super K> comparator;
Comparator<? super K> comparator() {
return comparator;
}
public BTBlock(int size, Comparator<? super K> c) {
entries = new ArrayList<BlockEntry<K, V>>();
maxSz = size;
this.comparator = c;
}
/**
* PosAndCompare usage: if compare is zero, then a match was found, and
* pos is the insertion entry if compare < 0 and pos == 0 , then the
* search ended up less than the leftmost entry else compare > 0 , and
* the search will be to the immediate right of pos.
*
*
*
*/
// private void blockSearch(K k, PosAndCompare pc) {
// for (int i = 0; i < entries.size(); ++i) {
// pc.compare = comparator.compare(k, entries.get(i).k);
// if (pc.compare == 0) {
// pc.pos = i;
// return;
// }
// if (pc.compare < 0 && i == 0) {
// pc.pos = 0;
// return;
// }
//
// if (pc.compare < 0) {
// pc.pos = i - 1;
// pc.compare = 1;
// return;
// }
//
// }
// pc.pos = entries.size() - 1;
// pc.compare = 1;
//
// // binary search, it's hard to get it right !
// // int left = 0;
// // int right = entries.size();
// //
// // while (left <= right && left < entries.size()) {
// // // pc.pos = (right - left) / 2 + left;
// // pc.pos = (left + right) / 2;
// // pc.compare = comparator().compare(k, entries.get(pc.pos).k);
// // if (pc.compare < 0) {
// // right = pc.pos - 1;
// // } else if (pc.compare > 0) {
// // left = pc.pos + 1;
// // } else {
// // return;
// // }
// // }
// //
// // BlockEntry<K, V> e = new BlockEntry<K, V>(k, null);
// // pc.pos = Collections.binarySearch(entries, e, cmp);
//
// }
Comparator<BlockEntry<K, V>> cmp = new Comparator<BlockEntry<K, V>>() {
@Override
public int compare(BlockEntry<K, V> o1, BlockEntry<K, V> o2) {
// TODO Auto-generated method stub
return comparator.compare(o1.k, o2.k);
}
};
resultAndSplit<K, V> put(K k, V v) {
V v2;
if (entries.size() == 0) {
entries.add(new BlockEntry<K, V>(k, v));
return new resultAndSplit<K, V>(v);
} else {
// PosAndCompare pc = new PosAndCompare();
BlockEntry<K, V> e = new BlockEntry<K, V>(k, v);
int res = Collections.binarySearch(entries, e, cmp);
int index = -res - 1;
// blockSearch(k, pc);
// a match
if (res >= 0) {
v2 = entries.get(res).v;
entries.get(res).v = v;
return new resultAndSplit<K, V>(v2);
}
// follow leftBlock if search is to left of first entry
if (index == entries.size() && rightBlock != null) {
resultAndSplit<K, V> result = rightBlock.put(k, v);
if (result.splitNode != null) {
rightBlock = result.splitNode.right;
entries.add(result.splitNode.entry);
}
} else if (index == entries.size() && rightBlock == null
&& entries.size() == maxSz) {
rightBlock = new BTBlock<K, V>(this.maxSz, comparator);
resultAndSplit<K, V> result = rightBlock.put(k, v);
} else if (index < entries.size()
&& entries.get(index).left != null) {
// follow right block if it exists
resultAndSplit<K, V> result = entries.get(index).left.put(
k, v);
if (result.splitNode != null) {
entries.get(index).left = result.splitNode.right;
// add to the left
entries.add(index, result.splitNode.entry);
}
} else {
// add to the left
entries.add(index, e);
}
// check if overflowed block , split if it has.
if (entries.size() > maxSz) {
int mid = entries.size() / 2;
// copy right half to new entries list.
List<BlockEntry<K, V>> leftEntries = new ArrayList<BlockEntry<K, V>>();
for (int i = 0; i < mid; ++i) {
leftEntries.add(entries.get(i));
}
BlockEntry<K, V> centreEntry = entries.get(mid);
BTBlock<K, V> leftBlock = new BTBlock<K, V>(maxSz,
comparator);
leftBlock.entries = leftEntries;
// the median entry's left block is the new left block's
// leftmost block
leftBlock.rightBlock = centreEntry.left;
// the new right block becomes the right block
centreEntry.left = leftBlock;
// reduce the old block's entries into its left half of
// entries.
ArrayList<BlockEntry<K, V>> newEntries = new ArrayList<BlockEntry<K, V>>();
for (int i = mid + 1; i < entries.size(); ++i)
newEntries.add(entries.get(i));
this.entries = newEntries;
// create a return object, with the reduced old block as the
// left block
// and the median entry with the new right block attached
SplitRootEntry<K, V> split = new SplitRootEntry<K, V>(
centreEntry, this);
// the keyed value didn't exist before , so null
return new resultAndSplit<K, V>(split, null);
}
return new resultAndSplit<K, V>(v);
}
}
V get(K k) {
if (entries.size() == 0)
return null;
BlockEntry<K, V> e = new BlockEntry<K, V>(k, null);
int res = Collections.binarySearch(entries, e, cmp);
int index = -res - 1;
if (res >= 0) {
return entries.get(res).v;
}
if (index == entries.size() && rightBlock != null) {
return rightBlock.get(k);
} else if (index < entries.size()
&& entries.get(index).left != null) {
return (V) entries.get(index).left.get(k);
} else
return null;
}
void getRange(SortedMap map, K k1, K k2) {
BlockEntry<K, V> e = new BlockEntry<K, V>(k1, null);
int res = Collections.binarySearch(entries, e, cmp);
int index = -res - 1;
BlockEntry<K, V> e2 = new BlockEntry<K, V>(k2, null);
int res2 = Collections.binarySearch(entries, e2, cmp);
int index2 = -res2 - 1;
int from = res >= 0 ? res : index;
int to = res2 >= 0 ? res2 : index2;
for (int i = from; i <= to; ++i) {
if (i < entries.size() && (i > from || res < 0)
&& entries.get(i).left != null) {
entries.get(i).left.getRange(map, k1, k2);
// if (pc2.pos == pc.pos)
// break;
}
if (i < to || res2 >= 0)
map.put(entries.get(i).k, entries.get(i).v);
if (i == entries.size() && rightBlock != null) {
rightBlock.getRange(map, k1, k2);
}
}
}
K headKey() {
if (rightBlock != null) {
return rightBlock.headKey();
}
return entries.get(0).k;
}
K tailKey() {
int i = entries.size() - 1;
if (entries.get(i).left != null) {
return (K) entries.get(i).left.tailKey();
}
return entries.get(i).k;
}
void show(int n) {
showTabs(n);
for (int i = 0; i < entries.size(); ++i) {
BlockEntry<K, V> e = entries.get(i);
System.err.print("#" + i + ":(" + e.k + ":" + e.v + ") ");
}
System.err.println();
showTabs(n);
if (rightBlock != null) {
System.err.print("Left Block\n");
rightBlock.show(n + 1);
} else {
System.err.println("No Left Block");
}
for (int i = 0; i < entries.size(); ++i) {
BlockEntry<K, V> e = entries.get(i);
showTabs(n);
if (e.left != null) {
System.err.println("block right of #" + i);
e.left.show(n + 1);
} else {
System.err.println("No block right of #" + i);
}
}
showTabs(n);
System.err.println("End of Block Info\n\n");
}
private void showTabs(int n) {
// TODO Auto-generated method stub
for (int i = 0; i < n; ++i) {
System.err.print(" ");
}
}
}
@Override
public SortedMap<K, V> subMap(K fromKey, K toKey) {
TreeMap<K, V> map = new TreeMap<K, V>();
root.getRange(map, fromKey, toKey);
return map;
}
@Override
public SortedMap<K, V> headMap(K toKey) {
// TODO Auto-generated method stub
return subMap(root.headKey(), toKey);
};
@Override
public SortedMap<K, V> tailMap(K fromKey) {
// TODO Auto-generated method stub
return subMap(fromKey, root.tailKey());
}
@Override
public K firstKey() {
// TODO Auto-generated method stub
return root.headKey();
}
@Override
public K lastKey() {
// TODO Auto-generated method stub
return root.tailKey();
}
@Override
public int size() {
// TODO Auto-generated method stub
return 0;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}
@Override
public boolean containsKey(Object key) {
// TODO Auto-generated method stub
return get(key) != null;
}
@Override
public boolean containsValue(Object value) {
// TODO Auto-generated method stub
return false;
}
@Override
public V get(Object key) {
// TODO Auto-generated method stub
return root.get((K) key);
}
@Override
public V put(K key, V value) {
resultAndSplit<K, V> b = root.put(key, value);
if (b.splitNode != null) {
root = new BTBlock<K, V>(root.maxSz, root.comparator);
root.rightBlock = b.splitNode.right;
root.entries.add(b.splitNode.entry);
}
return b.v;
}
@Override
public V remove(Object key) {
// TODO Auto-generated method stub
return null;
}
@Override
public void putAll(Map<? extends K, ? extends V> m) {
// TODO Auto-generated method stub
}
@Override
public void clear() {
// TODO Auto-generated method stub
}
@Override
public Set<K> keySet() {
// TODO Auto-generated method stub
return null;
}
@Override
public Collection<V> values() {
// TODO Auto-generated method stub
return null;
}
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
// TODO Auto-generated method stub
return null;
}
}
package btreemap;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
public class TestBtree {
private static final int N = 50000;
public static void main(String[] args) {
BTreeMap<Integer, Integer> map = new BTreeMap<Integer , Integer>();
Random r = new Random();
ArrayList<Integer> t = new ArrayList<Integer>();
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o1.intValue() - o2.intValue();
}
};
map.setComparator(comparator);
List<Integer> testVals = new ArrayList<Integer>();
for (int i =0 ; i < N ; ++i) {
testVals.add(i);
}
for (int i = 0; i < N; ++i ) {
int x = r.nextInt(testVals.size());
x = testVals.remove(x);
//int x=i;
t.add(x);
map.put(x, x);
}
System.err.println("output " + N + " vals");
map.root.show(0);
for (int i = 0; i < N; ++i) {
int x = t.get(i);
if ( x != map.get(x))
System.err.println("Expecting " + x + " got " + map.get(x));
}
System.err.println("Checked " + N + " entries");
}
}
實驗包括計時執行（例如，time java -cp . btreemap.BPlusTreeTest1），使用外部塊大小 + 1 大小的葉塊大小，這樣它基本上只是底層的條目 TreeMap，與使用 400 個內部節點大小和 200 個外部節點大小相比。其他實驗包括使用 SkipListMap 而不是 TreeMap。
package btreemap;
import java.util.Collection;
import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;
/**
* a B+ tree, where leaf blocks contain key-value pairs and
* internal blocks have keyed entries pointing to other internal blocks
* or leaf blocks whose keys are greater than or equal to the associated key.
*
* @author syan
*
* @param <K> key type implements Comparable
* @param <V> value type
*/
public class BPlusTreeMap<K, V> implements SortedMap<K, V> {
private int maxInternalBlockSize;
BPlusAnyBlock<K, V> root;
private int maxExternalSize;
BPlusTreeMap(int maxInternalSize, int maxExternalSize) {
this.maxInternalBlockSize = maxInternalSize;
this.maxExternalSize = maxExternalSize;
}
static class SplitOrValue<K, V> {
V v;
K k;
BPlusAnyBlock<K, V> left, right;
boolean split;
public boolean isSplit() {
return split;
}
public void setSplit(boolean split) {
this.split = split;
}
public SplitOrValue(V value) {
v = value;
setSplit(false);
}
public SplitOrValue(BPlusAnyBlock<K, V> left2,
BPlusAnyBlock<K, V> bPlusBlock) {
left = left2;
right = bPlusBlock;
k = right.firstKey();
setSplit(true);
// System.err.printf("\n\n** split occured %s**\n\n", bPlusBlock
// .getClass().getSimpleName());
}
}
static abstract class BPlusAnyBlock<K, V> {
public abstract SplitOrValue<K, V> put(K k, V v);
abstract SplitOrValue<K, V> splitBlock();
public abstract V get(K k);
public abstract boolean isEmpty();
public abstract K firstKey();
}
SortedSet<BPlusLeafBlock<K, V>> blockList = getLeafBlockSet();
SortedSet<BPlusLeafBlock<K, V>> getLeafBlockSet() {
// return new ConcurrentSkipListSet<BPlusLeafBlock<K, V>>();
return new TreeSet<BPlusLeafBlock<K, V>>();
}
static class BPlusLeafBlock<K, V> extends BPlusAnyBlock<K, V> implements
Comparable<BPlusLeafBlock<K, V>> {
SortedMap<K, V> entries = getEntryCollection();
static <K, V> SortedMap<K, V> getEntryCollection() {
return new TreeMap<K, V>();
}
int maxSize;
private BPlusTreeMap<K, V> owner;
public boolean isEmpty() {
return entries.isEmpty();
}
public BPlusLeafBlock(BPlusTreeMap<K, V> bPlusTreeMap,
SortedMap<K, V> rightEntries) {
this.owner = bPlusTreeMap;
maxSize = owner.maxExternalSize;
entries = rightEntries;
}
public SplitOrValue<K, V> put(K k, V v) {
V v2 = entries.put(k, v);
if (entries.size() >= maxSize)
return splitBlock();
else
return new SplitOrValue<K, V>(v2);
}
public SplitOrValue<K, V> splitBlock() {
SortedMap<K, V> leftEntries = getEntryCollection();
SortedMap<K, V> rightEntries = getEntryCollection();
int i = 0;
for (Entry<K, V> e : entries.entrySet()) {
// System.out.println(this.getClass().getSimpleName() +
// " split entry " + e.getKey());
if (++i <= maxSize / 2)
leftEntries.put(e.getKey(), e.getValue());
else
rightEntries.put(e.getKey(), e.getValue());
}
BPlusLeafBlock<K, V> right = createBlock(rightEntries);
// System.out.println("finished block split");
// System.out.println("\nleft block");
// for (K ik : leftEntries.keySet()) {
// System.out.print(ik + " ");
// }
// System.out.println("\nright block");
// for (K ik : right.entries.keySet()) {
// System.out.print(ik + " ");
// }
// System.out.println("\n");
this.entries = leftEntries;
return new SplitOrValue<K, V>(this, right);
}
private BPlusLeafBlock<K, V> createBlock(SortedMap<K, V> rightEntries) {
return owner.createLeafBlock(rightEntries);
}
@Override
public V get(K k) {
return entries.get(k);
}
@Override
public int compareTo(BPlusLeafBlock<K, V> o) {
return ((Comparable<K>) entries.firstKey()).compareTo(o.entries
.firstKey());
}
@Override
public K firstKey() {
return entries.firstKey();
}
}
static class BPlusBranchBlock<K, V> extends BPlusAnyBlock<K, V> {
SortedMap<K, BPlusAnyBlock<K, V>> entries = createInternalBlockEntries();
int maxSize;
private BPlusAnyBlock<K, V> left;
public boolean isEmpty() {
return entries.isEmpty();
}
public BPlusBranchBlock(int maxSize2) {
this.maxSize = maxSize2;
}
public SplitOrValue<K, V> put(K k, V v) {
BPlusAnyBlock<K, V> b = getBlock(k);
SplitOrValue<K, V> sv = b.put(k, v);
if (sv.isSplit()) {
entries.put(sv.k, sv.right);
if (entries.size() >= maxSize)
sv = splitBlock();
else
sv = new SplitOrValue<K, V>(null);
}
return sv;
}
BPlusAnyBlock<K, V> getBlock(K k) {
assert (entries.size() > 0);
BPlusAnyBlock<K, V> b = entries.get(k);
if (b == null) {
// headMap returns less than k
SortedMap<K, BPlusAnyBlock<K, V>> head = entries.headMap(k);
if (head.isEmpty()) {
b = left;
// System.out.println("for key " + k
// + " getting from leftmost block");
// showEntries();
} else {
b = entries.get(head.lastKey());
// System.out.println("for key " + k
// + " getting from block with key " + head.lastKey());
// showEntries();
}
}
assert (b != null);
return b;
}
public void showEntries() {
System.out.print("entries = ");
for (K k : entries.keySet()) {
System.out.print(k + " ");
}
System.out.println();
}
public SplitOrValue<K, V> splitBlock() {
Set<Entry<K, BPlusAnyBlock<K, V>>> ee = entries.entrySet();
int i = 0;
BPlusBranchBlock<K, V> right = new BPlusBranchBlock<K, V>(maxSize);
SortedMap<K, BPlusAnyBlock<K, V>> leftEntries = createInternalBlockEntries();
for (Entry<K, BPlusAnyBlock<K, V>> e : ee) {
// System.out.print("split check " + e.getKey() + ":"
// );
if (++i <= maxSize / 2)
leftEntries.put(e.getKey(), e.getValue());
else
right.entries.put(e.getKey(), e.getValue());
}
// System.out.println("\n");
this.entries = leftEntries;
return new SplitOrValue<K, V>(this, right);
}
private SortedMap<K, BPlusAnyBlock<K, V>> createInternalBlockEntries() {
return new TreeMap<K, BPlusAnyBlock<K, V>>();
}
@Override
public V get(K k) {
BPlusAnyBlock<K, V> b = getBlock(k);
return b.get(k);
}
@Override
public K firstKey() {
return entries.firstKey();
}
}
@Override
public SortedMap<K, V> subMap(K fromKey, K toKey) {
TreeMap<K, V> map = new TreeMap<K, V>();
BPlusLeafBlock<K, V> b1 = getLeafBlock(fromKey);
BPlusLeafBlock<K, V> b2 = getLeafBlock(toKey);
SortedSet<BPlusLeafBlock<K, V>> range = blockList.subSet(b1, b2);
for (BPlusLeafBlock<K, V> b : range) {
SortedMap<K, V> m = b.entries.subMap(fromKey, toKey);
map.putAll(m);
}
return map;
}
private BPlusLeafBlock<K, V> getLeafBlock(K key) {
BPlusAnyBlock<K, V> b1;
b1 = root;
while (b1 instanceof BPlusBranchBlock<?, ?>) {
b1 = ((BPlusBranchBlock<K, V>) b1).getBlock(key);
}
return (BPlusLeafBlock<K, V>) b1;
}
public BPlusLeafBlock<K, V> createLeafBlock(SortedMap<K, V> rightEntries) {
BPlusLeafBlock<K, V> b = new BPlusLeafBlock<K, V>(this, rightEntries);
blockList.add(b);
return b;
}
@Override
public SortedMap<K, V> headMap(K toKey) {
return subMap(firstKey(), toKey);
};
@Override
public SortedMap<K, V> tailMap(K fromKey) {
return subMap(fromKey, lastKey());
}
@Override
public K firstKey() {
return blockList.first().entries.firstKey();
}
@Override
public K lastKey() {
return blockList.last().entries.lastKey();
}
@Override
public int size() {
return (int) getLongSize();
}
private long getLongSize() {
long i = 0;
for (BPlusLeafBlock<K, V> b : blockList) {
i += b.entries.size();
}
return i;
}
@Override
public boolean isEmpty() {
return root.isEmpty();
}
@Override
public boolean containsKey(Object key) {
return get(key) != null;
}
@Override
public boolean containsValue(Object value) {
return false;
}
@Override
public V get(Object key) {
return (V) root.get((K) key);
}
@Override
public V put(K key, V value) {
if (root == null) {
SortedMap<K, V> entries = BPlusLeafBlock.getEntryCollection();
entries.put(key, value);
root = createLeafBlock(entries);
return null;
}
SplitOrValue<K, V> result = root.put(key, value);
if (result.isSplit()) {
BPlusBranchBlock<K, V> root = new BPlusBranchBlock<K, V>(
maxInternalBlockSize);
root.left = result.left;
root.entries.put(result.k, result.right);
this.root = root;
}
return result.v;
}
@Override
public V remove(Object key) {
return null;
}
@Override
public void putAll(Map<? extends K, ? extends V> m) {
for (K k : m.keySet()) {
put(k, m.get(k));
}
}
@Override
public void clear() {
}
@Override
public Set<K> keySet() {
TreeSet<K> kk = new TreeSet<K>();
for (BPlusLeafBlock<K, V> b : blockList) {
kk.addAll(b.entries.keySet());
}
return kk;
}
@Override
public Collection<V> values() {
// TODO Auto-generated method stub
return null;
}
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
// TODO Auto-generated method stub
return null;
}
@Override
public Comparator<? super K> comparator() {
// TODO Auto-generated method stub
return null;
}
public void showLeaves() {
for (BPlusLeafBlock<K, V> b : blockList) {
System.out.println("Block");
for (Entry<K, V> e : b.entries.entrySet()) {
System.out.print(e.getKey() + ":" + e.getValue() + " ");
}
System.out.println();
}
}
}
package btreemap;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
/** driver program to test B+ tree */
public class BPlusTreeTest1 {
private static final int N = 1200000;
public static void main(String[] args) {
BPlusTreeMap<Integer, Integer> map = new BPlusTreeMap<Integer, Integer>(
400, 200 );// 5000002);
Random r = new Random();
ArrayList<Integer> t = new ArrayList<Integer>();
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o1.intValue() - o2.intValue();
}
};
List<Integer> testVals = new ArrayList<Integer>();
for (int i = 0; i < N; ++i) {
testVals.add(i);
}
for (int i = 0; i < N; ++i) {
int x = r.nextInt(N);
int z = testVals.set(x, testVals.get(0));
testVals.set(0, z);
}
for (int i = 0; i < N; ++i) {
map.put(testVals.get(i), testVals.get(i));
showProgress("put", testVals, i);
}
System.err.println("output " + N + " vals");
try {
for (int i = 0; i < N; ++i) {
showProgress("get", testVals, i);
int x = testVals.get(i);
if (x != map.get(x))
System.err.println("Expecting " + x + " got " + map.get(x));
}
System.err.println("\nChecked " + N + " entries");
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
map.showLeaves();
}
}
private static void showProgress(String label, List<Integer> testVals, int i) {
if (i % (N / 1000) == 0) {
System.out.printf("%s %d:%d; ", label, i, testVals.get(i));
if (i % (N / 10100) == 0)
System.out.println();
}
}
}
二叉樹的不變性是，相對於插入鍵，左小於右。例如，對於一個有序的鍵，ord(L) < ord(R)。但是，這並不能決定節點之間的關係，左旋轉和右旋轉不會影響上述情況。因此，可以施加另一個順序。如果順序是隨機的，它很可能抵消普通二叉樹的任何傾斜，例如，當按順序插入一個已經排序的輸入時。
以下是一個 Java 示例實現，包括一個普通二叉樹刪除程式碼示例。
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;
public class Treap1<K extends Comparable<K>, V> {
public Treap1(boolean test) {
this.test = test;
}
public Treap1() {}
boolean test = false;
static Random random = new Random(System.currentTimeMillis());
class TreapNode {
int priority = 0;
K k;
V val;
TreapNode left, right;
public TreapNode() {
if (!test) {
priority = random.nextInt();
}
}
}
TreapNode root = null;
void insert(K k, V val) {
root = insert(k, val, root);
}
TreapNode insert(K k, V val, TreapNode node) {
TreapNode node2 = new TreapNode();
node2.k = k;
node2.val = val;
if (node == null) {
node = node2;
} else if (k.compareTo(node.k) < 0) {
node.left = insert(k, val, node.left);
} else {
node.right = insert(k, val, node.right);
}
if (node.left != null && node.left.priority > node.priority) {
// left rotate
TreapNode tmp = node.left;
node.left = node.left.right;
tmp.right = node;
node = tmp;
} else if (node.right != null && node.right.priority > node.priority) {
// right rotate
TreapNode tmp = node.right;
node.right = node.right.left;
tmp.left = node;
node = tmp;
}
return node;
}
V find(K k) {
return findNode(k, root);
}
private V findNode(K k, Treap1<K, V>.TreapNode node) {
if (node == null)
return null;
if (k.compareTo(node.k) < 0) {
return findNode(k, node.left);
} else if (k.compareTo(node.k) > 0) {
return findNode(k, node.right);
} else {
return node.val;
}
}
static class Deleted {
boolean success = false;
}
boolean delete(K k) {
Deleted del = new Deleted();
root = deleteNode(k, root, del);
return del.success;
}
private Treap1<K, V>.TreapNode deleteNode(K k, Treap1<K, V>.TreapNode node, Deleted del) {
if (node == null) {
return null;
} else if (k.compareTo(node.k) < 0) {
node.left = deleteNode(k, node.left, del) ;
} else if (k.compareTo(node.k) > 0) {
node.right = deleteNode(k, node.right, del);
// k.compareTo(node.k) == 0
} else if ( node.left == null ) {
del.success = true;
return node.right;
} else if ( node.right == null) {
del.success = true;
return node.left;
} else if (node.left !=null && node.right != null){
/*
// left rotate and all delete on left subtree
TreapNode tmp = node.right;
node.right = node.right.left;
tmp.left = node;
node = tmp;
node.left = deleteNode(k , node.left, del);
*/
// more standard method ? doesn't disturb tree structure as much
// find leftmost descendant of the right child node and replace contents
TreapNode n2 = node.right;
TreapNode previous2 = null;
while (n2.left != null) {
previous2 = n2;
n2 = n2.left;
}
if (previous2 != null) {
previous2.left = n2.right;
//n2 has no parent link, orphaned
} else {
node.right = n2.right;
//n2 has no parent link, orphaned
}
node.k = n2.k;
node.val = n2.val;
del.success = true;
// once n2 out of scope, the orphaned node at n2 will be garbage collected,
}
return node;
}
public static void main(String[] args) {
LinkedList<Integer> dat = new LinkedList<Integer>();
for (int i = 0; i < 15000; ++i) {
dat.add(i);
}
testNumbers(dat, true); // no random priority balancing
testNumbers(dat, false);
}
private static void testNumbers(LinkedList<Integer> dat,
boolean test) {
Treap1<Integer, Integer> treap = new Treap1<>(test);
for (Integer integer : dat) {
treap.insert(integer, integer);
}
long t1 = System.currentTimeMillis();
Iterator<Integer> desc = dat.iterator();
int found = 0;
while (desc.hasNext()) {
Integer j = desc.next();
Integer i = treap.find(j);
if (j.equals(i)) {
++found;
}
}
long t2 = System.currentTimeMillis();
System.out.println("found = " + found + " in " + (t2 - t1));
System.out.println("test delete");
int deleted = 0;
for (Integer integer : dat) {
if (treap.delete(integer))
++deleted;
}
System.out.println("Deleted = " + deleted);
}
}
- William Ford 和 William Tapp。使用STL的C++資料結構。第 2 版。新澤西州上薩德爾河：普倫蒂斯·霍爾，2002 年。
以下是堆的一些定義
堆是一個數組，其中存在父子關係，子節點的索引是父節點索引的 2 倍或 2 倍加 1，子節點在父節點之後有一個順序，這由堆的客戶端程式注入的某種具體排序方案決定。維護排序不變式在堆發生變化後至關重要。一些人（Sedgewick 和 Wayne）創造了“上浮”和“下沉”這兩個術語，其中維護不變式包括一個違反不變式的專案向上浮動到排序較低的子節點之上，然後下沉到排序較高的子節點之下，因為可能存在兩個子節點，因此一個專案可以浮動到排序較低的子節點之上，而另一個子節點的排序仍然更高。
堆是一種高效的半排序資料結構，用於儲存可排序資料的集合。最小堆支援兩種操作
INSERT(heap, element) element REMOVE_MIN(heap)
（我們討論最小堆，但最小堆和最大堆之間沒有真正區別，除了比較的解釋方式。）
本章將專門討論二叉堆，儘管存在不同型別的堆。在大多數情況下，術語二叉堆和堆可以互換使用。堆可以看作是一棵具有父節點和子節點的樹。堆和二叉樹之間的主要區別在於堆屬性。為了使一種資料結構被認為是堆，它必須滿足以下條件（堆屬性）
- 如果A和B是堆中的元素，並且B是A的子節點，那麼 key(A) ≤ key(B)。
（此屬性適用於最小堆。最大堆的比較將相反）。這意味著最小鍵將始終保留在頂部，而更大的值將位於其下方。由於這個事實，堆用於實現優先順序佇列，這允許快速訪問優先順序最高的專案。以下是一個最小堆的示例
堆是用一個從 1 到 N 索引的陣列實現的，其中 N 是堆中元素的數量。
在任何時候，堆都必須滿足堆屬性
array[n] <= array[2*n] // parent element <= left child
和
array[n] <= array[2*n+1] // parent element <= right child
只要索引在陣列邊界內。
我們將證明array[1]是堆中的最小元素。我們透過觀察如果其他元素小於第一個元素，則會產生矛盾來證明這一點。假設array[i]是第一個最小值的例項，其中對於所有j < i，array[j] > array[i]，並且i >= 2。但是根據堆不變式陣列，array[floor(i/2)] <= array[i]：這是一個矛盾。
因此，很容易計算MIN(heap)
MIN(heap)
return heap.array[1];
要移除最小元素，我們必須調整堆以填充heap.array[1]。這個過程被稱為滲透。基本上，我們將空洞從節點 i 移動到節點2i或2i+1。如果我們選擇這兩個節點中的最小值，則堆不變式將得到維護；假設array[2i] < array[2i+1]。然後array[2i]將被移動到array[i]，在2i處留下一個空洞，但是移動後array[i] < array[2i+1]，因此堆不變式得到維護。在某些情況下，2i+1將超出陣列邊界，我們被迫滲透2i。在其他情況下，2i也在邊界之外：在這種情況下，我們已經完成。
因此，以下是最小堆的移除演算法
#define LEFT(i) (2*i)
#define RIGHT(i) (2*i + 1)
REMOVE_MIN(heap)
{
savemin=arr[1];
arr[1]=arr[--heapsize];
i=1;
while(i<heapsize){
minidx=i;
if(LEFT(i)<heapsize && arr[LEFT(i)] < arr[minidx])
minidx=LEFT(i);
if(RIGHT(i)<heapsize && arr[RIGHT(i)] < arr[minidx])
minidx=RIGHT(i);
if(minidx!=i){
swap(arr[i],arr[minidx]);
i=minidx;
}
else
break;
}
}
為什麼這有效？
If there is only 1 element ,heapsize becomes 0, nothing in the array is valid. If there are 2 elements , one min and other max, you replace min with max. If there are 3 or more elements say n, you replace 0th element with n-1th element. The heap property is destroyed. Choose the 2 children of root and check which is the minimum. Choose the minimum between them, swap it. Now subtree with swapped child is loose heap property. If no violations break.
INSERT 存在類似的策略：只需將元素附加到陣列，然後透過交換修復堆不變式。例如，如果我們剛剛附加了元素 N，那麼唯一可能的不變式違反涉及該元素，特別是如果，那麼這兩個元素必須交換，現在唯一可能的不變式違反是在…之間
![{\displaystyle array[floor(N/2)]>array[N]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24c556c36e19d6cdca1424cc3846013f01027bb6)
array[floor(N/4)] and array[floor(N/2)]
我們繼續迭代，直到 N=1 或直到不變式得到滿足。
INSERT(heap, element)
append(heap.array, element)
i = heap.array.length
while (i > 1)
{
if (heap.array[i/2] <= heap.array[i])
break;
swap(heap.array[i/2], heap.array[i]);
i /= 2;
}
Merge-heap: it would take two max/min heap and merge them and return a single heap. O(n) time. Make-heap: it would also be nice to describe the O(n) make-heap operation Heap sort: the structure can actually be used to efficiently sort arrays
Make-heap 將使用一個名為 heapify 的函式
//Element is a data structure//
Make-heap(Element Arr[],int size)
{
for(j=size/2;j>0;j--)
{
Heapify(Arr,size,j);
}
}
Heapify(Element Arr[],int size,int t)
{
L=2*t;
R=2*t+1;
if(L<size )
{
mix=minindex(Arr,L,t);
if(R<=size)
mix=minindex(Arr,R,mix);
}
else
mix=t;
if(mix!=t)
{
swap(mix,t);
Heapify(Arr,size,mix);
}
}
minindex 返回較小元素的索引
在 2009 年，OzSort 贏得了較小的排序基準測試，它有一篇論文清晰地描述瞭如何使用優先順序堆作為排序機器來生成大型（內部）排序部分的合併部分。如果一個排序部分佔用 M 個記憶體，排序問題是 k x M 大小，那麼每次取 k 個部分中每個部分大小為 M/k 的連續部分，這樣它們就適合 M 個記憶體（k * M/k = M），並從 k 個部分的每個部分中取第一個元素來建立一個 k 大小的優先順序佇列，當頂部元素被移除並寫入輸出緩衝區時，從相應的部分取下一個元素。這意味著元素可能需要與它們所屬部分的標籤相關聯。當一個 M/k 大小的部分用完時，從磁碟上儲存的原始排序部分中載入下一個 M/k 大小的迷你部分。繼續執行，直到磁碟上 k 個部分中的所有迷你部分都已用盡。
（作為管道以填補磁碟操作延遲的示例，存在兩個輸出緩衝區，因此當一個輸出緩衝區已滿時，一個緩衝區寫入磁碟，而另一個緩衝區被填充。）
這篇論文表明，優先順序堆比二叉樹更直接，因為元素作為 k 路合併的排隊機制不斷被刪除和新增，並且在對超過內部記憶體儲存的大型資料集進行排序時具有實際應用價值。
一個圖是一個結構，它包含一組頂點和一組邊。邊是一對頂點。這兩個頂點稱為邊的端點。圖在計算機科學中無處不在。它們用於對現實世界系統進行建模，例如網際網路（每個節點代表一個路由器，每條邊代表路由器之間的連線）；航空連線（每個節點是一個機場，每條邊是航班）；或城市道路網路（每個節點代表一個交叉路口，每條邊代表一個街區）。計算機圖形中的線框圖是圖的另一個例子。
圖可以是無向的，也可以是有向的。直觀地說，無向邊模擬其端點之間的“雙向”或“雙工”連線，而有向邊是一路連線，通常繪製為箭頭。有向邊通常稱為弧。在數學上，無向邊是一對無序頂點，弧是一對有序頂點。例如，道路網路可以建模為有向圖，其中單行道由端點之間相應方向上的箭頭表示，雙行道由一對平行有向邊表示，在端點之間兩個方向上都走。你可能會問，為什麼不使用單個無向邊來表示雙行道。從理論上講，這沒有問題，但從實際程式設計的角度來看，堅持使用所有有向邊或所有無向邊通常更簡單、更不易出錯。
一個無向圖最多可以有條邊（每對無序頂點一條），而有向圖最多可以有條邊（每對有序頂點一條）。如果圖的邊數遠少於這個數（通常為條邊），則稱為稀疏圖；如果圖的邊數接近條邊，則稱為稠密圖。多重圖可以在同一對頂點之間擁有多條邊。例如，如果要對航空航班進行建模，則兩個城市之間可能存在多個航班，這些航班在一天中的不同時間發生。
圖中的路徑是一系列頂點，使得相鄰頂點之間存在邊或弧。如果，則該路徑稱為迴路。無向無環圖等效於無向樹。有向無環圖稱為DAG。它不一定是樹。
節點和邊通常具有關聯的資訊，例如標籤或權重。例如，在航空航班圖中，節點可能用相應機場的名稱標記，邊可能具有等於飛行時間的權重。流行的遊戲“凱文·貝肯的六度分離”可以用帶標籤的無向圖來建模。每個演員都成為一個節點，用演員的姓名標記。當兩個演員在某部電影中一起出現時，節點之間透過邊連線。我們可以用電影的名稱標記這條邊。確定演員是否與凱文·貝肯之間隔著六步或更少的步驟，相當於在圖中找到一條長度最多為六的路徑，連線貝肯的頂點和另一個演員的頂點。（這可以透過在配套演算法書中找到的廣度優先搜尋演算法來完成。弗吉尼亞大學的貝肯神諭實際上已經實現了這種演算法，並且可以通過幾次點選告訴你從任何演員到凱文·貝肯的路徑[1]。）
有向圖
[edit | edit source]
具有一個端點在給定頂點上的邊的數量稱為該頂點的度數。在有向圖中，指向給定頂點的邊的數量稱為其入度，而指向該頂點的邊的數量稱為其出度。通常，我們可能希望能夠區分不同的節點和邊。我們可以將標籤與它們中的任何一個相關聯。我們稱這樣的圖帶標籤的。
有向圖操作
make-graph(): graph- 建立一個新的圖，最初沒有節點或邊。
make-vertex(graph G, element value): vertex- 建立一個新的頂點，具有給定的值。
make-edge(vertex u, vertex v): edge- 在u和v之間建立一條邊。在有向圖中，邊將從u流向v。
get-edges(vertex v): edge-set- 返回從v流出的邊的集合。
get-neighbors(vertex v): vertex-set- 返回連線到v的頂點的集合。
無向圖
[edit | edit source]
在有向圖中，邊從一個頂點指向另一個頂點，而在無向圖中，邊只是連線兩個頂點。我們可以向前或向後移動。這是一個雙向圖。
我們可能還想將某些成本或權重與邊的遍歷相關聯。 當我們新增此資訊時，圖被稱為**加權圖**。 加權圖的一個例子是國家首都之間的距離。
有向圖和無向圖都可以是加權的。 加權圖上的操作與在建立邊時新增權重引數相同。
加權圖操作（無向/有向圖操作的擴充套件）
make-edge(頂點u，頂點v，權重w)：邊- 在u和v之間建立一條權重為w的邊。 在有向圖中，邊將從u流向v。
鄰接矩陣是表示圖的兩種常用方法之一。 鄰接矩陣顯示哪些節點是相鄰的。 如果兩個節點之間有一條邊連線，則這兩個節點是相鄰的。 在有向圖的情況下，如果節點與節點相鄰，則從到有一條邊。 換句話說，如果與相鄰，您可以透過遍歷一條邊從到達。 對於具有個節點的給定圖，鄰接矩陣將具有的維度。 對於無權圖，鄰接矩陣將用布林值填充。
對於任何給定節點，您可以透過檢視鄰接矩陣的第行來確定其相鄰節點。 處的真值表示從節點到節點有一條邊，而假值表示沒有邊。 在無向圖中，和的值將相等。 在加權圖中，布林值將被連線兩個節點的邊的權重替換，並使用一個特殊值表示邊的不存在。
![{\displaystyle \left(i,\left[1..n\right]\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/536da7d1241489aca63f932e0a87674ef50aa9ed)
鄰接矩陣的記憶體使用量為。
鄰接表是另一種常見的圖表示方法。有許多方法可以實現這種鄰接表示。一種方法是讓圖維護一個列表列表，其中第一個列表是對應於圖中每個節點的索引列表。這些中的每一個都引用另一個儲存與該節點相鄰的每個節點的索引的列表。在該列表中，將每個連結的權重與相鄰節點關聯起來也可能是有用的。
示例：一個無向圖包含四個節點 1、2、3 和 4。1 與 2 和 3 相連。2 與 3 相連。3 與 4 相連。
1 - [2, 3]
2 - [1, 3]
3 - [1, 2, 4]
4 - [3]
將圖中所有節點的列表儲存在雜湊表中可能會有用。然後鍵將對應於每個節點的索引，而值將是對相鄰節點索引列表的引用。
另一種實現可能要求每個節點保留其相鄰節點的列表。
在理想情況下，我們將完全瞭解圖的內容，從而讓我們最佳化頂點和邊的索引以進行高效查詢。但是，在計算機科學中，有許多開放式問題，在這些問題中，索引不切實際甚至不可能。圖遍歷讓我們可以解決這些問題。遍歷讓我們可以有效地搜尋大型空間，其中物件是透過它們與其他物件的關聯關係而不是物件本身的屬性來定義的。
從頂點 a 開始，訪問其鄰居 b，然後訪問 b 的鄰居 c，並一直進行下去，直到到達“死衚衕”，然後迭代回去並訪問從倒數第二個訪問的頂點可達的節點，並繼續應用相同的原則。
// Search in the subgraph for a node matching 'criteria'. Do not re-examine
// nodes listed in 'visited' which have already been tested.
GraphNode depth_first_search(GraphNode node, Predicate criteria, VisitedSet visited) {
// Check that we haven't already visited this part of the graph
if (visited.contains(node)) {
return null;
}
visited.insert(node);
// Test to see if this node satisfies the criteria
if (criteria.apply(node.value)) {
return node;
}
// Search adjacent nodes for a match
for (adjacent in node.adjacentnodes()) {
GraphNode ret = depth_first_search(adjacent, criteria, visited);
if (ret != null) {
return ret;
}
}
// Give up - not in this part of the graph
return null;
}
廣度優先搜尋訪問節點的鄰居，然後訪問鄰居的未訪問鄰居，等等。如果它從頂點 a 開始，它將訪問所有從 a 有邊的頂點。如果有些點無法訪問，它將不得不從新的頂點開始另一個 BFS。
一個雜湊表或雜湊對映是一個數據結構，它將鍵與值相關聯。它高效支援的主要操作是查詢：給定一個鍵（例如，一個人的姓名），找到相應的 value（例如，該人的電話號碼）。它的工作原理是使用一個雜湊函式將鍵轉換為一個雜湊，即一個雜湊表用來定位所需值的數字。此雜湊直接對映到鍵/值對陣列中的一個桶，因此稱為雜湊對映。對映方法允許我們直接訪問任何鍵/值對的儲存位置。
雜湊表<元素> 操作
make-hash-table(整數 n)：HashTable
- 建立一個包含 n 個桶的雜湊表。
get-value(HashTable h, Comparable key)：Element
- 返回給定鍵的元素的值。鍵必須是某種可比較的型別。
set-value(HashTable h, Comparable key, Element new-value)
- 將給定鍵的陣列元素設定為等於new-value。鍵必須是某種可比較的型別。
remove(HashTable h, Comparable key)
- 從雜湊表中刪除給定鍵的元素。鍵必須是某種可比較的型別。
雜湊表通常用於實現關聯陣列、集合和快取。與陣列類似，雜湊表提供平均常數時間O(1) 查詢，而與表中的專案數量無關。大多數雜湊表方案中的（希望很少見的）最壞情況查詢時間為 O(n)。[1] 與其他關聯陣列資料結構相比，當我們需要儲存大量資料記錄時，雜湊表最有用。
雜湊表可以用作記憶體中的資料結構。雜湊表也可以用於持久資料結構；資料庫索引通常使用基於雜湊表的基於磁碟的資料結構。
雜湊表還用於在許多資料壓縮實現中加快字串搜尋。
一個好的雜湊函式對於良好的雜湊表效能至關重要。選擇一個不好的雜湊函式可能會導致聚類行為，其中鍵對映到同一個雜湊桶（即衝突）的機率明顯大於隨機函式的預期。在任何雜湊實現中，衝突的非零機率是不可避免的，但解決衝突的運算元量通常隨對映到同一個桶的鍵的數量線性擴充套件，因此過多的衝突會顯著降低效能。此外，一些雜湊函式在計算上很昂貴，因此計算雜湊所需的時間（以及在某些情況下，記憶體）可能很繁重。
選擇一個好的雜湊函式很棘手。文獻中充斥著糟糕的選擇，至少在現代標準的衡量下是這樣。例如，Knuth 在《計算機程式設計藝術》中倡導的非常流行的乘法雜湊（參見下面的參考文獻）具有特別糟糕的聚類行為。但是，由於糟糕的雜湊只是會降低特定輸入鍵分佈的雜湊表效能，因此這些問題往往沒有被發現。
文獻中關於選擇雜湊函式的標準也很少。與大多數其他基本演算法和資料結構不同，關於什麼是“好的”雜湊函式沒有普遍的共識。本節的其餘部分按三個標準組織：簡單性、速度和強度，並將調查已知按這些標準表現良好的演算法。
簡單性和速度很容易客觀地衡量（例如，透過程式碼行數和 CPU 基準測試），但強度是一個更難以捉摸的概念。顯然，加密雜湊函式（如 SHA-1）將滿足雜湊表所需的相對寬鬆的強度要求，但它們的速度慢和複雜性使它們不受歡迎。事實上，即使是加密雜湊也不能提供保護，以防攻擊者想要透過選擇全部雜湊到同一個桶的鍵來降低雜湊表效能。對於這些特殊情況，應該使用通用雜湊函式，而不是任何一個靜態雜湊，無論它多麼複雜。
由於沒有標準衡量雜湊函式強度的度量方法，目前最先進的方法是使用一系列統計測試來衡量雜湊函式是否可以輕易地與隨機函式區分開來。可以說，最重要的測試是確定雜湊函式是否顯示雪崩效應，該效應本質上表明輸入金鑰的任何單個位變化應該平均影響輸出中的一半位。Bret Mulvey 特別主張測試嚴格雪崩條件，該條件指出，對於任何單個位變化，每個輸出位應該以二分之一的機率發生變化，而與金鑰中的其他位無關。純粹的加法雜湊函式，例如CRC，在滿足這個更強的條件方面表現糟糕。
顯然，一個強大的雜湊函式應該具有均勻分佈的雜湊值。Bret Mulvey 建議使用卡方檢驗來檢測均勻性，該檢驗基於從 21 到 216 的二的冪雜湊表大小。該測試比許多其他用於衡量雜湊函式的測試敏感得多，並且在許多流行的雜湊函式中發現了問題。
幸運的是，有一些好的雜湊函式可以滿足所有這些標準。最簡單的類別都是每次內部迴圈迭代消耗輸入金鑰的一個位元組。在這個類別中，簡單性和速度密切相關，因為快速演算法沒有時間執行復雜的計算。其中，Jenkins One-at-a-time 雜湊表現特別好，它改編自Bob Jenkins 的一篇文章，他是它的創造者。
uint32 joaat_hash(uchar *key, size_t len)
{
uint32 hash = 0;
size_t i;
for (i = 0; i < len; i++)
{
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
右側顯示了該雜湊的雪崩行為。該影像是使用 Bret Mulvey 的 AvalancheTest 在他的Hash.cs 工具集中製作的。每行對應於輸入中的單個位，每列對應於輸出中的一個位。綠色方塊表示良好的混合行為，黃色方塊表示弱混合行為，紅色表示無混合。最後一個位元組中只有幾個位是弱混合的，這比許多廣泛使用的雜湊函式的效能要好得多。
許多常用的雜湊函式在經過嚴格的雪崩測試時表現很差。例如，廣受歡迎的FNV 雜湊顯示了許多位根本沒有混合，特別是對於短金鑰。檢視Bret Mulvey 對 FNV 的評估，以進行更深入的分析。
如果速度比簡單性更重要，那麼每次迭代消耗多個位元組塊的雜湊函式類別可能令人感興趣。其中最複雜的一種是 Bob Jenkins 的“lookup3”，它以 12 位元組（96 位）塊消耗輸入。但請注意，使用此雜湊帶來的任何速度提升，只有在大型金鑰上才有可能有用，並且更高的複雜性也可能帶來速度問題，例如阻止最佳化編譯器內聯雜湊函式。Bret Mulvey 分析了早期版本，lookup2，發現它具有出色的雪崩行為。
雜湊函式的一個理想屬性是，從雜湊值（通常為 32 位）到特定大小雜湊表的儲存桶索引的轉換可以透過簡單的掩碼來完成，只保留較低的 k 位用於大小為 2k 的表（相當於計算雜湊值模表大小）。此屬性使雜湊表大小的增量加倍技術成為可能 - 舊錶中的每個儲存桶在新表中只對映到兩個儲存桶。由於其使用 XOR 摺疊，FNV 雜湊不具有此屬性。一些較舊的雜湊甚至更糟，要求表大小為素數而不是二的冪，同樣將儲存桶索引計算為雜湊值模表大小。通常，這樣的要求是函式基本較弱的跡象；使用素數表大小是使用更強大函式的糟糕替代方案。
衝突解決
[edit | edit source]如果兩個金鑰對映到同一個索引，則相應的記錄不能儲存在同一個位置。因此，如果它已經被佔用，我們必須找到另一個位置來儲存新記錄，並且要做到這一點，以便我們以後查詢時能夠找到它。
為了說明一個好的衝突解決策略的重要性，請考慮以下結果，該結果使用生日悖論推導而來。即使我們假設我們的雜湊函式輸出隨機索引，在均勻分佈在陣列上，即使對於具有 100 萬個條目的陣列，在它包含 2500 條記錄之前，至少發生一次衝突的機率為 95%。
有很多衝突解決技術，但最流行的是鏈式和開放定址。
鏈式
[edit | edit source]
在最簡單的鏈式雜湊表技術中，陣列中的每個槽位引用一個連結串列，該連結串列包含插入到同一個槽位的記錄。插入需要找到正確的槽位，並附加到該槽位中的連結串列的任一端；刪除需要搜尋連結串列並進行刪除。
鏈式雜湊表相對於開放定址雜湊表具有優勢，因為刪除操作很簡單，並且可以更長時間地推遲表的大小調整，因為即使在每個槽位都被使用的情況下，效能也會更加優雅地降低。事實上，許多鏈式雜湊表可能根本不需要調整大小，因為效能下降是線性的，因為表被填充。例如，包含其推薦容量兩倍資料的鏈式雜湊表平均速度大約只是其推薦容量下相同表的兩倍。
鏈式雜湊表繼承了連結串列的缺點。在儲存小型記錄時，連結串列的開銷可能很大。另一個缺點是遍歷連結串列的快取效能很差。
可以將其他資料結構用於鏈而不是連結串列。例如，透過使用自平衡樹，雜湊表的理論最壞情況時間可以降低到 O(log n) 而不是 O(n)。但是，由於每個連結串列都旨在很短，因此除非雜湊表設計為以最大容量執行，或者存在異常高的碰撞率，否則這種方法通常效率低下，就像在旨在導致碰撞的輸入中那樣。動態陣列也可以用於減少空間開銷並在記錄很小的情況下提高快取效能。
一些鏈式實現使用了一種最佳化，其中每個鏈的第一個記錄都儲存在表中。雖然這可以提高效能，但通常不建議這樣做：具有合理負載因子的鏈式表包含很大比例的空槽位，並且較大的槽位大小會導致它們浪費大量空間。
開放定址
[edit | edit source]
開放定址雜湊表可以將記錄直接儲存在陣列中。雜湊衝突透過探測來解決，或者搜尋陣列中的備選位置（探測序列），直到找到目標記錄，或者找到一個未使用的陣列槽位，這表明表中不存在這樣的鍵。眾所周知的探測序列包括
- 線性探測
- 其中探測之間的間隔是固定的——通常為 1，
- 二次探測
- 其中探測之間的間隔線性增加（因此，索引由二次函式描述），以及
- 雙重雜湊
- 其中探測之間的間隔對於每個記錄都是固定的，但由另一個雜湊函式計算。
這些方法之間的主要權衡是，線性探測具有最佳的快取效能，但對聚集最敏感，而雙雜湊具有較差的快取效能，但幾乎沒有聚集；二次雜湊在這兩個方面都處於中間位置。雙雜湊也可能比其他探測形式需要更多的計算。一些開放地址方法，例如後進先出雜湊和布穀鳥雜湊在陣列中移動現有鍵以騰出空間以容納新鍵。與基於探測的方法相比，這提供了更好的最大搜索時間。
對開放地址雜湊表效能的關鍵影響是負載因子；也就是說，陣列中使用的槽位的比例。當負載因子增加到 100% 時，查詢或插入給定鍵所需的探測次數會急劇增加。一旦表已滿，探測演算法甚至可能無法終止。即使使用良好的雜湊函式，負載因子通常也限制在 80%。一個不好的雜湊函式即使在非常低的負載因子下也能表現出較差的效能，因為它會產生大量的聚集。導致雜湊函式聚集的原因尚不清楚，並且很容易無意中編寫會導致嚴重聚集的雜湊函式。
示例虛擬碼
[edit | edit source]以下虛擬碼是開放地址雜湊表使用線性探測和單槽步進的實現，這是一種常見的有效方法，如果雜湊函式很好。查詢、設定和刪除函式中的每一個都使用一個通用的內部函式findSlot來定位陣列槽，該槽要麼包含給定鍵，要麼應該包含給定鍵。
record pair { key, value }
var pair array slot[0..numSlots-1]
function findSlot(key)
i := hash(key) modulus numSlots
loop
if slot[i] is not occupied or slot[i].key = key
return i
i := (i + 1) modulus numSlots
function lookup(key)
i := findSlot(key)
if slot[i] is occupied // key is in table
return slot[i].value
else // key is not in table
return not found
function set(key, value)
i := findSlot(key)
if slot[i].key = key
// (Key already in table. Update value.)
slot[i].value := value
else
// (Insert key and value in un-occupied slot.)
// (But first, make sure insert won't overload the table)
if the table is almost full
rebuild the table larger (note 1)
i := findSlot(key)
slot[i].key := key
slot[i].value := value
另一個展示開放地址技術的示例。所呈現的函式將網際網路協議地址的每個部分(4)進行轉換，其中 NOT 是按位取反，XOR 是按位異或，OR 是按位或，AND 是按位與，<< 和 >> 是左移和右移。
// key_1,key_2,key_3,key_4 are following 3-digit numbers - parts of ip address xxx.xxx.xxx.xxx
function ip(key parts)
j := 1
do
key := (key_2 << 2)
key := (key + (key_3 << 7))
key := key + (j OR key_4 >> 2) * (key_4) * (j + key_1) XOR j
key := key AND _prime_ // _prime_ is a prime number
j := (j+1)
while collision
return key
- 註釋 1
- 重建表需要分配一個更大的陣列，並遞迴使用設定操作將舊陣列的所有元素插入到新的更大陣列中。通常以指數方式增加陣列大小，例如將舊陣列大小加倍。
function remove(key)
i := findSlot(key)
if slot[i] is unoccupied
return // key is not in the table
j := i
loop
j := (j+1) modulus numSlots
if slot[j] is unoccupied
exit loop
k := hash(slot[j].key) modulus numSlots
if (j > i and (k <= i or k > j)) or
(j < i and (k <= i and k > j)) (note 2)
slot[i] := slot[j]
i := j
mark slot[i] as unoccupied
- 註釋 2
- 對於叢集中的所有記錄，其自然雜湊位置與其當前位置之間不得有空閒槽（否則查詢將在找到記錄之前終止）。在虛擬碼中的這一點上，i 是一個空閒槽，它可能會使叢集中後續記錄的此屬性失效。j 是這樣的後續記錄。k 是記錄在j 處自然落在雜湊表中的原始雜湊，如果不存在衝突。此測試是在詢問記錄j 是否相對於叢集的必要屬性被無效地定位，現在i 是空閒的。
另一種刪除技術是簡單地將槽標記為已刪除。但是，最終需要重建表才能簡單地刪除已刪除的記錄。以上方法提供了對現有記錄的 O(1) 更新和刪除，如果表的最高水位標記增加，則偶爾會重建。
上面的 O(1) 刪除方法只適用於線性探測的雜湊表，具有單槽步進。在一次操作中需要刪除許多記錄的情況下，標記要刪除的槽位並稍後重建可能更高效。
開放地址與鏈式
[edit | edit source]與開放地址相比，鏈式雜湊表具有以下優點
- 它們易於有效地實現，並且只需要基本資料結構。
- 從編寫合適的雜湊函式的角度來看，鏈式雜湊表對聚集不敏感，只需要最小化衝突。開放地址依賴於更好的雜湊函式來避免聚集。如果新手程式設計師可以新增自己的雜湊函式，這一點尤其重要，但即使是經驗豐富的程式設計師也會被意想不到的聚集效應所困擾。
- 它們的效能下降更加平穩。雖然鏈隨著表的填充而變長，但鏈式雜湊表不會“填滿”，也不會表現出在接近滿的表中使用開放地址時出現的查詢時間突然增加。(參見右側)
- 如果雜湊表儲存大型記錄，每個記錄約 5 個或更多個字，則鏈式比開放地址使用更少的記憶體。
- 如果雜湊表是稀疏的（即它有一個大型陣列，其中有很多空陣列槽），則即使對於每個記錄只有 2 到 4 個字的小型記錄，鏈式也比開放地址使用更少的記憶體，因為它的外部儲存。
對於小型記錄大小（幾個字或更少），與鏈式相比，就地開放地址的優勢在於
- 它們可能比鏈式更節省空間，因為它們不需要儲存任何指標或在雜湊表之外分配任何額外的空間。簡單的連結串列每個元素需要一個字的開銷。
- 插入避免了記憶體分配的時間開銷，甚至可以在沒有記憶體分配器的情況下實現。
- 由於它使用內部儲存，因此開放地址避免了鏈式外部儲存所需的額外間接定址。它還具有更好的區域性性，尤其是對於線性探測。對於小型記錄大小，這些因素可以產生比鏈式更好的效能，尤其是對於查詢。
- 它們更容易序列化，因為它們不使用指標。
另一方面，對於大型元素，普通開放地址是一個糟糕的選擇，因為這些元素會填充整個快取行（抵消快取優勢），並且在大型空表槽位上會浪費大量空間。如果開放地址表只儲存對元素的引用（外部儲存），那麼即使對於大型記錄，它也使用與鏈式相當的空間，但會失去其速度優勢。
一般來說，開放地址更適合用於具有小型記錄的雜湊表，這些記錄可以儲存在表中（內部儲存）並適合快取行。它們特別適合一個字或更少的元素。在預計表將具有高負載因子、記錄很大或資料大小可變的情況下，鏈式雜湊表通常可以執行得一樣好或更好。
最終，明智地使用任何型別的雜湊表演算法通常都足夠快；並且在雜湊表程式碼中花費的計算百分比很低。記憶體使用量很少被認為過大。因此，在大多數情況下，這些演算法之間的差異是微不足道的，並且其他考慮因素通常會起作用。
合併雜湊
[edit | edit source]合併雜湊是鏈式和開放地址的混合體，它在表本身內將節點鏈連結在一起。與開放地址一樣，它實現了比鏈式更高的空間使用率和（略微降低的）快取優勢。與鏈式一樣，它不會表現出聚集效應；事實上，表可以有效地填充到很高的密度。與鏈式不同，它不能擁有比表槽更多的元素。
完美雜湊
[edit | edit source]如果所有將要使用的鍵都已提前知道，並且沒有更多鍵可以適合雜湊表，則可以使用完美雜湊來建立一個完美散列表，其中不會發生衝突。如果使用最小完美雜湊，雜湊表中的每個位置也可以使用。
完美雜湊提供了一個雜湊表，其中查詢時間在最壞情況下是恆定的。這與鏈式和開放地址方法形成對比，在這些方法中，查詢時間平均較低，但可能會任意大。存在用於在插入鍵時維護完美雜湊函式的方法，稱為動態完美雜湊。一個更簡單的替代方案，它也提供最壞情況下的恆定查詢時間，是布穀鳥雜湊.
解決衝突的最簡單方法可能是用新值替換已存在於槽中的值，或者不太常見的是，丟棄要插入的記錄。在後面的搜尋中，這可能會導致搜尋找不到已插入的記錄。此技術對於實現快取特別有用。
一個更節省空間的解決方案類似於此，它使用 位陣列（一個一位欄位陣列）作為我們的表格。最初所有位都被設定為零，當我們插入一個鍵時，我們將相應的位設定為一。不會發生假陰性，但可能會發生 假陽性，因為如果搜尋找到一個 1 位，它會聲稱找到了該值，即使它只是一個巧合地雜湊到同一陣列槽中的另一個值。實際上，這樣的雜湊表僅僅是一種特定的 布隆過濾器。
使用良好的雜湊函式，雜湊表通常可以包含大約 70%–80% 的表格槽位數量的元素，並且仍然能夠很好地執行。根據衝突解決機制的不同，隨著新增更多元素，效能可能會逐漸或大幅度下降。為了解決這個問題，當負載因子超過某個閾值時，我們會分配一個新的、更大的表，並將原始表中的所有內容新增到這個新表中。例如，在 Java 的 HashMap 類中，預設的負載因子閾值為 0.75。
這可能是一個非常昂貴的操作，它的必要性是雜湊表的一個缺點。事實上，一些簡單的實現方法，例如在每次新增新元素時將表擴大一個，會大大降低效能，以至於使雜湊表變得毫無用處。但是，如果我們以固定的百分比（例如 10% 或 100%）擴大表，則可以使用 攤銷分析 來證明這些調整大小的頻率很低，以至於每次查詢的平均時間仍然是常數時間。為了瞭解為什麼這是真的，假設一個使用鏈式雜湊表的雜湊表從最小大小 1 開始，並在每次填充滿超過 100% 時加倍。如果最後它包含了 n 個元素，那麼為所有調整大小執行的總新增操作次數為
- 1 + 2 + 4 + ... + n = 2n - 1。
因為調整大小的成本構成一個 幾何級數，所以總成本為 O(n)。但是，我們還執行了 n 個操作來新增最初的 n 個元素，所以新增 n 個元素並調整大小的總時間為 O(n)，每個元素的攤銷時間為 O(1)。
另一方面，一些雜湊表實現，特別是在 即時系統 中，無法承受一次性擴大雜湊表的代價，因為它可能會中斷時間關鍵的操作。一種簡單的方法是最初為預期的元素數量分配足夠的記憶體，並禁止新增過多的元素。另一種有用的但更佔記憶體的技術是逐步執行調整大小
- 分配新的雜湊表，但保留舊的雜湊表，並在查詢時檢查這兩個表。
- 每次執行插入操作時，將該元素新增到新表中，並將 k 個元素從舊錶移動到新表中。
- 當所有元素都從舊錶中移除時，釋放舊錶。
為了確保在新的表本身需要擴大之前完全複製舊錶，在調整大小期間必須將表的大小至少增加 (k + 1)/k 倍。
線性雜湊 是一種允許增量雜湊表擴充套件的雜湊表演算法。它是使用一個單一的雜湊表實現的，但是有兩個可能的查詢函式。
另一種降低表調整大小成本的方法是選擇一種雜湊函式，這樣大多數值的雜湊值在表調整大小後不會改變。這種方法稱為 一致性雜湊，在基於磁碟和分散式雜湊中很普遍，因為調整大小成本過高。
雜湊表以偽隨機位置儲存資料，因此以排序方式訪問資料是一個非常耗時的操作。其他資料結構，如 自平衡二叉搜尋樹 通常操作速度更慢（因為它們的查詢時間為 O(log n)），並且實現起來比雜湊表複雜得多，但始終保持排序的資料結構。參見 雜湊表和自平衡二叉搜尋樹的比較。
雖然雜湊表查詢平均使用常數時間，但花費的時間可能很長。評估一個好的雜湊函式可能是一個緩慢的操作。特別是，如果可以使用簡單的陣列索引代替，這通常更快。
雜湊表通常表現出較差的 區域性性——也就是說，要訪問的資料似乎隨機分佈在記憶體中。由於雜湊表導致跳躍的訪問模式，這會導致 微處理器快取 未命中，從而導致長時間延遲。緊湊的資料結構（如使用 線性搜尋 搜尋的陣列）可能更快，如果表相對較小，並且金鑰比較起來很便宜，例如使用簡單的整數金鑰。根據 摩爾定律，快取大小呈指數級增長，因此被認為“小”的範圍可能正在擴大。最佳效能點因系統而異；例如，在 Parrot 上的測試表明，它的雜湊表在除最簡單情況（一到三個條目）以外的所有情況下都優於線性搜尋。
更重要的是，雜湊表更難編寫和使用，並且更容易出錯。雜湊表要求為每種金鑰型別設計一個有效的雜湊函式，在許多情況下，這比自平衡二叉搜尋樹所需的設計和除錯比較函式更困難、更費時。在開放地址雜湊表中，建立糟糕的雜湊函式更容易。
此外，在某些應用程式中，具有雜湊函式知識的 駭客 能夠向雜湊提供資訊，從而透過導致過多的衝突來建立最壞情況的行為，從而導致非常糟糕的效能（即 拒絕服務攻擊）。在關鍵應用程式中，可以使用 通用雜湊 或者可能更喜歡具有更好最壞情況保證的資料結構。有關詳細資訊，請參見 Crosby 和 Wallach 的文章 Denial of Service via Algorithmic Complexity Attacks。
可擴充套件雜湊 和 線性雜湊 是雜湊演算法，用於資料庫演算法中，例如索引檔案結構，甚至資料庫的主檔案組織。通常，為了使大型資料庫的搜尋可擴充套件，搜尋時間應該與 log N 或接近常數成正比，其中 N 是要搜尋的記錄數。log N 搜尋可以透過樹結構實現，因為扇出度和樹的高度與找到記錄所需的步驟數相關，所以樹的高度是找到記錄所需的最大磁碟訪問次數。然而，雜湊表也被使用，因為磁碟訪問的成本可以用磁碟訪問的單位來計算，並且該單位通常是資料塊。由於雜湊表在最佳情況下可以使用一次或兩次訪問找到鍵，所以雜湊表索引在檢索連線操作期間的記錄集合時通常被認為更快，例如。
SELECT * from customer, orders where customer.cust_id = orders.cust_id and cust_id = X
例如，如果 orders 有一個關於 cust_id 的雜湊索引，那麼定位包含與 cust_id = X 匹配的訂單記錄位置的塊將花費常數時間。（雖然，如果 orders 的值型別是訂單 ID 列表，那麼雜湊鍵將只是每個訂單批次的一個唯一的 cust_id，這將避免不必要的衝突）。
可擴充套件雜湊和線性雜湊有一些相似之處：衝突被認為是不可避免的，並且是演算法的一部分，其中添加了衝突空間的塊或桶；需要傳統的良好雜湊函式範圍，但雜湊值透過動態地址函式進行轉換；在 可擴充套件雜湊 中，使用位掩碼來遮蔽不需要的位，但該掩碼長度會週期性地增加一，使可用定址空間翻倍；在可擴充套件雜湊中，還有一個間接定址目錄地址空間，目錄條目與另一個地址（指標）配對，指向包含鍵值對的實際塊；目錄中的條目對應於位掩碼後的雜湊值（因此條目數量等於最大位掩碼值 + 1，例如 2 位位掩碼，可以定址一個包含 00 01 10 11 的目錄，或 3 + 1 = 4）。
在 線性雜湊 中，傳統的雜湊值也使用位掩碼進行掩碼，但如果得到的較小雜湊值低於“分裂”變數，則原始雜湊值使用比它長一位的位掩碼進行掩碼，使得到的雜湊值定址最近新增的塊。分裂變數在 0 到當前最大位掩碼值之間遞增，例如 2 位位掩碼，或線上性雜湊術語中，級別為 2，分裂變數將在 0 到 3 之間變化。當分裂變數達到 4 時，級別增加 1，所以在下一輪分裂變數中，它將在 0 到 7 之間變化，並在達到 8 時重置。
分裂變數遞增允許增加定址空間，因為新塊被新增；每次插入鍵值對並且溢位鍵值對鍵所對映到的特定塊時，就會決定新增一個新塊。這個溢位位置可能與分裂變數所指向的要分裂的塊完全無關。但是，隨著時間的推移，如果假設給定一個良好的隨機雜湊函式，它將條目均勻地分佈在所有可定址塊中，那麼實際上需要分裂的塊（因為它們溢位了）將會按照迴圈的方式依次獲得機會，因為分裂值在 0 到 N 之間變化，其中 N 是 2 的 level 次方的倍數，level 是分裂變數達到 N 時遞增的變數。
使用可擴充套件雜湊和線性雜湊都一次新增一個新塊。
在 可擴充套件雜湊 中，塊溢位（一個新的鍵值與 B 個其他鍵值衝突，其中 B 是一個塊的大小）透過檢查位掩碼的大小“本地”處理，稱為“區域性深度”，這是一個必須與塊一起儲存的屬性。目錄結構也具有深度，稱為“全域性深度”。如果區域性深度小於全域性深度，那麼區域性深度就會增加，並且所有鍵值都會重新雜湊並透過現在長一位的位掩碼，將它們放置在當前塊或另一個塊中。如果另一個塊在目錄中查詢時碰巧是同一個塊，那麼就會新增一個新塊，並且另一個塊的目錄條目將指向新塊。為什麼目錄中有兩個條目指向同一個塊？這是因為如果區域性深度等於目錄的全域性深度，這意味著目錄的位掩碼沒有足夠的位來處理塊位掩碼長度的遞增，因此目錄必須遞增其位掩碼長度，但這意味著目錄現在將可定址條目數量翻倍。由於一半的可定址條目不存在，目錄只是將指標複製到新的條目中，例如，如果目錄包含 00、01、10、11 的條目，或 2 位位掩碼，並且它變成了 3 位位掩碼，那麼 000 001 010 011 100 101 110 111 將成為新的條目，並且 00 的塊地址將指向 000 和 001；01 的指標指向 010 和 011，10 指向 100 和 101，等等。因此，這種情況導致了兩個目錄條目指向同一個塊。雖然即將溢位的塊現在可以透過將第二個指標重定向到新新增的塊來新增一個新塊，但其他原始塊將有兩個指向它們的指標。當它們輪到分裂時，演算法將檢查區域性深度和全域性深度，這一次會發現區域性深度更小，因此不需要目錄分裂，只需要新增一個新塊，並將第二個目錄指標從指向以前的塊移動到指向新塊。
在 線性雜湊 中，新增一個類似雜湊的塊不會在塊溢位時立即發生，因此會建立一個溢位塊來附加到溢位塊。然而，塊溢位表明需要更多空間，這是透過分裂“分裂”變數所指向的塊實現的，該變數最初為零，因此最初指向塊零。分裂是透過獲取分裂塊中所有鍵值對及其溢位塊（如果有），再次雜湊鍵，但使用長度為當前級別 + 1 的位掩碼來完成的。這將導致兩個塊地址，一些將是舊的塊號，而另一些將是
a2 = old block number + ( N times 2 ^ (level) )
- 基本原理
令 m = N 乘以 2 的 level 次方；如果 h 是原始雜湊值，並且舊塊號 = h mod m，現在新的塊號是 h mod ( m * 2 )，因為 m * 2 = N 乘以 2 的 (level+1) 次方，那麼新的塊號是 h mod m 如果 (h / m) 是偶數，所以將 h/m 除以 2 會留下一個零餘數，因此不會改變餘數，或者新的塊號是 ( h mod m ) + m，因為 h / m 是一個奇數，將 h / m 除以 2 會留下 m 的剩餘餘數，加上原始餘數。（相同的原理適用於可擴充套件雜湊深度遞增）。
如上所述，使用編號為 a2 的新塊建立，這通常發生在 +1 的先前 a2 值上。完成此操作後，分裂變數就會遞增，以便下一個 a2 值將再次是舊的 a2 + 1。透過這種方式，每個塊最終都會被分裂變數覆蓋，因此每個塊都會被預先重新雜湊到額外的空間中，並且新塊會被逐步新增。不再需要的溢位塊會被丟棄，以便在需要時進行垃圾收集，或者透過連結放到一個可用的空閒塊列表中。
當分裂變數達到 ( N 乘以 2 的 level 次方 ) 時，level 就會遞增，分裂變數就會重置為零。在下一輪中，分裂變數現在將從零遍歷到 ( N 乘以 2 的 (old_level + 1) 次方 )，這與上一輪開始時的塊數完全相同，但包括上一輪建立的所有塊。
對線性雜湊和可擴充套件雜湊的檔案儲存對映的簡單推論
[edit | edit source]可以看出，可擴充套件雜湊需要空間來儲存一個目錄，該目錄可以翻倍。
由於兩種演算法的空間都是一次增加一個塊，如果塊具有已知的最大尺寸或固定尺寸，那麼將塊對映為順序附加到檔案的塊是直接的。
在可擴充套件雜湊中，將目錄儲存為一個單獨的檔案是有邏輯的，因為翻倍可以透過將檔案附加到目錄檔案的末尾來實現。單獨的塊檔案不需要改變，除了將塊附加到它的末尾。
線性雜湊的標題資訊不會增加大小：基本上只需要記錄 N、level 和 split 的值，因此可以將這些值作為標題合併到固定塊大小的線性雜湊儲存檔案中。
然而，線性雜湊需要空間來存放溢位塊，這最好儲存在另一個檔案中，否則線上性雜湊檔案中定址塊並不像將塊號乘以塊大小然後加上 N、level 和 split 的空間那樣簡單。
在下一節中，給出了用 Java 實現的線性雜湊的完整示例，使用記憶體中實現的線性雜湊，以及程式碼來管理檔案目錄中的檔案塊，檔案目錄的整個內容代表持久線性雜湊結構。
實現
[edit | edit source]雖然許多程式語言已經提供了雜湊表功能，[2] 但有一些獨立的實現值得一提。
- Google Sparse Hash Google SparseHash 專案包含幾個 Google 使用的雜湊對映實現，具有不同的效能特徵，包括一個針對空間進行最佳化的實現和一個針對速度進行最佳化的實現。記憶體最佳化的實現非常節省記憶體，只有 2 位/條目的開銷。
- MCT 提供類似於 Google 的
dense_hash_map的雜湊表，但對包含的值沒有限制；它還提供異常安全性並支援 C++0x 功能。 - 許多執行時語言和/或標準庫使用雜湊表來實現它們對關聯陣列的支援，因為它們的效率很高。
可擴充套件雜湊的 Python 實現
[edit | edit source]檔案 - 塊管理例程不存在，因此可以新增進來，使之成為資料庫雜湊索引的真實實現。
一個完整頁面根據（本地深度）th 位進行分割，首先收集指向完整頁面的所有目錄索引，根據 d 位為 0 或 1（分別對應第一和第二新頁面）更新指標，然後在對每個鍵進行雜湊並使用每個雜湊的 d 位來檢視要分配到哪個頁面之後，重新載入所有鍵值對。每個新頁面的本地深度比舊頁面的本地深度大 1，這樣在下一次分割時可以使用下一個 d 位。
PAGE_SZ = 20
class Page:
def __init__(self):
self.m = {}
self.d = 0
def full(self):
return len(self.m) > PAGE_SZ
def put(self,k,v):
self.m[k] = v
def get(self,k):
return self.m.get(k)
class EH:
def __init__(self):
self.gd = 0
p = Page()
self.pp= [p]
def get_page(self,k):
h = hash(k)
p = self.pp[ h & (( 1 << self.gd) -1)]
return p
def put(self, k, v):
p = self.get_page(k)
if p.full() and p.d == self.gd:
self.pp = self.pp + self.pp
self.gd += 1
if p.full() and p.d < self.gd:
p.put(k,v);
p1 = Page()
p2 = Page()
for k2 in p.m.keys():
v2 = p.m[k2]
h = k2.__hash__()
h = h & ((1 << self.gd) -1)
if (h | (1 << p.d) == h):
p2.put(k2,v2)
else:
p1.put(k2,v2)
l = []
for i in xrange(0, len(self.pp)):
if self.pp[i] == p:
l.append(i)
for i in l:
if (i | ( 1 << p.d) == i):
self.pp[i] = p2
else:
self.pp[i] = p1
p1.d = p.d + 1
p2.d = p1.d
else:
p.put(k, v)
def get(self, k):
p = self.get_page(k)
return p.get(k)
if __name__ == "__main__":
eh = EH()
N = 10000
l = []
for i in range(0,N):
l.append(i)
import random
random.shuffle(l)
for i in l:
eh.put(i,i)
print l
for i in range(0, N):
print eh.get(i)
可擴充套件雜湊的 Java 實現
[edit | edit source]上面 Python 程式碼的直接 Java 翻譯，經測試可以使用。
package ext_hashing;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
public class EH2<K, V> {
static class Page<K, V> {
static int PAGE_SZ = 20;
private Map<K, V> m = new HashMap<K, V>();
int d = 0;
boolean full() {
return m.size() > PAGE_SZ;
}
void put(K k, V v) {
m.put(k, v);
}
V get(K k) {
return m.get(k);
}
}
int gd = 0;
List<Page<K, V>> pp = new ArrayList<Page<K, V>>();
public EH2() {
pp.add(new Page<K, V>());
}
Page<K, V> getPage(K k) {
int h = k.hashCode();
Page<K, V> p = pp.get(h & ((1 << gd) - 1));
return p;
}
void put(K k, V v) {
Page<K, V> p = getPage(k);
if (p.full() && p.d == gd) {
List<Page<K, V>> pp2 = new ArrayList<EH2.Page<K, V>>(pp);
pp.addAll(pp2);
++gd;
}
if (p.full() && p.d < gd) {
p.put(k, v);
Page<K, V> p1, p2;
p1 = new Page<K, V>();
p2 = new Page<K, V>();
for (K k2 : p.m.keySet()) {
V v2 = p.m.get(k2);
int h = k2.hashCode() & ((1 << gd) - 1);
if ((h | (1 << p.d)) == h)
p2.put(k2, v2);
else
p1.put(k2, v2);
}
List<Integer> l = new ArrayList<Integer>();
for (int i = 0; i < pp.size(); ++i)
if (pp.get(i) == p)
l.add(i);
for (int i : l)
if ((i | (1 << p.d)) == i)
pp.set(i, p2);
else
pp.set(i, p1);
p1.d = p.d + 1;
p2.d = p1.d;
} else
p.put(k, v);
}
public V get(K k) {
return getPage(k).get(k);
}
public static void main(String[] args) {
int N = 500000;
Random r = new Random();
List<Integer> l = new ArrayList<Integer>();
for (int i = 0; i < N; ++i) {
l.add(i);
}
for (int i = 0; i < N; ++i) {
int j = r.nextInt(N);
int t = l.get(j);
l.set(j, l.get(i));
l.set(i, t);
}
EH2<Integer, Integer> eh = new EH2<Integer, Integer>();
for (int i = 0; i < N; ++i) {
eh.put(l.get(i), l.get(i));
}
for (int i = 0; i < N; ++i) {
System.out.printf("%d:%d , ", i, eh.get(i));
if (i % 10 == 0)
System.out.println();
}
}
}
線性雜湊的 Java 實現
[edit | edit source]（可用於任意大小的簡單資料庫索引，（幾乎？））
這段程式碼源於對更大 Java HashMap 的需求。最初，Java HashMap 標準物件用作 Map 來索引類似堆的資料庫檔案（DBF 格式）。但是後來，遇到了一個包含太多記錄的檔案，導致丟擲 OutOfMemoryError，因此線性雜湊似乎是一個相當簡單的演算法，可以用作基於磁碟的索引方案。
最初，線性雜湊是在 Java Map 介面之後實現的，主要是 put(k,v) 和 get(k,v) 方法。使用了泛型，為了不陷入鍵值對的細節。
除錯以實現功能
[edit | edit source]自定義轉儲到 System.err 用於驗證塊是否已建立、填充，以及溢位塊的數量是否符合預期（數量 = 1）。所有這些都是在純記憶體實現中完成的。
後來，引入了標準的 Java 解耦，原始的 LHMap2 類接受事件的偵聽器，例如需要塊時。然後將偵聽器實現為塊檔案管理器，每當在塊列表上遇到空塊時，將塊載入到記憶體 LHMap2 物件的塊列表中，並檢查虛擬機器執行時空閒記憶體是否不足，並使用最基本的先到先出快取刪除演算法（不是最近使用 (LRU)，也不是最少使用）透過將它們儲存到磁碟檔案，然後主動呼叫系統垃圾收集器來退休塊。
由於存在應用程式用例，即外部索引大型 DBF 表，因此該用例被用作演算法實現的主要測試工具。
package linearhashmap;
import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
/**
*
* @param <K>
* key type , must implement equals() and hashCode()
* @param <V>
* value type
*
*
*/
public class LHMap2<K, V> implements Map<K, V>, Serializable {
/**
*
*/
private static final long serialVersionUID = 3095071852466632996L;
/**
*
*/
public static interface BlockListener<K, V> {
public void blockRequested(int block, LHMap2<K, V> map);
}
List<BlockListener<K, V>> listeners = new ArrayList<BlockListener<K, V>>();
// int savedBlocks;
int N;
int level = 0;
int split = 0;
int blockSize;
long totalWrites = 0;
List<Block<K, V>> blockList = new ArrayList<Block<K, V>>();
public void addBlockListener(BlockListener<K, V> listener) {
listeners.add(listener);
}
void notifyBlockRequested(int block) {
for (BlockListener<K, V> l : listeners) {
l.blockRequested(block, this);
}
}
public LHMap2(int blockSize, int nStartingBlocks) {
this.blockSize = blockSize;
this.N = nStartingBlocks;
for (int i = 0; i < nStartingBlocks; ++i) {
addBlock();
}
Runtime.getRuntime().addShutdownHook(new Thread(new Runnable() {
@Override
public void run() {
showStructure();
}
}));
}
public static class Block<K, V> implements Externalizable {
/**
*
*/
int j = 0;
Block<K, V> overflow = null;
LinkedList<K> keyList = new LinkedList<K>();
LinkedList<V> valueList = new LinkedList<V>();
transient private LHMap2<K, V> owner;
transient private Map<K, V> shadow = new TreeMap<K, V>();
private boolean changed = false;
private int size = 0;
public LHMap2<K, V> getOwner() {
return owner;
}
public void setOwner(LHMap2<K, V> owner) {
this.owner = owner;
Block<K, V> ov = overflow;
while (ov != null) {
overflow.setOwner(owner);
ov = ov.overflow;
}
}
public Block() {
super();
}
public Block(LHMap2<K, V> map) {
setOwner(map);
}
public V put(K k, V v) {
setChanged(true);
V v2 = replace(k, v);
if (v2 == null) {
++size;
if (keyList.size() == getOwner().blockSize) {
if (overflow == null) {
getOwner().blockOverflowed(this, k, v);
} else {
overflow.put(k, v);
}
} else {
keyList.addFirst(k);
valueList.addFirst(v);
}
}
return v2;
}
void setChanged(boolean b) {
changed = b;
}
public Map<K, V> drainToMap(Map<K, V> map) {
while (!keyList.isEmpty()) {
K k = keyList.removeLast();
V v = valueList.removeLast();
map.put(k, v);
}
if (overflow != null)
map = overflow.drainToMap(map);
garbageCollectionOverflow();
return map;
}
public void updateMap(Map<K, V> map) {
Iterator<K> ik = keyList.descendingIterator();
Iterator<V> iv = valueList.descendingIterator();
while (ik.hasNext() && iv.hasNext()) {
map.put(ik.next(), iv.next());
}
if (overflow != null)
overflow.updateMap(map);
}
private void garbageCollectionOverflow() {
if (overflow != null) {
overflow.garbageCollectionOverflow();
overflow = null;
}
}
public void addOverflowBucket() {
// assert overflow is needed
if (keyList.size() < getOwner().blockSize)
return;
if (overflow == null) {
overflow = new Block<K, V>(getOwner());
} else {
overflow.addOverflowBucket();
}
}
public V replace(K key, V v2) {
if (overflow != null) {
V v = overflow.replace(key, v2);
if (v != null)
return v;
}
Iterator<K> i = keyList.listIterator();
int j = 0;
while (i.hasNext()) {
if (key.equals(i.next())) {
V v = valueList.get(j);
if (v2 != null) {
valueList.set(j, v2);
}
return v;
}
++j;
}
return null;
}
public boolean isChanged() {
return changed;
}
@Override
public void readExternal(ObjectInput arg0) throws IOException,
ClassNotFoundException {
int sz = arg0.readInt();
for (int i = 0; i < sz; ++i) {
K k = (K) arg0.readObject();
V v = (V) arg0.readObject();
shadow.put(k, v);
}
}
public void loadFromShadow(LHMap2<K, V> owner) {
setOwner(owner);
Block<K, V> b = this;
for (K k : shadow.keySet()) {
if (b.keyList.size() == owner.blockSize) {
Block<K, V> overflow = new Block<K, V>(owner);
b.overflow = overflow;
b = overflow;
}
b.keyList.add(k);
b.valueList.add(shadow.get(k));
}
shadow.clear();
}
@Override
public void writeExternal(ObjectOutput arg0) throws IOException {
if (!changed)
return;
Map<K, V> map = new TreeMap<K, V>();
updateMap(map);
int sz = map.size();
arg0.writeInt(sz);
for (K k : map.keySet()) {
arg0.writeObject(k);
arg0.writeObject(map.get(k));
}
setChanged(false);
}
}
void init() {
for (int i = 0; i < N; ++i) {
addBlock();
}
}
/**
* @param hashValue
* @return a bucket number.
*/
int getDynamicHash(int hashValue) {
long unsignedHash = ((long) hashValue << 32) >>> 32;
// ^^ this long cast needed
int h = (int) (unsignedHash % (N << level));
// System.err.println("h = " + h);
if (h < split) {
h = (int) (unsignedHash % (N << (level + 1)));
// System.err.println("h < split, new h = " + h);
}
return h;
}
@Override
public V put(K k, V v) {
++totalWrites;
int h = getDynamicHash(k.hashCode());
Block<K, V> b = getBlock(h);
b.put(k, v);
return v;
}
public long getTotalWrites() {
return totalWrites;
}
private Block<K, V> getBlock(int h) {
notifyBlockRequested(h);
return blockList.get(h);
}
void blockOverflowed(Block<K, V> b, K k, V v) {
splitNextBucket();
b.addOverflowBucket();
b.put(k, v);
}
private void splitNextBucket() {
Block<K, V> b = getBlock(split);
TreeMap<K, V> map = new TreeMap<K, V>();
b.drainToMap(map);
addBlock();
System.err.printf("split N LEVEL %d %d %d \n", split, N, level);
if (++split >= (N << level)) {
++level;
split = 0;
}
for (K k : map.keySet()) {
V v = map.get(k);
int h = getDynamicHash(k.hashCode());
System.err.println(h + " ");
Block<K, V> b2 = getBlock(h);
b2.put(k, v);
}
}
private Block<K, V> addBlock() {
Block<K, V> b = new Block<K, V>(this);
blockList.add(b);
return b;
}
@Override
public void clear() {
blockList = new ArrayList<Block<K, V>>();
split = 0;
level = 0;
totalWrites = 0;// savedBlocks = 0;
}
@Override
public boolean containsKey(Object key) {
return get(key) != null;
}
@Override
public boolean containsValue(Object value) {
return values().contains(value);
}
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
TreeSet<Map.Entry<K, V>> set = new TreeSet<Map.Entry<K, V>>();
Set<K> kk = keySet();
for (K k : kk) {
final K k2 = k;
set.add(new Entry<K, V>() {
@Override
public K getKey() {
return k2;
}
@Override
public V getValue() {
return get(k2);
}
@Override
public V setValue(V value) {
return put(k2, value);
}
});
}
return set;
}
@Override
public V get(Object key) {
int h = getDynamicHash(key.hashCode());
Block<K, V> b = getBlock(h);
return b.replace((K) key, null);
}
@Override
public boolean isEmpty() {
return size() == 0;
}
@Override
public Set<K> keySet() {
TreeSet<K> kk = new TreeSet<K>();
for (int i = 0; i < blockList.size(); ++i) {
Block<K, V> b = getBlock(i);
kk.addAll(b.keyList);
Block<K, V> ov = b.overflow;
while (ov != null) {
kk.addAll(ov.keyList);
ov = ov.overflow;
}
}
return kk;
}
@Override
public void putAll(Map<? extends K, ? extends V> m) {
for (K k : m.keySet()) {
put(k, m.get(k));
}
}
@Override
public V remove(Object key) {
return null;
}
@Override
public int size() {
long sz = longSize();
return (int) (sz > Integer.MAX_VALUE ? Integer.MAX_VALUE
: sz);
}
public long longSize() {
long sz = 0;
for (Block<K, V> b : blockList) {
Block<K, V> b1 = b;
while (b1 != null) {
sz += b1.size;
b1 = b.overflow;
}
}
return sz;
}
@Override
public Collection<V> values() {
ArrayList<V> list = new ArrayList<V>();
Set<K> kk = keySet();
for (K k : kk) {
list.add(get(k));
}
return list;
}
private void showStructure() {
for (int i = 0; i < blockList.size(); ++i) {
Block<K, V> b = getBlock(i);
Block<K, V> ov = b.overflow;
int k = 0;
while (ov != null) {
ov = ov.overflow;
++k;
}
System.out.println("Block " + i + " size " + b.keyList.size()
+ " overflow blocks = " + k);
}
}
}
在這個實現中，每個塊都是一個檔案，因為塊在這裡是可變大小的，以考慮泛型和可變大小的鍵值對，溢位塊是概念性的，而不是實際的磁碟儲存，因為塊的內容及其溢位桶（如果存在）的內容，在這個實現中，以交替的鍵值對列表的形式儲存。使用標準的 Java 自定義物件持久化方式，在 Block 資料類中實現 Externalizable 介面，方法用於儲存和載入到 Object 流。
package linearhashmap;
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Random;
/**
* This class manages the LHMap2 class block disk swapping, and saves and load an instance of the LHMap2 class.
* It has been used to externally index a legacy file based database of 100,000 record master table, and 1,000,000 record
* sized child tables, and accounts for heap space available in the java virtual machine, so that OutOfMemory errors
* are avoided when the heap space is low by putting blocks back on files, and garbage collecting them.
* The main performance bottleneck appeared when loading a million record table for an index , on initial creation
* of the index.
* @author doctor
*
* @param <K>
* @param <V>
*/
public class LHMap2BlockFileManager<K, V> implements
LHMap2.BlockListener<K, V>, Serializable {
/**
*
*/
private static final long serialVersionUID = 2615265603397988894L;
LHMap2BlockFileManagerData data = new LHMap2BlockFileManagerData(
new byte[10000], new Random(), 0, new ArrayList<Integer>(), 0);
public LHMap2BlockFileManager(File baseDir, String name, int maxBlocks,
double unloadRatio) {
data.home = new File(baseDir, name);
if (!data.home.exists())
data.home.mkdir();
this.data.maxBlocks = maxBlocks;
this.data.unloadRatio = unloadRatio;
}
@Override
public void blockRequested(int block, LHMap2<K, V> map) {
LHMap2.Block<K, V> b = map.blockList.get(block);
if (b == null) {
int tries = 3;
File f = new File(data.home, Integer.toString(block));
do {
if (f.exists())
break;
if (!f.exists()) {
if (--tries >= 0)
fatal(block);
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
} while (true);
try {
ByteArrayInputStream bis = new ByteArrayInputStream(data.buf);
FileInputStream fis = new FileInputStream(f);
int sz = fis.read(data.buf);
fis.close();
addByteStats(sz);
ObjectInputStream ois = new ObjectInputStream(bis);
b = new LHMap2.Block<K, V>();
b.readExternal(ois);
ois.close();
b.loadFromShadow(map);
map.blockList.set(block, b);
--data.retired;
} catch (FileNotFoundException e) {
e.printStackTrace();
fatal(block);
} catch (IOException e) {
e.printStackTrace();
fatal(block);
} catch (ClassNotFoundException e) {
e.printStackTrace();
fatal(block);
}
}
int size = map.blockList.size();
try {
long freeMemory = Runtime.getRuntime().freeMemory();
long limitMemory = (long) (data.avgBlockSize * data.unloadRatio * size);
if (block % 30 == 0)
System.err.println("free memory =" + freeMemory + " limit "
+ limitMemory);
if (map.split % 20 == 19) {
// this is just to add statistics before really needing to retire
retireRandomBlock(map, block);
++data.retired;
} else if (freeMemory < limitMemory) {
for (int i = 0; i < size / 4; ++i) {
retireRandomBlock(map, block);
++data.retired;
}
System.runFinalization();
System.gc();
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
private void addByteStats(int sz) {
++data.avgCount;
data.avgBlockSize = (int) ((data.avgBlockSize
* (data.avgCount - 1) + sz) / data.avgCount);
}
public void retireRandomBlock(LHMap2<K, V> map, int notThisOne)
throws FileNotFoundException, IOException {
int pick = 0;
int size = map.blockList.size();
LHMap2.Block<K, V> b = null;
for (pick = 0; pick < size
&& (pick == notThisOne || (b = map.blockList.get(pick)) == null); ++pick)
;
if (pick < size)
retireOneBlock(map, pick, b);
}
private void retireOneBlock(LHMap2<K, V> map, int pick, LHMap2.Block<K, V> b)
throws IOException, FileNotFoundException {
if (b == null)
return;
if (b.isChanged()) {
// System.err.println("Retiring " + pick);
File f = new File(data.home, Integer.toString(pick));
ByteArrayOutputStream bos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(bos);
b.writeExternal(oos);
oos.flush();
oos.close();
FileOutputStream fos = new FileOutputStream(f);
byte[] bb = bos.toByteArray();
fos.write(bb);
fos.flush();
fos.close();
if (bb.length > data.buf.length) {
data.buf = bb;
}
}
map.blockList.set(pick, null);
b = null;
}
private void fatal(int block) {
Exception e = new Exception();
try {
throw e;
} catch (Exception e2) {
e2.printStackTrace();
}
System.err.println("block " + block
+ " requested and it is not in blocklist and not a file");
for (int i : data.retirees) {
System.err.print(i + " ");
}
System.err.println(" were retired");
System.exit(-2);
}
public static boolean metaExists(File indexDir, String name) {
File home = new File(indexDir, name);
return new File(home, "LinearMap2").exists();
}
public static <K, V> LHMap2<K, V> load(File baseDir, String name)
throws FileNotFoundException, IOException, ClassNotFoundException {
File home = new File(baseDir, name);
File f2 = new File(home, "LinearMap2");
ObjectInputStream ois = new ObjectInputStream(new FileInputStream(f2));
LHMap2<K, V> map = (LHMap2<K, V>) ois.readObject();
ois.close();
loadBlocks(map);
return map;
}
private static <K, V> void loadBlocks(LHMap2<K, V> map) {
LHMap2BlockFileManager<K, V> mgr = getBlockManagerListener(map);
int size = map.blockList.size();
for (int i = 0; i < size; ++i) {
mgr.blockRequested(i, map);
}
}
public static <K, V> LHMap2BlockFileManager<K, V> getBlockManagerListener(
LHMap2<K, V> map) {
LHMap2BlockFileManager<K, V> mgr = (LHMap2BlockFileManager<K, V>) map.listeners
.get(0);
return mgr;
}
public static void save(File indexDir, String name,
LHMap2<?, ?> offsetMap) throws FileNotFoundException, IOException {
retireAllBlocks(offsetMap);
File home = new File(indexDir, name);
File f2 = new File(home, "LinearMap2");
ObjectOutputStream oos = new ObjectOutputStream(
new FileOutputStream(f2));
oos.writeObject(offsetMap);
oos.close();
}
private static <K, V> void retireAllBlocks(LHMap2<K, V> offsetMap)
throws FileNotFoundException, IOException {
LHMap2BlockFileManager<K, V> mgr = getBlockManagerListener(offsetMap);
int sz = offsetMap.blockList.size();
for (int i = 0; i < sz; ++i) {
LHMap2.Block<K, V> b = offsetMap.blockList.get(i);
// offsetMap.blockList.set(i, null); // mark for reloading as block
// destroyed after writing
if (b != null) {
mgr.retireOneBlock(offsetMap, i, b);
}
}
}
}
package linearhashmap;
import java.io.File;
import java.io.Serializable;
import java.util.List;
import java.util.Random;
public class LHMap2BlockFileManagerData implements Serializable{
/**
*
*/
private static final long serialVersionUID = 1L;
public byte[] buf;
public Random r;
public File baseDir;
public File home;
public int maxBlocks;
public int retired;
public double unloadRatio;
public List<Integer> retirees;
public int avgBlockSize;
public long avgCount;
public LHMap2BlockFileManagerData(byte[] buf, Random r, int retired,
List<Integer> retirees, long avgCount) {
this.buf = buf;
this.r = r;
this.retired = retired;
this.retirees = retirees;
this.avgCount = avgCount;
}
}
參考文獻
[edit | edit source]- ↑ 最簡單的雜湊表方案 - “帶有線性探測的開放定址”、“帶有連結串列的獨立連結”等等 - 在最壞情況下具有 O(n) 的查詢時間，其中（意外地或惡意地）大多數鍵“衝突” - 大多數鍵被雜湊到一個或幾個桶中。其他雜湊表方案 - “布穀鳥雜湊”、“動態完美雜湊”等等 - 即使在最壞情況下也能保證 O(1) 的查詢時間。當插入一個新鍵時，這些方案會在必要時改變它們的雜湊函式以避免衝突。
- ↑ 維基百科：程式語言比較（對映） 顯示了多少程式語言提供雜湊表功能。
集合在軟體應用程式中是很有用的工具，正如在數學中一樣，類似的抽象物件被聚合成集合。數學集合有一個相當簡單的介面，可以用令人驚訝的多種方式實現。
Set<item-type> ADT
contains(test-item:item-type):Boolean- 如果 test-item 包含在集合中，則為 True。
insert(new-item:item-type)- 將 new-item 新增到集合中。
remove(item:item-type)- 從集合中刪除 item。如果 item 不在集合中，此方法不執行任何操作。
remove(item-iter:List Iterator<item-type>)- 從集合中刪除由 item-iter 標識的專案。
get-begin():List Iterator<item-type>- 允許迭代集合中的元素。
get-end():List Iterator<item-type>- 還允許迭代集合中的元素。
union(other:Set<item-type>):Set<item-type>- 返回一個集合，其中包含此集合或 other 集合中的所有元素。具有預設實現。
intersect(other:Set<item-type>):Set<item-type>- 返回一個集合，其中包含此集合和 other 集合中的所有元素。具有預設實現。
subtract(other:Set<item-type>):Set<item-type>- 返回一個集合，其中包含此集合中但不在 other 集合中的所有元素。具有預設實現。
is-empty():Boolean- 如果不再有專案可以彈出，並且沒有棧頂專案，則為真。
get-size():Integer- 返回集合中的元素數量。
所有操作都可以在 時間內完成。
列表實現
[edit | edit source]有幾種不同的方法來實現集合。最簡單但大多數情況下效率最低的方法是簡單地建立一個線性列表（陣列、連結串列或類似結構），其中包含集合中的每個元素。對於最基本的操作，測試成員資格，可能的實現可能如下所示
function contains(List<T> list, T member)
for item in list
if item == member
return True
return False
要向此集合新增新成員，只需將元素新增到列表的開頭或結尾。（如果進行檢查以確保沒有重複元素，則其他一些操作可能更簡單。）其他操作可以類似地根據簡單的列表操作來實現。不幸的是，成員資格測試的最壞情況執行時間為 ，如果該項不在列表中，甚至平均情況時間也是相同的，假設該項在列表中的任何位置的可能性都是相同的。如果集合很小，或者如果經常訪問的項可以放在列表的前面，這可能是一個有效的解決方案，但其他選項的執行時間可能更快。
假設元素可以排序，並且插入和刪除很少，則一個保證按排序順序排列且沒有重複元素的列表可以更高效。使用排序列表，成員資格測試可以高效到 的順序。此外，並集、交集和差集可以線上性時間內實現，而使用無序列表則需要二次時間。
位陣列實現
[edit | edit source]對於某些資料，維護一個描述集合內容的位陣列可能更實用。在這種表示中，每個問題域元素都有一個 1 或 0，指定該物件是否是集合的元素。對於一個簡單的情況，假設只有 0 到 n 的整數可以是集合的成員，其中 n 是事先知道的。這可以用長度為 n+1 的位陣列來表示。contains 操作很簡單
function contains(BitArray array, Int member)
if member >= length(array)
return False
else if array[member] == 1
return True
else
return False
要向這種集合新增或刪除元素，只需修改位陣列以反映該索引應為 1 或 0。成員資格在正好 （常數）時間內執行，但它的域非常有限。可以對域進行移位，從 m 到 n 以步長 k，而不是像上面指定的那樣從 0 到 n 以步長 1，但這裡沒有太多靈活性。儘管如此，對於正確的域，這通常是最有效的解決方案。
位陣列是儲存布林變數集的有效結構。一個例子是一組命令列選項，這些選項允許應用程式在執行時執行各種行為。C 及類似語言提供了按位運算子，使程式設計師能夠在單個機器指令中訪問位域，而陣列訪問通常需要兩個或三個指令，包括記憶體讀取操作。一個功能齊全的位集實現包括用於計算集合並集、集合交集、集合差集和元素值的運算子。[1]
關聯陣列實現
[edit | edit source]關聯陣列——即雜湊表和二叉搜尋樹，代表了集合的一種重量級但通用的表示。二叉樹通常具有 時間實現以用於查詢和修改特定鍵，而雜湊表具有 實現（儘管有一個更高的常數因子）。此外，它們能夠儲存幾乎任何型別的鍵。成員資格測試很簡單：只需測試潛在的集合成員是否作為關聯陣列中的鍵存在。要新增元素，只需將集合成員作為關聯陣列中的鍵新增，並使用一個虛擬值。在最佳化的實現中，可以編寫一個專門的雜湊表或二叉樹，它不儲存與鍵相對應的值，而不是重複使用現有的關聯陣列實現。這裡的值沒有意義，它們會佔用一個常數因子的額外記憶體空間。
參考文獻
[edit | edit source]- ↑ Samuel Harbison 和 Guy Steele。C：參考手冊。2002 年。
在選擇資料結構之前，全面瞭解需要解決的問題非常重要，因為每種結構都針對特定任務進行了最佳化。例如，雜湊表有利於快速查詢時間而不是記憶體使用，而陣列則緊湊且不靈活。其他結構，例如堆疊，針對在整個程式執行過程中如何新增、刪除和訪問資料進行了最佳化以實施嚴格的規則。對資料結構的深刻理解是至關重要的，因為它為我們提供了以結構化方式思考程式行為的工具。
[TODO:] Use asymptotic behaviour to decide, most importantly seeing how the structure will be used: an infrequent operation does not need to be fast if it means everything else will be much faster
[TODO:] Can use a table like this one to compare the asymptotic behaviour of every structure for every operation on it.
| 陣列 | 動態陣列 | 陣列雙端佇列 | 單鏈表 | 雙向連結串列 | |
|---|---|---|---|---|---|
| 推入（前端） | - | O(n) | O(1) | O(1) | O(1) |
| 彈出（前端） | - | O(n) | O(1) | O(1) | O(1) |
| 推入（後端） | - | O(1) | O(1) | O(n)，可能 O(1)* | O(1) |
| 彈出（後端） | - | O(1) | O(1) | O(n) | O(1) |
| 在（給定迭代器）之前插入 | - | O(n) | O(n) | O(n) | O(1) |
| 刪除（給定迭代器） | O(n) | O(n) | O(n) | O(1) | |
| 在（給定迭代器）之後插入 | O(n) | O(n) | O(1) | O(1) | |
| 在（給定迭代器）之後刪除 | - | O(n) | O(n) | O(1) | O(1) |
| 獲取第 n 個元素（隨機訪問） | O(1) | O(1) | O(1) | O(n) | O(n) |
| 適合實現堆疊 | 否 | 是（後端是頂部） | 是 | 是（前端是頂部） | 是 |
| 適合實現佇列 | 否 | 否 | 是 | 可能* | 是 |
| C++ STL | std::array
|
std::vector
|
std::deque
|
std::forward_list
|
std::list
|
| Java 集合 | java.util.Array
|
java.util.ArrayList
|
java.util.ArrayDeque
|
- | java.util.LinkedList
|
* singly-linked lists can push to the back in O(1) with the modification that you keep a pointer to the last node
| 排序陣列 | 排序連結串列 | 自平衡二叉搜尋樹 | 雜湊表 | |
|---|---|---|---|---|
| 查詢鍵 | O(log n) | O(n) | O(log n) | 平均 O(1)，最壞情況下 O(n) |
| 插入元素 | O(n) | O(n) | O(log n) | 平均 O(1)，最壞情況下 O(n) |
| 刪除鍵 | O(n) | O(n) | O(log n) | 平均 O(1)，最壞情況下 O(n) |
| 刪除元素（給定迭代器） | O(n) | O(1) | O(1) | O(1) |
| 可以按排序順序遍歷嗎？ | 是 | 是 | 是 | 否 |
| 需要 | 比較函式 | 比較函式 | 比較函式 | 雜湊函式 |
| C++ STL | - | - | std::setstd::mapstd::multiset
|
std::unordered_setstd::unordered_mapstd::unordered_multiset
|
| Java 集合 | - | - | java.util.TreeSet
|
java.util.HashSet
|
- 請更正任何錯誤
| 二叉搜尋 | AVL 樹 | 二叉堆（最小） | 二項式佇列（最小） | |
|---|---|---|---|---|
| 插入元素 | O(log n) | O(log n) | O(log n) | O(1)（平均） |
| 刪除元素 | O(log n) | O(log n) | 不可用 | 不可用 |
| 刪除最小元素 | O(log n) | O(log n) | O(log n) | O(log n) |
| 查詢最小元素 | O(log n) | O(log n) | O(1) | O(log n)（如果指向最小的指標，則可以為 O(1)） |
| 增加鍵 | 不可用 | 不可用 | O(log n) | O(log n) |
| 減少鍵 | 不可用 | 不可用 | O(log n) | O(log n) |
| 查詢 | O(log n) | O(log n) | 不可用 | 不可用 |
| 刪除元素 | O(log n) | O(log n) | 不可用 | 不可用 |
| 建立 | O(1) | O(1) | O(1) | O(1) |
| 查詢第 k 小元素 | O(log n) | O(log n) | O((k-1)*log n) | O(k*log n) |
| 雜湊表（雜湊對映） | |
|---|---|
| 設定值 | Ω(1), O(n) |
| 獲取值 | Ω(1), O(n) |
| 刪除 | Ω(1), O(n) |
[TODO:] Can also add a table that specifies the best structure for some specific need e.g. For queues, double linked. For stacks, single linked. For sets, hash tables. etc...
[TODO:] Could also contain table with space complexity information (there is a significative cost in using hashtables or lists implemented via arrays, for example).