資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究資料結構中的除法雜湊
這裡我們將討論除法雜湊。為此，我們使用以下雜湊函式：
ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚
為了使用此雜湊函式，我們維護一個數組 A[0, … m – 1]。其中陣列的每個元素都是指向連結列表頭的指標。連結列表 Li 指向陣列元素 A[i]，包含所有滿足 h(x) = i 的元素 x。這種技術被稱為鏈地址法。
在這種雜湊表中，如果我們想要插入一個元素 x，這將花費 O(1) 的時間。我們計算索引 i = h(x)。然後將 x 追加或預先新增到列表 Li 中。如果我們想要搜尋或刪除一個元素，這個過程並不容易。我們必須找到索引 i = h(x)。然後遍歷列表 Li，直到我們到達所需的值或列表耗盡。此操作花費的時間與列表 Li 的大小成正比。如果我們的集合 S 有 0、m、2m、3m、…、nm 個元素，那麼儲存在 L0 中的所有元素將需要線性時間來搜尋和刪除。
這種情況非常罕見。例如，如果 S 在全集 U 中均勻且獨立地分佈，並且 u 是 m 的倍數，則每個列表 Li 的預期大小僅為 n/m。在這種情況下，搜尋和刪除花費 O(1 + α) 的時間。為了避免上述情況，我們必須明智地選擇 m。通常，我們避免將 m 設為 2 的冪。建議將 m 設為一個不接近 2 的冪的素數。
更新於： 2020年8月10日
476 次瀏覽
廣告