数据结构中的Brent方法
在本节中，我们将了解与开放式寻址哈希相关的布伦特方法。此方法是一种启发式方法。这试图最小化哈希表中成功搜索的平均时间。
该方法最初应用于双重哈希技术，但是可以用于任何开放式寻址技术，例如线性和二次探测。元素x的年龄存储在一个开放式地址哈希表中，它是最小值i，因此x放置在A[xi]上
布伦特方法试图使所有元素的总寿命最小化。如果我们插入元素x，则它将遵循一些步骤-我们将找到i的最小值，从而A[xi]为空，这是标准开放式寻址将插入x的位置。现在考虑一个元素y，该元素存储在A[xi-2]中。该元素存储在这里，因为yj=xi-2，对于j≥0的某个值。我们检查数组位置A[yj+1]是否为空，然后将y移至位置A[yj+1]，并将x存储在位置A[xi-2]。
与常规开放式寻址相比，这使总生存期减少了1。通常，Brent方法对每个2≤k≤i进行检查，数组条目A[xi-k]可以查看是否将元素y存储在那里。到A[yj+1]，A[yj+2]，...中的任何一个。。。，A[yj+k-1]，为x腾出空间。