В программу приходят объекты.

Условие

В программу приходят объекты. В каждом объекте может быть указан номер телефона и/или логин (либо одно из этих значений, либо оба сразу), а так же полезная нагрузка в виде бинарных данных. Приходящие объекты необходимо сохранять в оперативной памяти соблюдая следующие ограничения: Если у пришедшего объекта логин и/или телефон такие же, как у одного из сохраненных ранее объектов, то сохраненный объект нужно удалить, пришедший не сохранять. Если объект хранится в оперативной памяти более 60 секунд, то его необходимо удалить. Считается, что объекты приходят часто. При этом совпадающих по логину/телефону - кратно меньше от общего количества приходящих объектов.

void process(Object o) { }

Ответ

Храните объекты по внутреннему id, два хеш-индекса по телефону и логину и очередь истечения срока. Совпадение ищется без полного обхода, удаление очищает оба индекса.

Сначала уточните случай, когда телефон совпал с одним объектом, а логин — с другим. Ниже принято правило: удалить все совпавшие старые объекты, новый не сохранять.

При process сначала удалите истёкшие записи по монотонным часам. Затем соберите множество id из индексов login/phone, пропуская отсутствующие поля. Если множество непустое — удалите каждый объект и обе его индексные записи. Иначе сохраните новый уникальный id, payload, индексы и deadline в очереди.

TTL одинаковый и не продлевается, поэтому достаточно FIFO с возрастающими сроками. В очереди храните id, а не payload: запись о досрочно удалённом объекте можно пропустить, не удалив новый объект с тем же телефоном. Фоновый таймер нужен для очистки и без новых входящих данных.

Средняя стоимость поиска O(1), очистка амортизированно O(1) на объект. Задайте лимит памяти; при конкурентных вызовах обновление всех индексов должно быть одной согласованной операцией.