1

次の形式のデータ タプルに取り組んでいます: [IP、提供されるバイト数、時間]。各 IP に提供されるバイト数をカウントするために、IP で HashMap を作成しました。次に、最近使用されていないキーと値のペアをいくつか削除して、スペースを増やす必要があることに気付きました。時間の制約、たとえば 1 時間を作成し、その期間にアクションのないキーと値のペアを削除したいと考えています。そのため、各ペアの更新時間を節約する必要があります。実際、良いパフォーマンスを得るためには、ペアをタイムスタンプでソートするのが合理的です。

したがって、私がやりたいことは、キーと値のペアの作成または更新時間に基づいてソートされたリストを維持することです。これらの作成時間と更新時間を明示的に知る必要があります。私は 2 つの異なるアイデアを思いつきましたが、どちらをどのように使用するかが正確にわかりました。ここに私の2つのアイデアがあります：

  • 最近更新されたキーと値のペアのタイムスタンプを指す head を持つ LinkedList が必要で、このキーと値のペアがリスト ノードを指すようにします。
  • 作成/更新時間に基づいてソートされた順序で HashMap を維持する必要があります。おそらく、整数値とタイムスタンプを示す長い値を使用して、値を整数からオブジェクトに変更する必要があります。

問題は、効率的な追加/削除/取得のパフォーマンスのためにこれらを Java で実装する方法です。または、作成/更新時間でソートされた HashMap を取得するために使用できるライブラリはどれですか?

4

3 に答える 3

2

LinkedHashMap2セントを提供します...最近、セッション情報を追跡する必要がある同様のことをしました（当時は知りませんでした）。

ConcurrentHashMap一度に複数のユーザー セッションがアクティブになる可能性があり、30 分ごとにクリーンアップを実行して古いセッション データをクリアするため、最終的に を使用しました。私の考えたプロセスは、アプリがセッション データを処理するためにより高速なパフォーマンスを必要とするため、セッション ID をキーとして保持することでした。最も古いデータをクリアする必要がある場合は、値のリストを取得して並べ替えるだけです (クラスが実装しているComparableか、そのための a を記述できるComparator場合)。これは「それほど頻繁に」行われないためです。

それが役立つことを願っています。

PS。LinkedHashMapこれが実装とどのように比較されるのか興味がありますか?

于 2013-03-11T19:39:33.833 に答える
1

これはLinkedHashMapが適切で、removeEldestEntry()メソッドをオーバーライドするケースです。このマップのキーは IP アドレスになり、値は のタプルになり(bytes, last_update)ます。

最初に、「アクセス順序」を使用してマップを作成する必要があります。これは、マップ エントリへのアクセスによって、そのエントリがリスト (MRU) の最後に移動されることを意味します。次に、新しいレコードを取得したら、次の操作を行います。

  • マップに IP のエントリが含まれていない場合は、バイト数で新しいものを作成します。
  • マップにエントリが含まれている場合は、そこからバイト数を取得し、古いバイトに新しいバイトを追加して新しいエントリを作成します。次にput()、古いエントリを置き換えて、マップに新しいエントリを追加します。

タプルは、時間フィールドを現在の時間に自動的に設定する必要があります。ただし、理解する必要があるのは、時間はあまり気にしないということです。これは、リストからアイテムを削除するために使用される単なる属性です。

をオーバーライドし、時間が範囲外の場合はremoveEldestEntry()戻ります。true

ただし、正直に言うと、サイズに基づく削除戦略 (マップを固定数のエントリに制限する) を使用した方がよいと思います。時間ベースの戦略では、DDOS 攻撃にさらされる可能性があります。この場合、多数のエントリが一度に入ってきて、メモリを使い果たします。

于 2013-03-11T19:18:20.023 に答える
0

作成/更新時間で並べ替えるには、その時間を比較する必要があります。つまり、オブジェクトはいつ作成/更新されたかを知る必要があります。versionこれは、オブジェクトの作成時にフィールドをデフォルトで設定しnew Date()、オブジェクトの更新時にフィールドを設定することで、比較的簡単に実現できます。

オブジェクト自体 (インターフェースTreeSet)または. 作成日または更新日を保存するアイテムを保存する場合は、並べ替えプロセスに役立つコンパレータを実装できます。TreeMapComparableComparator

LinkedListとに制限されてHashMapいる場合は、たとえば を使用してリストを並べ替える必要がありますCollections#Sort。の場合、HashMapエントリ セットをソートする必要がありますが、変更できないため、この方法で新しいソート マップを生成する必要があります。

それでも、 aHashMapは順序付けとは何の関係もない構造であるため、それを反復するときにまだいくつかの問題が発生します。ALinkedHashMapでこれを解決できますが、繰り返しになりますが、すべてデータ型の制限に依存します。

于 2013-03-11T17:29:05.130 に答える