いくつかの基準に基づいて一意性を提供するFIFOキューがありますか

Question

私はJavaを使用しています。私はFIFOキューにデータを公開する必要があります。このキューは別のスレッドで処理されます。このようにして、メインスレッドをブロックしないようにします。 公開データに関する私のユースケースである： -

• 各データオブジェクトを一意に識別するフィールド、...を有しているので、50の奇数ような「鍵」は存在します。他のフィールドはオブジェクトの残りのデータです。
• 新しいデータオブジェクトが来たら、盲目的にキューに挿入すべきではありませんが、フィールド比較などに基づいてデータが異なる場合は古いものを置き換えてください。それ以外の場合は単に破棄されます。覚えておいてください、フィールドの1つはキーです..残りはデータであり、大きく違うことがあります。
• これらのデータはFIFO単位で処理する必要があります。したがって、キューの種類が必要です。
• 言うまでもなく、スレッドセーフである必要はありません。

誰もがこれらの基準を満たす任意のデータ構造を知っていますか？ありがとう。私はC＃でこのような何かをしなければならなかったとき

Answer 1

は、私は辞書とキューを含まカスタムデータ構造を作成しました。ディクショナリは項目キーによって索引付けされ、値にはキーに関連付けられたデータが含まれていました。キューにはキーのみが含まれていました。キューに項目を挿入するには

は、私はアイテムをデキューするには、以下の（擬似コード）

lock the data structure 
    if key exists in dictionary 
     replace old item data in dictionary with new item data 
    else 
     add new item to the dictionary, indexed by key 
     add new item key to the queue 
release lock 

をした：

lock 
    remove first item key from queue 
    lookup data for that key in dictionary 
    remove item from dictionary 
release lock 
process the item 

私たちは、アップデートの数千人を複数のスレッド間で第二をした、とパフォーマンス上の問題は発生しませんでした。ロックは非常に長い間保持されていません。もちろん、あなたの走行距離は変わるかもしれません。

あなたは、メインスレッドがへの更新をプッシュすることができますロックフリー同時キューを追加することにより、メインスレッドのロックを回避することができます。別のスレッドは、そのキューにサービスを提供し、上述のハイブリッド辞書/キュー構造にアイテムを追加することができる。