資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法學資料結構中的 LCFS 雜湊
在本節中，我們將瞭解什麼是 LCFS 雜湊。這是開放定址策略之一，該策略更改了衝突解決策略。如果我們檢查開放地址方案中的雜湊演算法，我們可以發現如果兩個元素髮生衝突，那麼優先順序較高的一項將被插入到表中，而後續元素必須繼續。因此，我們可以說開放定址方案中的雜湊是先進先出標準。
使用 LCFS（後進先出）方案。任務將以相反的方式執行。當我們插入一個元素時，它將放置在位置 x0。如果該位置已被元素 y 佔據，因為 yj = x0，那麼我們將 y 放置在位置 yj+1，可能會替換一些元素 z，依此類推。
根據 Poblete 和 Munro 的說法，在空表中插入 n 個元素後的預期搜尋時間可以透過以下公式限制。
$$E[W]=1+\Gamma^{-1}(\alpha n)\lgroup1+\frac{ln\:ln\:\frac{1}{1+\alpha}}{ln\:\Gamma^{-1}(\alpha n)}+O(\frac{1}{ln^{2}\:\Gamma^{2}(\alpha n)})\rgroup$$
此處 Γ 是伽馬函式，且
$$\Gamma^{-1}(\alpha n)=\frac{ln\:n}{ln\:ln\:n}\lgroup1+\frac{ln\:ln\:ln\:n}{ln\:ln\:n}+O(\frac{1}{ln\:ln\:n})\rgroup$$
更新於: 2020-08-11
422 次瀏覽
廣告