JCH
Java Community | Help. Code. Learn.•2mo ago
Lukas

Find out if collections content changed, performant and efficient way

So this is more a question about a programming paradigm than java i guess, but given the following variable 
    HashSet<Whatever> mySet;
    HashSet<Whatever> mySet;
which I recalculate every so often, I want to know whether they contain any updated definition My naive approach would be to keep the previous contents, save the new calculated contents into temp variables of the same types, and compare them using equals (assuming their entries and potentially keys for maps have a good implementation for equals too), and only update the original var if they !equals. But that seems like a waste of memory and quite easy to break. Is there any better solution?
8 Replies
JavaBot
JavaBot•2mo ago
⌛ This post has been reserved for your question.
Hey @Lukas! Please use /close or the Close Post button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically marked as dormant after 300 minutes of inactivity.
TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.
bassus
bassus•2mo ago
You could use a boolean flag an set it to true anytime someone deletes or adds smth? Or is it just like one update methode, where you feed a new HashSet into?
Lukas
LukasOP•2mo ago
Hm, the Set gets calculated from multiple other sets every so often, so I would have to add that complexity there. Tbh I would like to just work based on this final mySet
bassus
bassus•2mo ago
Hmmm, so you are basically saying you are merging a bunch of sets from time to time and only want to update if the are different/check that? Ngl, the checking fun will probably take longer than just merging and asigning the value Because setting the new value is O(1), while the whole checking fun is Omega(n) In short: merging is probably cheaper than checking everything
Lukas
LukasOP•2mo ago
nah, on the one hand it's more than merging (4 sets determine the choice of elements of another map, which get stored in the mySet in question) and further than that I need to know if the mySet content changed for further processing along the chain (an object is created out of mySet)
bassus
bassus•2mo ago
Hmm, if you have to look at each fucking element either way it doesn't matter too much, my condolences Just try to avoid O(n²) and it'll be fine
dan1st
dan1st•2mo ago
You can write your own set that delegetes all calls to an internal HashSet and then add additional logic that ensures you are notified on changes to it but one pitfall is that iterators allow removing elements so you should probably make sure that notifies you as well another option that might be a bit edgy is to use the fail-fast behavior of iterators on concurrent modifications Basically, if you have an Iterator, every modification to the HashSet will throw a ConcurrentModification on consecutive next() calls Note: NoSuchElementExceptions can also occur when there are no further elements - but ConcurrentModificationExceptions seem to take precedence over that so it could still be used to check for modifications (though I am not sure whether that behavior would stay the same in future JDK versions so a more robust approach would be to check both the length and whether the previous's next() method throws a ConcurrentModificationException) but note that you'd need to recreate the iterator if you want to get new notifications something like 
/**
* This class can be used to check whether a HashSet has been modified.
* This class is not thread-safe.
*/
public class HashSetModificationTracker {
  private final Set<?> set;
  private Iterator<?> iterator;
  private int size;

  public HashSetModificationTracker(HashSet<?> set) {
    this.set = set;
    reset();
  }

  /**
  * Resets the modifications to ensure that future {@link HashSetModificationTracker#reset} calls compare to the version of the set at the time of this call.
  */
  public void reset(){
    size = set.size();
    iterator = set.iterator();
  }

  /**
  * Checks whether the set has changed since construction or the last {@link HashSetModificationTracker#reset} call.
  * If the set was empty at the last {@link HashSetModificationTracker#reset} call, elements were added and then removed causing it to be empty again, this is considered to be no change (even if hasChanged() returned {@code true} before).
  * Other than that, any modifications to the set are considered to be "changing" it.
  */
  public boolean hasChanged() {
    if(size != set.size()) {
      return true;
    }
    if(!iterator.hasNext()) {
      // This means the set was empty on the last reset() call
      assert size == 0;
      // While it's possible to add an element and remove it again, the set would still be the same so this case is considered to not be a change
      return false;
    }
    try {
      iterator.next();
      iterator = set.iterator();
      return false;
    }catch(ConcurrentModificationException _) {
      return true;
    }
  }
}
/**
* This class can be used to check whether a HashSet has been modified.
* This class is not thread-safe.
*/
public class HashSetModificationTracker {
  private final Set<?> set;
  private Iterator<?> iterator;
  private int size;

  public HashSetModificationTracker(HashSet<?> set) {
    this.set = set;
    reset();
  }

  /**
  * Resets the modifications to ensure that future {@link HashSetModificationTracker#reset} calls compare to the version of the set at the time of this call.
  */
  public void reset(){
    size = set.size();
    iterator = set.iterator();
  }

  /**
  * Checks whether the set has changed since construction or the last {@link HashSetModificationTracker#reset} call.
  * If the set was empty at the last {@link HashSetModificationTracker#reset} call, elements were added and then removed causing it to be empty again, this is considered to be no change (even if hasChanged() returned {@code true} before).
  * Other than that, any modifications to the set are considered to be "changing" it.
  */
  public boolean hasChanged() {
    if(size != set.size()) {
      return true;
    }
    if(!iterator.hasNext()) {
      // This means the set was empty on the last reset() call
      assert size == 0;
      // While it's possible to add an element and remove it again, the set would still be the same so this case is considered to not be a change
      return false;
    }
    try {
      iterator.next();
      iterator = set.iterator();
      return false;
    }catch(ConcurrentModificationException _) {
      return true;
    }
  }
}
This would also work with (most) other non-thread safe collections but not with thread-safe collections as these don't have the fail-fast behavior of Iterators
JavaBot
JavaBot•2mo ago
💤 Post marked as dormant
This post has been inactive for over 300 minutes, thus, it has been archived. If your question was not answered yet, feel free to re-open this post or create a new one. In case your post is not getting any attention, you can try to use /help ping. Warning: abusing this will result in moderative actions taken against you.

Did you find this page helpful?