Using [complement operation][1] from set theory. 
And assuming recent notifications limited to 100.

    Set<Notification> updateNotifications(Set<Notification> persisted, Set<Notification> recent) {
        Set<Notification> newNotifications = complement(recent, persisted);
        persisted = persisted.addAll(newNotifications);

        if (persisted.size() <= 100) {
            return persisted;
        Set<Notification> obsoleteNotifications = complement(persisted, recent);
        persisted = persisted.removeAll(obsoleteNotifications);
        return persisted;


    class Notification {
        /* Fields provided by the service */
        boolean dismissed;

`Notification` class presumably deserialized from JSON and `dismissed` set to false by default. After each service fetch call `updateNotifications` to save new notification and delete obsolete ones. Only new notifications are saved, so dismissed flag on previously persisted notifications is preserved.


With a timestamp you can implement `complement` and `delete` more efficiently.