1

ここで、挿入プロセス中に線形プローブを使用したときに、ハッシュ テーブルから値を削除するコストを尋ねられたという質問があります。

インターネットでさまざまなことを読んでわかったことは、負荷率をどうにかしなければならないということです。よくわかりませんが、負荷率と必要なプローブ本数の関係を読んだところ、プローブ本数＝1/(1-LF)でした。

したがって、コストはプローブ配列に依存する必要があると思います。しかし、別の考えがすべてを台無しにします。

エレメントが p プローブに挿入されていて、このエレメントを削除しようとしている場合はどうでしょうか。しかし、この前に、同じハッシュ コードを持ついくつかの要素を既に削除しており、p 未満のプローブへの挿入の一部でした。

この場合、ハッシュ テーブルに空のスロットが表示される段階に到達しますが、削除しようとしている要素が既に削除されているのか、プローブの結果として別の場所にあるのかはわかりません。

また、要素を削除したら、このスロットを特別なインジケーターでマークして、それが利用可能であることを通知する必要があることもわかりましたが、これでは、削除しようとしている要素が不明であるという問題は解決しません。

そのような場合のコストを見つける方法を誰か提案してもらえますか? 非線形プロービングの場合、アプローチは変化しますか?

4

1 に答える 1

4

標準的なアプローチは、「要素を検索し、削除済みとしてマークする」ことです。マーキングには明らかに O(1) のコストがかかるため、総操作コストは lookup: O(1) expectedと同じです。縮退した場合 (たとえば、すべての要素が同じハッシュを持つ場合) には、O( n ) と同じくらい高くなる可能性があります。理論的に言えるのは、予想される O(1) だけです。

負荷率について。負荷係数 (占有バケット数と合計数の比率) が高いほど、期待される係数は大きくなります (ただし、理論上の O コストは変わりません)。この場合、負荷係数には、テーブル要素に存在する両方の数と、以前に削除済みとしてマークされたバケットの数が含まれることに注意してください。

他のプロービングの種類 (二次など) は、理論上のコストを変更しませんが、期待される定数係数またはその分散を変更する可能性があります。「フォールバック」シーケンスを見ると、線形順序で異なるバケットのシーケンスが重複しています。これは、あるバケットのシーケンスが長い場合、隣接するバケットも長くなることを意味します。例: バケット 4 から 10 が占有されている場合、バケット #4 のシーケンスは 7 バケット (4、5、6、...、10)、#5 は 6 などです。二次プロービングの場合、これは当てはまりません。

ただし、線形プロービングには、互いに近いメモリ セルをチェックするため、メモリ キャッシュの動作が向上するという利点があります。ただし、実際には、二次プロービングの場合、フォールバック シーケンスがこれが問題になるほど長くなることはめったにありません。

最後に、線形プロービングの場合、削除されたマークなしで作業することは可能ですが、そのためには、削除手順をかなり複雑にする必要があります (ただし、O(1) が予想されますが、定数係数がはるかに高くなります)。それが価値があるかどうかは、実際のプロファイリングで決定する必要があります。たとえば、これにより、挿入が多少簡素化され、ルックアップが少し簡素化されます。ただし、C++ 実装の場合、ererase() が反復子を無効にするという欠点があります。

于 2012-06-03T20:57:09.467 に答える