資料結構中的 Brent 方法

在本節，我們將瞭解 Brent 方法與開放定址雜湊有關的知識。這種方法是一種啟發式。它旨在儘可能減少雜湊表中成功搜尋的平均時間。

這種方法最初應用於雙重雜湊技術，但它可用於任何開放定址技術，例如線性探測和二次探測。在開放定址雜湊表中儲存的元素 x 的年齡是滿足 x 位於 A[x_i] 中最小的值 i。

Brent 方法試圖最小化所有元素的總年齡。如果我們插入元素 x，那麼它會遵循以下步驟——我們找到 i 的最小值，使得 A[x_i] 為空，這是傳統開放定址會插入 x 的位置。現在考慮一個元素 y，儲存在 A[x_i-2] 中。該元素存在於那裡是因為 yj = x_i-2，某個值 j ≥ 0。我們檢查陣列位置 A[y_j+1] 是否為空，那麼我們會將 y 移動到位置 A[y_j+1]，並在位置 A[x_i-2] 儲存 x。

與普通的開放定址相比，該方法將總年齡減少了 1。通常，Brent’s 方法針對每個 2 ≤ k ≤ i、陣列項 A[x_i-k] 進行檢查，檢視是否儲存了元素 y，該方法可以移動 y 到 A[y_j+1]、A[y_j+2]、……、A[y_j+k-1] 中的任何一個，以便為 x 騰出空間。

阿納布·查克拉博蒂

更新於：2020 年 8 月 10 日

518 次觀看

開啟您的 職業生涯

透過完成課程獲得認證

入門