TreeSet add operation is O(log(N)) while LinkedHashSet is O(1). The javadoc [1] seems to go with LinkedHashSet being faster too: "This implementation spares its clients from the unspecified, generally chaotic ordering provided by HashSet, without incurring the increased cost associated with TreeSet".

In practice this can of course vary, I found some benchmarks [2] where TreeSet is faster on smaller entries and LinkedHashSet faster on bigger ones. I guess we would need to do benchmarks in our specific case but that would be a bit overkill.

[1] https://docs.oracle.com/javase/10/docs/api/java/util/LinkedHashSet.html
[2] https://github.com/ThreaT/Java-Collections-Benchmark