私は、IDと日付からなるオブジェクトの集合を持っています。これらのオブジェクトを効率的にIDで検索し、ある時点以前に発生したすべてのイベントを削除する方法でこれらのオブジェクトを保存します。しばらく前にイベントを排除するための効率的なデータ構造ですか？
HashMapとTreeMapを使用することを考えていました.HashMapにはIDが格納され、TreeMapには日付でソートされた要素が格納されています。これはIDによるO（1）ルックアップを提供し、すべての古いイベントを効率的に削除できるようにします。私はまたIDのハッシュテーブルなしで日付のソートされたTreeMapを使ってみました。
これらの操作を効率的にサポートする情報を格納するためのさらに効率的なデータ構造がありますか？あなたがサポートしたい操作が挿入、
をいくつかの時間前に発生したすべてのものを
連鎖されたハッシュテーブルとスプレイツリーの組み合わせであるデータ構造を使用したいと考えています。基本的な考え方は次のとおりです。ハッシュテーブルはID値を問題のオブジェクトにマップし、スプレイツリーはオブジェクトを日付でソートして格納します。構造体に挿入するには、IDハッシュテーブルとスプレイツリーの両方に要素をO（ログn）償却時間で挿入します。ハッシュテーブルでO（1）の予想時間内にルックアップを行うことができます。
問題のパラメータによっては、しばらく前に表示されるすべての要素を非常に効率的に削除することができます。アイデアは次のとおりです。スプレイツリーは効率的に（償却O（log n））、時間がある特定の値よりも前のツリー内のすべてを削除することをサポートします。今度は、この構造体に挿入するエントリに、ある時間以下のすべての値を削除するたびにエントリを挿入しないと、次の削除プロシージャを使用できます。まず、すべてを削除するための効率的なアルゴリズムを使用しますスプレイツリーから削除する必要のあるエントリを償却時間O（log n）で合計し、次に削除したばかりの時間を記録します。その時点から、ハッシュテーブルでルックアップを行うたびに、指定した時間しきい値を下回る要素がある場合は、その要素を削除するだけです。再ハッシュ中にこれを行うと、削除する必要があるハッシュテーブルのすべてを削除するために必要なO（n）作業を必要な時点にただちに広めて、作業を償却することができます。これはIDとO（1）で検索時間O（1）を与え、ハッシュテーブルへの挿入時間を償却します。要するに、この仮定をすることができれば、以下のランタイムを得るでしょう：
素晴らしいアイデアをありがとう。ほんとうにありがとう ！！ – user1180969
@ user1180969-喜んで助けてください！それがあなたが探しているものだと思えば、この答えを受け入れることができることを忘れないでください。 :-) – templatetypedef
どのような比較をしていますか？範囲検索（日付範囲またはID範囲のすべてを検索）を実行しますか？ – templatetypedef
ID検索は基本的にルックアップです。日付検索は今までに何かを削除することです – user1180969