我需要使用某种数据结构来存储待处理的网络请求。
理想情况下，我想要一个还提供 Map 访问的队列，因为操作基本上如下：
interface PendingRequestStore<K, V>
{
/* add item to queue with value v and key k */
void add(K k, V v);
/* remove and return value of first item in queue, or null if empty */
V pollFirst();
/* return the key of the first item in the queue, or null if empty */
K getFirstKey();
/* get item with key k, or null if absent */
V get(K k);
/* remove and return value of item in queue with key k, or null if absent */
V remove(K k);
}
目的是在发出挂起的请求时存储它们；然后，当我收到响应时，我可以使用指定的密钥删除请求。响应通常不会按照请求发送的顺序到达。如果我可以保证及时响应，常规的 Map 就足够了，但偶尔也会出现故障，我还需要按照添加到队列的顺序重新发送孤立请求。因此，我会使用队列和地图，但是当我收到无序的响应时，我需要一种方法来删除队列中间的项目。
如果我无法避免同步也没关系，但是使用并发数据结构也很好。
有什么建议吗？
注意：键没有顺序，因此是有序映射，例如 ConcurrentSkipListMap 对我没有帮助。
I need to use some kind of data structure to store pending network requests.
Ideally I would like a queue which also offers Map access, as the operations are basically as follows:
interface PendingRequestStore<K, V>
{
/* add item to queue with value v and key k */
void add(K k, V v);
/* remove and return value of first item in queue, or null if empty */
V pollFirst();
/* return the key of the first item in the queue, or null if empty */
K getFirstKey();
/* get item with key k, or null if absent */
V get(K k);
/* remove and return value of item in queue with key k, or null if absent */
V remove(K k);
}
The intent is to store pending requests when they are sent out; then, when I get a response, I can remove the request with the specified key. The responses generally don't arrive in the order the requests were sent out. If I could guarantee timely responses, a regular Map would be enough for that, but there are occasional failures where I also need to resend orphan requests in the order they were added to the queue. So I'd use a queue and a map, but then I need a way to remove items in the middle of the queue when I get responses that are out of order.
If I can't avoid synchronized that's ok, but it would be nice to use a concurrent data structure too.
Any suggestions?
NOTE: The keys have no ordering so an ordered map e.g. ConcurrentSkipListMap won't help me.
发布评论
评论（3）
您所描述的内容对于不同步的 LinkedHashMap 看起来非常熟悉，但它提供了排序的概念，并且还将键映射到值。
What you describe looks very familiar to a LinkedHashMap which isn't synchronized, but it provides the concept of ordering and also maps a key to a value.
如果您使用 LinkedList 作为队列，则可以利用它的
remove(Object o)方法。显然，您需要保证映射和队列之间的一致性，因此需要某种手动同步。If you use a LinkedList as your queue, you can take advantage of it's
remove(Object o)method. Obviously you'd need to guarantee consistency between the map and queue so some sort of manual synchronization will be required.您是否看过 java.util.concurrent 包，特别是 ConcurrentSkipListMap？您只需要定义一个比较器，该比较器将按插入时间对它们进行排序。
ConcurrentSkipListMap
Have you looked at the java.util.concurrent package, specifically the ConcurrentSkipListMap? You will just need to define a comparator that will order them by insertion time.
ConcurrentSkipListMap