在本節中，我們將瞭解什麼是開放定址雜湊。開放定址是另一種解決衝突的技術。與鏈式方法不同，它不會將元素插入到其他資料結構中。它將資料插入到雜湊表本身。雜湊表的尺寸應大於鍵的數量。開放定址技術有三種不同的常用方法。這些方法是：線性探測、二次探測和雙重雜湊。在這種技術中，我們使用類似於其他雜湊技術的雜湊函式。如果該位置是空閒的，則將元素插入到該位置。現在，如果該位置已… 閱讀更多

在本節中，我們將瞭解什麼是鏈式雜湊。鏈式法是一種解決衝突的技術。我們無法避免衝突，但可以嘗試減少衝突，並嘗試為相同的雜湊值儲存多個元素。此技術假設我們的雜湊函式 h(x) 的範圍為 0 到 6。因此，對於超過 7 個元素，必須有一些元素會被放置在同一個位置。為此，我們將建立一個列表來相應地儲存它們。每次我們都將在列表的開頭新增元素，以便在 O(1) 時間內執行插入操作。讓… 閱讀更多

對於任何雜湊函式，我們都可以說，如果表大小 m 遠小於宇宙大小 u，那麼對於任何雜湊函式 h，U 的某個大的子集將具有相同的雜湊值。為了解決此問題，我們需要一組雜湊函式，從中我們可以選擇一個對 S 執行良好的函式。如果大多數雜湊函式對 S 更好，我們可以選擇隨機雜湊函式。假設 ℌ 是一組雜湊函式。我們可以說 ℌ 是通用的，如果對於每個 x、y ∈ U，… 閱讀更多

這裡我們將討論乘法雜湊方法。為此，我們使用雜湊函式：ℎ(𝑥) = ⌊𝑚𝑥𝐴⌋ 𝑚𝑜𝑑 𝑚這裡 A 是一個實值常數。此方法的優點是 m 的值不是那麼關鍵。我們也可以將 m 設為 2 的冪。雖然 A 的任何值都會產生雜湊函式，但某些 A 值比其他值更好。根據 Knuth 的說法，我們可以使用黃金分割率作為 A，所以 A 將是$$A=\frac{\sqrt5-1}{2}=0.61803398$$當然，無論為 A 選擇什麼值。鴿巢原理意味著如果 u ≥ … 閱讀更多

這裡我們將討論除法雜湊。為此，我們使用雜湊函式：ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚要使用此雜湊函式，我們維護一個數組 A[0, … m – 1]。其中陣列的每個元素都是指向連結列表頭的指標。連結列表 Li 指向陣列元素 A[i]，包含所有滿足 h(x) = i 的元素 x。此技術稱為鏈式雜湊。在這種雜湊表中，如果我們想要增加一個元素 x，這將花費 O(1) 時間。我們計算索引 i = h(x)。… 閱讀更多

這裡我們將討論具有整數鍵的雜湊表。這裡鍵值 𝑥 來自宇宙 𝑈，其中 𝑈 = {0, 1, … , 𝑢 – 2, 𝑢 – 1}。雜湊函式是 ℎ。此雜湊函式的域是 𝑈。範圍在集合 {0, 1, … , 𝑚 – 1} 中，並且 𝑚 ≤ 𝑢。如果對於每個 𝑥 ∈ 𝑆，ℎ(𝑥) 都是唯一的，則稱雜湊函式 h 是集合 𝑆 ⊆ 𝑈 的完美雜湊函式。S 的完美雜湊函式 ℎ 是最小的… 閱讀更多

我們將瞭解如何從二叉最大堆資料結構中刪除元素。假設初始樹如下所示：刪除演算法delete(heap, n) - 開始    如果堆為空，則退出    否則       item := heap[1]       last := heap[n]       n := n – 1       對於 i := 1, j := 2, j = heap[j]，則中斷          heap[i] := heap[j]       完成    結束 if    heap[i] := last 結束示例假設我們想要從最終堆中刪除 30：-

我們將瞭解如何從二叉最大堆資料結構中插入和元素。假設初始樹如下所示：插入演算法insert(heap, n, item) - 開始    如果堆已滿，則退出    否則       n := n + 1       對於 i := n, i > 1, 在每次迭代中設定 i := i / 2，執行          如果 item

與二項堆一樣，斐波那契堆是樹的集合。它們鬆散地基於二項堆。與二項堆中的樹不同，斐波那契堆中的樹是有根的但無序的。斐波那契堆中每個節點 x 都包含一個指向其父節點的指標 p[x]，以及一個指向其任意一個子節點的指標 child[x]。x 的子節點透過一個稱為 x 的子列表的迴圈雙向連結串列連結在一起。子列表中的每個子節點 y 都有指標 left[y] 和 right[y] 分別指向 y 的左右兄弟節點。如果節點 y 只是… 閱讀更多

二項堆是二項樹的集合。二項樹 Bk 是一個遞迴定義的有序樹。二項樹 B0 由單個節點組成。二項樹 Bk 由兩個二項樹 Bk-1 組成。它們連結在一起。其中一個的根是另一個的左端子節點。一些二項堆如下所示：二項樹的一些屬性是：Bk 的二項樹有 2k 個節點。樹的高度是 k深度為 i 的節點正好有 $$\left(\begin{array}{c}k\ j\end{array}\right)$$ 個，對於範圍 0 到 k 中的所有 i 二項堆二項堆… 閱讀更多