HashSet jest zwykle szybszy dla add/contains (średnio O(1)), bo jest oparty o hash. TreeSet trzyma elementy posortowane (zbalansowane drzewo), więc operacje są O(log n), ale dostajesz kolejność i zapytania zakresowe.