連鎖ハッシュテーブルに挿入するとき、いつ再ハッシュしますか? alpha = 1のときに再ハッシュする方が良いでしょうか? (アルファ=保存された要素数/ハッシュテーブルのサイズ)連鎖ハッシュテーブルをいつ再ハッシュしますか?
0
A
答えて
0
連鎖を使用すると、バケットに設定された数以上の項目が含まれている場合に、通常はサイズを変更する必要があります。たとえば、バケットに最大5個のアイテムを含めることができます。最初に6番目の項目をバケットに挿入するときは、テーブルのサイズを変更します。
また、理想的な数値が10または3になるように決定することもできます。リサイズ時間とリサイズパフォーマンスのバランスをどのように調整するかはあなた次第です。バケットサイズが小さいほど、平均ルックアップが速くなりますが、テーブルのサイズをもっと頻繁に変更する必要があります。バケットサイズを大きくすると、頻繁にサイズを変更する必要はなくなりますが、平均ルックアップ時間は長くなります。
バケットサイズが10の最悪の場合の検索時間は、バケットサイズが2の場合よりも5倍遅くなります。ただし、それでもリストの順次スキャンよりもずっと速くなり、5xあなたが再ハッシュしなければならない回数の削減。アプリケーションの最適なバケットサイズを試す必要があります。
大きなバケットサイズでルックアップ時間を改善するためにできることは、ルックアップ時に、参照されたばかりのアイテムをバケット内のリストの先頭に移動することです。ここでの理論は、いくつかのアイテムが他のアイテムよりも頻繁に参照されるということです。したがって、常に最新の参照アイテムをリストの先頭に移動すると、より速く見つけることができます。この最適化は、項目が一様に参照されていれば、何の効果もありません。
連鎖すると、しばしば負荷率が150%または200%の良好なパフォーマンスが得られます。時にはさらに高い。再ハッシングとは対照的に、負荷率70〜75%ですばやく劣化し始めます。
関連する問題
- 1. 連鎖ハッシュテーブルと理解解散
- 2. キーの連鎖がハッシュ
- 3. 連鎖的にハッシュを使用する
- 4. ハッシュテーブルはいつ使用しますか?
- 5. jQuery/Javascriptが連鎖しますか?
- 6. 順序付けされていない連想配列では、いつ再ハッシュが発生しますか?
- 7. .NET Reactiveを使用して連鎖を連鎖させる
- 8. 連鎖支払いと払い戻し
- 9. C++の連鎖
- 10. '連鎖' WPFバインディング
- 11. 連鎖コレクションビューソース
- 12. マルコフ連鎖は
- 13. 連鎖型プロバイダ
- 14. JQuery連鎖/カスケードドロップダウンイベント
- 15. 連鎖支払いとPayPal
- 16. 2つの式の結合/連鎖
- 17. 2つの異なるハッシュテーブルを使用して新しいデータ(新しいハッシュ)を生成するPerl
- 18. CloudFoundry UAA連合の連鎖
- 19. coffeescript連鎖呼び出し
- 20. SVNリポジトリを連鎖する
- 21. バリデーションテンプレートを連鎖する
- 22. イベントが連鎖反応を引き起こしています
- 23. Dojo:連鎖アニメーションを繰り返しますか?
- 24. 文字列を一様にハッシュしようとするハッシュテーブル?
- 25. セレン連鎖CSSセレクタ
- 26. jQueryの連鎖セレクタ
- 27. はなぜ、連鎖
- 28. 連鎖アプリケーションのインストール
- 29. アニメーション連鎖のトグルメニュー
- 30. JQuery連鎖イベント(.html)?