Java Collections Implementations (e.g. HashMaps vs HashSet vs HashTable ...), what is the cost of choosing the wrong one?

This is a very general question, but i´ll throw in a couple of thougts.

If you are programming oriented to interfaces, then flexibility wont take a great hit. For example

void foo(List<E> list);

The cost of choosing poorly could be seen in performance penalties. For example, choosing a LinkedList when direct access (as in ArrayList) is what you are looking for.

Sets have a similiar issue. If you want to keep sorted collections with no duplicates, a SortedSet would be a wiser choice over a HashSet. In the latter one, you´d have to sort the entire Set manually (this is, a call to Collections.sort())

<EDIT>

As for maps, there are a lot of different implementations. Each one has a different purpose. For example, there´s SortedMap, analog to SortedSet. Then, there´s WeakHashMap, that doesn´t work like a HashMap, in the sense that keys can be removed by the garbage collector. As you can imagine, the choice between a HashMap and a WeakHashMap is not trivial. As always, depends on what you want to implement with them.

</EDIT>

Regarding the story, in my current project, we replaced a HashSet with a SortedSet because performance was being affected. DataCenter didn´t caught fire though.

My two cents.