1 of 7

You might use set operations: complement and union.

Assuming that recent notifications limited to 100.

Map<Id, Notification> updateNotifications(Map<Id, Notification> persisted, Map<Id, Notification> recent) {
    Map<Id, Notification> newNotifications = complement(recent, persisted);
    save(newNotifications);

    if (recent.size() < 100) {
        return union(persisted, newNotifications);
    }

    Map<Id, Notification> obsoleteNotifications = complement(persisted, recent);
    delete(obsoleteNotifications);

    return newNotifications;
}