Не сказано главного: какого размера map ? т е сколько объектов ? десятки, сотни, десятки тысяч ?
Второе, что не сказано - с какой частотой надо принудительно обновлять, и с какой частотой валятся события на обновление. Одно дело раз в 20мс другое дело раз в минуту. Либо же надо поддерживать эту структуру сортированной при любом обновлении ?
Wataru вам предлагает вполне ризонно список использовать. Если у вас ключ - это время, то вам мап не нужен вообще. Возьмите очередь (Deque) и пихайте только что обновленный объект в конец.
Для принудительного обновления: берете первые 4 из очереди и раздаете в потоки.
Для обновления по событию: придется сначала найти объект в очереди. Для этого пройтись по ней итератором. Это позволяет, например, ConcurrentLinkedDeque Итератор там потокобезопасен, но не итерирует вставки, которые были после взятия итератора. Т е может быть такой момент, что пока вы итерируете, придет ещё одно событие и всунет вам новый объект который в итератор не попадет. Либо ваш поток обновит порядок, а итератор этого не увидит, поэтому приходящее событие нужно будет ручками синхронизировать с выдачей элементов на принудительное обновление. И что-то лучшее боюсь тут сложно придумать. Дайте больше информации о масштабах задачи. Если объектов много, то возможно вместо простой очереди использовать какой-нибудь TreeMap или ещё что-то такое, где есть доступ по индексу.