データ構造におけるブレント法（Brent's Method）とは｜ハッシュ表の探索を高速化する手法

ブレント法（Brent's Method）とは

本記事では、オープンアドレス法（open addressing）によるハッシングに関連する「ブレント法」について解説します。ブレント法はヒューリスティック（発見的手法）の一種であり、ハッシュテーブルにおける成功探索（目的の要素が実際に見つかる探索）の平均所要時間を最小化することを目的とした手法です。

この方法はもともとダブルハッシングの技法に対して考案されたものですが、線形探査（linear probing）や二次探査（quadratic probing）をはじめとする、あらゆるオープンアドレス法の技術にも適用できます。

要素の「エイジ」という概念

オープンアドレス法のハッシュテーブルに格納された要素xの「エイジ（age：年齢）」とは、xが配列位置A[x_i]に置かれるときの最小の値iを指します。言い換えれば、要素がハッシュ関数により与えられた本来の位置から、何回の探査（プローブ）で到達できるかを表す指標です。エイジが大きいほど、その要素の発見までに多くの比較が必要となり、探索が遅くなります。

ブレント法の挿入手順

ブレント法は、テーブル内の全要素のエイジの総和を最小化しようとします。新しい要素xを挿入する際には、以下の手順を実行します。

• 手順1：A[x_i]が空になるような最小の値iを求めます。この位置は、標準的なオープンアドレス法であればxを挿入する場所です。
• 手順2：位置A[x_i-2]に格納されている要素yに着目します。yがそこに存在するのは、ある値j ≥ 0 に対して y_j = x_i-2 となっているためです。
• 手順3：配列位置A[y_j+1]が空であるかを確認します。空であれば、yをA[y_j+1]へ移動させ、代わりにxをA[x_i-2]へ格納します。

通常のオープンアドレス法と比較すると、この一連の操作によって全要素のエイジの合計を1だけ減少させることができます。

一般化されたブレント法

より一般的な形では、ブレント法は 2 ≤ k ≤ i を満たす各kについて、配列要素A[x_i-k]を調べます。そこに格納された要素yが、A[y_j+1]、A[y_j+2]、…、A[y_j+k-1] のいずれかの位置へ移動できるかを確認し、xのための空きを作り出します。これにより、1つの移動だけでは実現できないケースでも、総エイジをより大きく削減することが可能になります。

メリットとトレードオフ

ブレント法の最大の利点は、成功探索の平均時間を大幅に短縮できる点にあります。一方で、挿入時には移動候補の確認という追加の計算が必要となるため、挿入処理のコストが増加するというトレードオフが存在します。そのため、探索が頻繁に発生し、挿入や更新が比較的少ないアプリケーションにおいて、この手法は特に高い効果を発揮します。