#java #data-structures #concurrency #map #queue
#java #структуры данных #параллелизм #словарь #очередь
Вопрос:
Мне нужно использовать какую-то структуру данных для хранения ожидающих сетевых запросов.
В идеале я хотел бы очередь, которая также предлагает доступ к карте, поскольку операции в основном заключаются в следующем:
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 мне не поможет.
Комментарии:
1. Взгляните на классы коллекции в
java.util.concurrentпакете.2. ? Какие из них? Я смутно знаком с j .u.c, и ни один из них не кажется явно пригодным для использования в этом случае.
3. Что не так со старым добрым LinkedHashMap,
Map m = Collections.synchronizedMap(new LinkedHashMap(...))?4. Хм. В нем есть
add,getиremove; как бы я реализовалgetFirstKey()и атомарныйpollFirst()?5. зачем им нужно повторять до конца? кроме того, pollFirst потребовал бы от меня ручной синхронизации. в любом случае, есть некоторые возможности….
Ответ №1:
То, что вы описываете, выглядит очень знакомо для LinkedHashMap, который не синхронизирован, но он обеспечивает концепцию упорядочения, а также сопоставляет ключ со значением.
Комментарии:
1. 1. Я не знаю ни одного параллельного класса, который помог бы здесь, поэтому я бы вернулся к использованию LinkedHashedMap и вашей собственной синхронизации. getFirstKey() и pollFirst() могут быть реализованы с помощью (синхронизированного) кода, который: проверяет, что карта не пуста; использует iterator().next()
2. Согласен — это действительно нужно немного доработать в собственном коде — во-первых, по соображениям синхронизации, а во-вторых, для предоставления методов, упомянутых выше.
Ответ №2:
Итак, я бы использовал очередь и карту, но тогда мне нужен способ удалять элементы в середине очереди, когда я получаю ответы, которые не по порядку.
Если вы используете LinkedList в качестве своей очереди, вы можете воспользоваться этим remove(Object o) методом. Очевидно, вам нужно было бы гарантировать согласованность между картой и очередью, поэтому потребуется какая-то ручная синхронизация.
Комментарии:
1. однако здесь проблема в эффективности.
Ответ №3:
Вы смотрели пакет java.util.concurrent, в частности ConcurrentSkipListMap? Вам просто нужно будет определить компаратор, который упорядочит их по времени вставки. ConcurrentSkipListMap
Комментарии:
1. хммм … это означает, что мне нужно добавить поле метки времени в мои данные; Я бы предпочел избежать этого, но вы правы.
2. Или вы могли бы использовать атомарную длину в качестве счетчика.