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

在本節中，我們將瞭解什麼是鏈式雜湊。鏈式定址是一種衝突解決技術。我們無法避免衝突，但我們可以嘗試減少衝突，並嘗試為相同的雜湊值儲存多個元素。此技術假設我們的雜湊函式 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。對於 0 到 k 範圍內的所有 i，深度 i 處正好有 $$\left(\begin{array}{c}k\ j\end{array}\right)$$ 個節點。二項堆... 閱讀更多