40年間のハッシュテーブルに関する予想が覆される

40年間、コンピューター科学者たちは、ハッシュテーブルの検索効率に関する1985年のアンドリュー・ヤオの予想を受け入れてきました。しかし、クラピビンとそのチームは、ヤオの最悪の場合の限界をはるかに超える新しいハッシュテーブルを開発しました。彼らの新しいアルゴリズムは、はるかに高速なクエリと挿入時間を達成し、驚くべきことに、テーブルの満杯率に関係なく、平均クエリ時間は一定です。この画期的な結果は、長年信じられてきた仮説を覆すだけでなく、ハッシュテーブルの最適化のための新しい道を切り開きます。