Selecting appropriate data structures and algorithms for a problem is not optimization. It's one of the basic skills and responsibilities of a programmer. That's why the bulk of the first volume of Knuth's _The Art of Computer Programming_ is about data structures.
Using the Set interface is probably the right thing. Then you profile, and if the set implementation you chose is too slow, you just swap it out for another implementation that implements the Set interface.
