data-structures - ハッシュ テーブルの実装に二次プロービングを使用する理由

Question

最近、ハッシュテーブルについて学んでいます。コリジョン レゾリューションの例がいくつかありますが、そのうちの 1 つは二次プロービングです。なぜ二次プロービングを使用するのでしょうか? 彼は、ハッシュ テーブルが常に半分以下になることを知っていますか? もしそうなら、なぜ彼はそもそもそんなに大きなテーブルを使うのですか?

Answer 1

二次リハッシュは、線形ハッシュのクラスタリングの問題を回避するための非常にシンプルで高速な方法です。通常、テーブル サイズが素数の場合にのみ使用されます (これは、他の理由にも適している場合があります)。

「テーブルが半分いっぱいになる」という心配を避けるには、ある時点でリニアプローブに切り替えるのが最も簡単です。(このような切り替えのしきい値テストを通常のif (index >= size) {index -= size;}ブロック内に配置して、パフォーマンスの低下を回避できます。