Originally posted by Marilyn de Queiroz:
I'm not very strong on the ln(n) vs amortized stuff, but I'm thinking that TreeSet is the way to go in this instance.
The difference isn't huge. If searching through a million items in an ArrayList takes 1,000,000 time units, then searching in a TreeSet is going to take ~ 13 units. Searching a HashSet will take ~ 1
unit -- but it's probably a bigger unit, and every once in a while, an insertion will take a whole lot of units.
Going from a List to a Set is going to save a huge amount of time; which set you choose doesn't matter nearly so much.