data-structures - 線形プロービングに対する二次プロービング

Question

特定のハッシュ値に対して、線形プローブによって生成されるインデックスは次のとおりです。

h、h+1、h+2、h+3など。

特定のハッシュ値に対して、二次プロービングによって生成されるインデックスは次のとおりです。

h、h+1、h+4、h+9など。

線形の場合はクラスターが形成されますが、二次の場合はクラスターが形成されません。

しかし、両方のプロセス（メソッド）が挿入または検索に同じ数のステップを必要とする場合、二次は線形よりも効率的です。ありがとう！

Answer 1

効率は、線形プロービングと二次プロービングによって形成されるクラスタリングの種類に依存します。

線形プロービングは、一度形成されたプライマリ クラスタリングを形成し、クラスタが大きくなればなるほど、急速に成長します。これにより、パフォーマンスが大幅に低下します。Robert Lafore が良い例を挙げています。ショッピング モールで誰かが気を失ったときに集まる群衆のようなものです。最初の到着者は、犠牲者が倒れるのを見たために来ます。他の人が何を見ているのか疑問に思ったので、後で到着した人が集まります。群衆が大きくなればなるほど、より多くの人々がそれに惹かれます。

二次プロービングは二次クラスタリングを形成します。クラスターが形成されないようにする試みです。アイデアは、プライマリ ハッシュ サイトに隣接するセルではなく、より広く分離されたセルをプローブすることです。類推に従って、群衆を形成するのを避けるために、最初の到着を防ごうとします。セカンダリ クラスタリングは、プライマリ クラスタリングと比較してパフォーマンスの点でより微妙であり、それほど深刻ではありません。

Answer 2

クラスター形成が少ないため。値はより分散されるため、必要なプローブの平均数は 2 次ケースでは少なくなります。