分離チェインとランダムプロービング

Question

現在、ハッシュテーブルの衝突解決戦略のオプションを検討中です。もともとハッシュテーブルの実装について教えていたとき、私は、Separate Chainingが多くの落とし穴を持つ線形プロービングに比べて好ましい選択であることを学びました。オンラインで研究した結果、Python辞書の基本的な実装では、ランダム化プロービングと呼ばれる手法を使用して、文書ストリングthis CPython fileで説明されているように衝突を解決することがわかりました。

公式辞書の実装で使用されているとすれば、おそらくハッシュテーブルの衝突を解決する最も効率的な方法だと思われます。しかし、ランダムプロービングの実装の複雑さと、別々のチェーニングは一般に許容されるコリジョン戦略であるため、ランダムプロービングのために別々のチェーニングを使用しないでください。私は考えることができる

Answer 1

つの理由：

1）プロービングが別のチェーンよりも安いですが（それは要素）

を格納するために使用されたリンクリストまたは任意のデータ構造を展開するメモリ割り当てを必要としません。

2）データ構造からのオーバーヘッドを格納する必要がないため、（リンクリストの次のポインタなど）