ある学部生が、40 年来のコンピューター サイエンスに対する信念を打ち破りました。 1985年以降、ハッシュテーブルは、ほぼいっぱいになると、データを検索または追加するために多くのスポットをチェックする必要があると信じられていました。 Andrew Krapivin さんは、この速度低下を回避する新しいハッシュテーブル内のデータを整理する方法を発見しました。 スロットをランダムにチェックしたり、順番にチェックしたりするのではなく、彼の方法はより効率的な構造を使用して検索をガイドします。 これにより、テーブルがほぼいっぱいの場合でも、最悪の場合の時間がO(n)ステップから(log n)²ステップに短縮されます。